rp++ rk--

Is the online mirror's scoreboard synced with the actual contest scoreboard?

There is a solution for E in $$$O((n + q)\log n)$$$, using m stacks.

https://codeforces.me/contest/2206/submission/365799729

problem — K

consider this testcase

if you got WA in TC-22

1
53
00000000001111111133344555555666666666788889999999999

I hope everyone can pass smoothly, good luck.

Was sqrt decomposition unintended for D? I had to use some stupid tricks to make it fit within the TL

someone explain solution of problem K...

For Problem K:

I think you can avoid binary search entirely and get an O(N) solution.

I solved it by greedily trying to generate valid solutions and just counting how many there were, breaking when no more solutions can be found. It takes O(1) to generate the next solution, and there's a maximum of N/4 solutions.

Is this a faster/simpler way of solving K, or is there a benefit of using binary search like the intended method?

373286371 2206K - Time Display Stickers

A greedy solution to the last question (K. Time Display Stickers) without binary search

#include <iostream>
#include <unordered_map>
using namespace std;

void solve(){
    int n;
    cin >> n;

    string seq;
    cin >> seq;

    unordered_map<int, int> freq;
    int non_zero = 0;
    int og_non_zero = non_zero;


    for (int i = 0; i < n; i++){
        freq[seq[i] - '0']++;
    }

    for (auto pr: freq){
        if (pr.second > 0){
            non_zero++;
        }
    }

    long long combinations = 0;

    while (true){
        bool d1_found = false;
        int d1;
        for (int i = 0; i < 2; i++){
            if (freq[i] == 0){
                continue;
            } else {
                freq[i]--;
                d1_found = true;
                d1 = i;
                break;
            }
        }

        if (d1_found == false){
            cout << combinations << "\n";
            return;
        }

        bool d2_found = false;
        int d2;
        int limit;
        if (d1 == 0){
            limit = 9;
        } else {
            limit = 1;
        }
        for (int i = limit; i >= 0; i--){
            if (freq[i] == 0){
                continue;
            } else {
                freq[i]--;
                d2_found = true;
                d2 = i;
                break;
            }
        }

        if (d2_found == false){
            cout << combinations << "\n";
            return;
        }

        bool d3_found = false;
        int d3;
        for (int i = 5; i >= 0; i--){
            if (freq[i] == 0){
                continue;
            } else {
                freq[i]--;
                d3_found = true;
                d3 = i;
                break;
            }
        }

        if (d3_found == false){
            cout << combinations << "\n";
            return;
        }

        bool d4_found = false;
        int d4;
        for (int i = 9; i >= 0; i--){
            if (freq[i] == 0){
                continue;
            } else {
                freq[i]--;
                d4_found = true;
                d4 = i;
                break;
            }
        }

        if (d4_found == false){
            cout << combinations << "\n";
            return;
        }

        //cout << d1 << d2 << ":" << d3 << d4 << "\n";
        combinations++;
    }
}

int main(){
    int testcases;
    cin >> testcases;

    for (int i = 0; i < testcases; i++){
        solve();
    }
}

2206-K Time Display Stickers

My Approach:

First, I create an array of size 10 to store the frequency of each digit. I convert each character into an integer and use it as an index to count the available digits.

Then, I create four integers: st, lt, mid and ans.

After that, I start a while loop and check the condition arr[st] != 0 && st < 2.

For the hour, I select the required digits while updating their frequencies. Then, I calculate the minutes. The first digit of the minutes must be between 0 and 5.

Whenever a complete valid time can be formed, I increment ans.

The process continues until no more valid times can be constructed.

Code:

import java.util.Scanner;

public class Sol {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while (t-- > 0) {
            int n = sc.nextInt();
            String str = sc.next();

            int[] arr = new int[10];

            for (int i = 0; i < n; i++) {
                char ch = str.charAt(i);
                int num = ch - '0';
                arr[num]++;
            }

            int st = 0;
            int lt = 9;
            int mid = 5;
            int ans = 0;

            while (st <= lt) {

                if (arr[st] != 0 && st < 2) {
                    arr[st]--;

                    if (st == 0) {
                        boolean hour = false;

                        for (int j = lt; j >= 0; j--) {
                            if (arr[j] != 0) {
                                arr[j]--;
                                lt = j;
                                hour = true;
                                break;
                            }
                        }

                        if (!hour) {
                            break;
                        }
                    } else {
                        if (arr[st] != 0) {
                            arr[st]--;
                        } else {
                            break;
                        }
                    }

                    boolean minuteFirstDigit = false;

                    for (int i = mid; i >= 0; i--) {
                        if (arr[i] != 0) {
                            arr[i]--;
                            mid = i;
                            minuteFirstDigit = true;
                            break;
                        }
                    }

                    if (!minuteFirstDigit) {
                        break;
                    }

                    boolean minuteSecondDigit = false;

                    for (int i = lt; i >= 0; i--) {
                        if (arr[i] != 0) {
                            arr[i]--;
                            lt = i;
                            minuteSecondDigit = true;
                            break;
                        }
                    }

                    if (!minuteSecondDigit) {
                        break;
                    } else {
                        ans++;
                    }

                } else {
                    st++;
                }
            }

            System.out.println(ans);
        }
    }
}