How to solve the C problem with dfs?

Nice Problem Set :). Got to learn few new things.

D was a nice one :)

D was very good (well, every problem was very good actually). Looking forward to your next rounds!

Is there anyone who solved problem C using 2SAT method?

Good questions

C is so elegant, I can't believe I missed that observation

Nice editorial shashwatchan. No BS, straight to the point and easily understandable.

Well, I came up with observation for C just before I enter here :(

Such a good problemset, but it's quite a pity that it unrated :-(

problems are soo elegant

I have a doubt on C. I am not sure of my solutions time complexity. Could anyone please prove it or hack it. 98306400

I need proof for a magical part as suggested in an editorial in Problem-D. How the last element will automatically be the same by applying operations for the first n-1 elements.

A great problemset ! Requires creativity & clever observations .

Nice problem set.

The problem set was really nice! Looking forward to more contests from you peeps! :)

Is there any math to know how reasonably sure we can be that we have the 2 children of the root after $$$q$$$ queries in problem F? Is 420 deliberately chosen or is it just a meme number?

In problem B I am using map to check whether there are duplicates but getting runtime error, pls tell me why is it so?

int main(){
    int tc;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        vector<int> v(n);
        map<int,int> mp;
        int flag = 0;
        for(int i=0; i<n; ++i){
            cin>>v[i];
            if(mp.find(v[i])!=mp.end()){
                flag=1;
                cout<<"YES"<<endl;
                break;
            }
            mp[v[i]]++;
        }
        if(flag==0)
            cout<<"NO"<<endl;
   }
    return 0;
}

https://mirror.codeforces.com/contest/1438/submission/98367651

dont know why my solution is not passing test case 2 for problem C :( can anyone help??thanks soltn :https://pastebin.ubuntu.com/p/m7rG5Rkj5y/ UPD:i got my mistake

I have a different approach for problem E.

Let's denote psum[i] as the sum of A[j], for all 1 <= j <= i.

First, we can notice that a + b >= a ^ b. So, we can compute all pairs of indexes l and r, such that A[l] + A[r] >= psum[r-1] — psum[l]. There are at most nlogn of this pairs, because for a fixed l, the valid r's need to be at least two times bigger than the previous one, so there are at most logn for a fixed l, and the worst case is something like 1, 1, 1, 1, 2, 4, 8, ...

Then we can find all such pairs in the following way. First, with simple transformations we can show that a pair is valid if A[r] — psum[r-1] >= -A[l] — psum[l]. Then we can maintain a set of pairs (-A[l]-psum[l],l) and iterate over it while the condition remains true, and for each of these pairs we can check if A[l] ^ A[r] = psum[r-1] — psum[l] and count the number of good pairs.

when will rating will get updated ?

Here's a bonus problem for A: What if the numbers have to be pairwise distinct? Take $$$n \lt 1000$$$ and the numbers you output must be less than $$$5000$$$.

In problem B, for the test case array-{1 2 3}, why is the answer NO, as we have {1,2} and {3} as subarrays having same sum.

so there's a funny and unproven solution for task C by Ali_Tavakoli :

for every pair of adjacent elements, we check whether they are equal or not, if they are equal we randomly change one of them which hasn't been changed yet. After we check all the pairs, we check whether the matrix is good or not, if the matrix is good then we have an answer and we are done, if not we will repeat this process until we find a good matrix. he has no proof for this solution but by doing at most 400 repetitions of the algorithm above, he managed to pass the sys tests.

Stupid comment ahead I think i might have misunderstood the question "1438D — Powerful Ksenia". So, please help me out here. Let's say the array is 1 2 3 4 Now, the operations are as follows: 1 2 3 4 (initial array) -> 0 0 0 4 -> 0 4 4 4 -> 0 0 0 0. Number of operations = 3, and all array elements are equal. After looking at the editorial, XOR of the above array is 4 and the array length is even. So, answer is "NO". What am i missing?

Can you help me explain Problem B?

I am not getting problem D.

Where can i practice these puzzle problems like 1438C — Engineer Artem? and why are the tags at problem C so weird? constructive algo + 2-SAT + FFT + chinese theorem + flows !!