this educational round felt a bit harder than previous edcuational rounds…

thank you for this beautiful round.

Why the rating isn't updated yet?

add it in contest material or annoucement blog i had been waiting for this

How long do we need to wait for the rating to update ?

1 2 1 1 2 2

in D if we see what they watched it will look like

1 2 null

1 2 null

so all three days are same work

then why only 4 segmenst why not 6 segment ??

i am confused please help me

the problems where amazing this round but the pretests where kind of weak but yea overall top tier

Another approach to Problem D uses binary lifting.

The general idea of my solution is fix the endpoint $$$l$$$ and count the valid right endpoints $$$r$$$(for both arrays)

We have the following observation: If the segment $$$[l, r]$$$ is valid, then the segment $$$[l, r - 1]$$$$$$(l \lt r)$$$ is also valid. So, we can consider an approach of finding the largest position that satisfies the condition, and then add $$$r - l + 1$$$ to the answer, where $$$r$$$ is the largest valid position.

Consider the subarray $$$[l, r]$$$, If $$$a[l] = b[l] = 1$$$, then position $$$l$$$ can be treated as a valid starting point for both arrays. In other cases, we need to find the first position greater than $$$l$$$(which equals $$$1$$$) in both arrays $$$a$$$ and $$$b$$$, denoted by $$$\text{pos}_a$$$ and $$$\text{pos}_b$$$ respectively. If $$$\text{pos}_a \ne \text{pos}_b$$$, then the two people will not watch the first movie at the same time. Therefore, the valid positions for $$$l$$$ range from $$$l$$$ to $$$\min(\text{pos}_a, \text{pos}_b) - 1$$$. Otherwise, the segment from $$$l$$$ to $$$\text{pos}_a$$$ ($$$\text{pos}_a = \text{pos}_b$$$) is still valid. Let $$$next_a$$$ be the nearest position to the right of $$$pos_a$$$ that has value $$$2$$$, and let $$$next_b$$$ be the nearest position to the right of $$$pos_b$$$ that has value $$$2$$$. Thus, for Alice and Bob to both watch the second movie, we must have $$$next_a = next_b$$$. From this, we have the idea of finding a movie (each movie corresponds to a position) such that Alice and Bob watch it together as the final one. Let the last movie watched be $$$p$$$, located at index $$$idx$$$ in both arrays. If there is no occurrence of $$$p + 1$$$ in both arrays at any position greater than $$$idx$$$, then $$$r = n$$$. Otherwise, we can process like conditions $$$\text{pos}_a \ne \text{pos}_b$$$, use $$$n$$$ vector contains index of value and use binary search.

Now, we consider each joint movie watch as a “jump” on the array. Thus, we need to determine how many steps we can jump in total. To solve this problem, we define an array $$$isNext[idx]$$$, which represents the next position we can jump to. Note that $$$isNext$$$ is only meaningful for indices $$$idx$$$ such that $$$a_{idx} = b_{idx}$$$. Let $$$p = a_{idx} = b_{idx}$$$. Then, $$$isNext[idx]$$$ is true if the first position greater than $$$idx$$$ in array $$$a$$$ with value $$$p + 1$$$ is equal to the first position greater than $$$idx$$$ in array $$$b$$$ with value $$$p + 1$$$. For the brute-force approach, we can keep jumping until no further moves are possible. However, we can improve by using binary lifting on the $$$isNext$$$ array.

Time complexity is $$$O(n \log n)$$$.

nice problems

what could be the possible rating for D?

B only needs to be computed at the odd and even nodes; it does not need to be computed at every point.

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        // int n;
        string s;
        cin >> s;
        int n = s.length();
        // cin >> n;
        int ans = 0;
        for (auto i : s)
        {
            if (i == '4')
                ans++;
        }
        int twos = 0, others = 0;
        vector<bool> m(n, false);
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '1' or s[i] == '3')
            {
                bool found = false;
                for (int j = i + 1; j < n; j++)
                {
                    if (s[j] == '2')
                    {
                        found = true;
                        if (!m[j])
                        {
                            twos++;
                            m[j] = true;
                        }
                    }
                }
                if (found)
                    others++;
            }
        }
        ans += min(others, twos);
        cout << ans;
        cout << endl;
    }
    return 0;
}

O(N^2) I am really frustrated. Why my solution for problem B is incorrect? Apart from TLE what is wrong in the logic? See we will need to remove all the 4s. We then need to make sure that no 2 comes after 1 or 3. So we take the minimum of the (one + threes) and twos and then add it to number of 4s. What is wrong in this? I also have O(n) solution for the same problem. Please someone help me out. God bless you!

hey why my code for digit string is wrong in second test

#include<iostream>
#include<string>

using namespace std;

int main(){
    long long t;
    cin>>t;
    for(long long i = 1 ; i <=t ; i++){
        string Str;
        cin>>Str;
        long long a = 0;
        long long b = 0;
        long long moves = 0;
        for(auto& e : Str){
            if(e=='4'){
                moves++;
                continue;
            }
            if((e == '2') && a>=0){
                b++;
            }
            else{
                a++;
            }
            if(e=='1' || e=='3'){
                if(b!=0){
                    if(a-1>=b){
                        moves +=b;
                        b=0;
                    }
                    else{
                        moves += a-1;
                        a=1;
                        b=0;
                    }
                }
            }
        }
        if(a>=b){
            moves+=b;
        }
        else{
            moves+=a;
        }
        cout<<moves<<endl;
        }
            return 0;
    }

i dont get it what is going wrong with my code

so it is enough to choose the news item with the minimum Ic(i,j). But this is equivalent to choosing the news item with the minimum ci.

Can someone please explain this again?

$$$min_{ p_i \lt tp_j } I_c(i, j) == min( min_{ p_i \lt tp_j } I_c(i, j), min_{p_k \gt = tp_j}(I_c(k, j) + I_p(k, j) )$$$ ?

Another approach for D: 375158478

guys , please , dislike my comment , please :)

I solved 4 questions, but it is still showing skipped on my end and my rating has not been updated.

For problem E, I have made 2 submissions 379607342 and 379607834. The first submission has a typo in case3, due to which binary search is performed on a different array than the intended one. However, both of these solutions have passed the system tests.

The first solution should give a Wrong Answer in cases where the optimal answer comes strictly from an index $$$i$$$ where $$$p_i \ge tp_j + d_j$$$.

One of those test cases is:

2
100 100
12 100
1
10
10
20

The expected output is 42 but this 379607342 submission gives output as 60.

C has every type of test case that one can think of

Editorial of E blew my mind :)