Thanks for the round and the fast editorials!

UPD: It seems that many participants hate this round because of unclear statements, weak pretests or main tests, too hard time limits and so on. But I think these problems are interesting and challenging, aren't they?

Thanks! :)

1A can be solved using FFT. 109885329

What does "C" denote to in going home editorial ?

Two logarithms in B and logarithm in C and these TLs? Are you crazy? ;_;

Div 2 C was hard :(

min(n^2,n+C)......I think too much.

Can I see the model solution to B, with complexity O((n+m)⋅log(n+m)⋅log(k⋅(n+m)), that passes the constraints? How was the TL set? Thanks

Div.1C has some similarities with Bucket Sort.

I decompose 2C into several cases:

1) We have 4 copies of a value X (e.g. 1 1 1 1 2 3) => YES

2) We have 2 or 3 copies of a value X; and we have several such X (at least 2), (e.g 1 1 2 2 2 5 10) => YES

3) We have 2 or 3 copies of a value X; and there is exactly one X like that (e.g. 1 2 2 2 100 7 9) => two pointers for checking whether we have u and v such that u < X < v and u+v = 2*X => YES/NO.

If YES, it is ok. Otherwise, we remove duplicated elements and continue with case 4.

4) We have only distinct values (e.g. 1 2 5 9 11 13 ...)

If N*(N-1)/2 > 5*10^6: we will have two different pairs (x,y)and(z,t) that meets the condition; because of the Dirictle lemma. Just check bruto-force the first sqrt(10^7) elements.

Otherwise, perform O(n^2) algorithm to check.

Can you unhide the main tests? I can't wait to find why I FSTed:(

Div1 B can be solved in O(n log k). Crt and Gcd is not necessary .

This editorials is so fast that I'm be so surprised of it!

I have a randomised solution for div2C/div1A and I'm not sure if I cheesed system tests or if it's supposed to pass. Can someone take a look at it and hack if possible? Otherwise, if it's supposed to pass, can someone tell me the probability of failure?

Submission: 109876872

I got a FST in Div1B.

But when I submit the code again after contest , it accepted (but 1981ms).

And when I submit the same code again with C++17(64) , it accepted and only ran 1653ms.

What a pity...

My submisson during contest:109857178

Submisson after contest:109891513

With C++17(64):109891826

I found the GFG page, but looking at it I thought it wouldn't pass. After the contest and reading some comments here, I thought it just might.

I tried, and it got AC. Smile in pain. Hehe.

GeeksForGeeks article

Please can someone explain me this : During the contest I submitted ABC and there it said pretest passed and now it is showing -1 in A and C, saying WA in tc 6(for A) and TLE in C problem. How does this happen?Should not they show this during the contest, that i have done 2 questions wrong ?? Please if someone could help me understand what happened ? I am really frustrated rn

Good contest with strong pretests, especially in problem B and problem C.

What's more, the tl of problem B and the ml of problem D are very friendly. No one can get TLE or MLE on them.

How to solve Div1B/Div2D ?

Can anybody please explain why this solution for div2 A is giving wrong answer https://mirror.codeforces.com/contest/1501/submission/109849523

109860426

Who wants to hack my randomized div1A?

For n <= 150, I use a quartic brute force.

For n > 150, I use MITM, where I partition the array into two halves, and randomly select 10^6 pairs from each half, and check for any common sums.

ML in D was brutal. If only $$$q \le 9$$$ instead of $$$10$$$ or number of colors was up to $$$2\cdot 10^6$$$ instead of $$$2.25 \cdot 10^6$$$ it would really be easier xd

Div-2 C solution in gfg:

some modifications will do

Shitty Round especially statement of problem DIV2A.

109889803
For 1500C - Matrix Sorting , the $$$O(nm^2)$$$ approach could be optimized to $$$O(\frac{nm^2}{w})$$$ using bitset, which could pass the tests.

I had figured out a $$$O(nm^{2})$$$ solution for 1C, but now I don't even understand how the editorial reaches $$$O(nm^{2})$$$, let alone understanding optimising it to $$$O(nm)$$$. The editorial is hard to understand.

I think the optimising part made it too difficult a problem for its position as 1C ?!

In particular, can someone please explain this part:

If two rows are in the same class, then the columns that we applied had the same values. Then, we need to find a column that does not break the sequence between the rows inside each of the classes. Let's iterate through such a column every time.

What values are we talking about?

An alternative approach for Div1A.

Let us prove that if $$$n \gt \sqrt{8\max a} + 2$$$ then we can always find such a quadruple. Indeed, sort $$$a$$$ in ascending order and consider the differences $$$a_2 - a_1, \, a_4 - a_3, \, \dots, \, a_{2k} - a_{2k - 1}, \, \dots$$$ These are $$$\left\lfloor \frac{n}{2} \right\rfloor$$$, so there are two of them which are equal. If that weren't the case, we would have

Let $$$i, \, j$$$ be such that $$$a_{2i} - a_{2i - 1} = a_{2j} - a_{2j - 1}$$$. Then $$$x = 2i$$$, $$$y = 2j - 1$$$, $$$z = 2j$$$, $$$w = 2i - 1$$$ is a solution.

Now we proceed as follows. We sort $$$a$$$, iterate over the even values of $$$k$$$ and check if two differences $$$a_{2k} - a_{2k - 1}$$$ are equal. If this is the case, we are done. Otherwise, $$$n \lt \sqrt{8\max a} + 2$$$ and we can bruteforce the answer in $$$O(n^2)$$$.

1500A going home. I notice that ai<=2.5*10^6 but didn't investigate into that.. Indeed, $$$1 \lt =ai+aj \lt =5*10^6$$$ for arbitrary i,j. And if we have n distinct elements, we will have $$$\frac{n*(n-1)}{2}$$$ pairs of different pair of (i,j). If $$$\frac{n*(n-1)}{2} \gt 5*10^6 = \gt n \gt =3162$$$ you are guaranteed to find an answer. Well, doesn't help to solve this problem.

I feel like this approach for div1A/div2C is right but it FSTd. Can someone tell me why?

So first i rewrite the eqn as ax-az = aw-ay. Now I just need to find 2 pairs of indices such that their differences are the same.

For this, I store all elements in a frequency array and iterate over all differences.

for(int i=0;i<N;i++)
    for(int j=0;j+i<N;j+=i)
        //check if j and j+i are present in the freq array
        //Find 2 such pairs and that would be our answer

My submission

div-2D/1B can be solved in linear time. We just need to calculate for each starting position in 1st array, how many matches will be with 2nd array in next m indexes. Here's my AC: 109899040

Can anyone explain why brute force worked in C (going home) even though the constraints are 4≤n≤200000? 2*10^5 should require an O(n) or O(nlog(n)) solution so how O(n^2) worked?

What is the variable "y" in 1B's tutorial?