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 > \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 < \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<=ai+aj<=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}>5*10^6 => n>=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?

Thanks for fast and clear editiorials!

I quickly(I hope so) solve two problems, when I come to think about C, I had a challange. But finally I solve it. And the great thing is I have a rank of 239! I'm really excited about that:-)

The problems are really great and I enjoyed it a lot, thanks!

In Div2 C ( Div1 A ) why the brute force using map and checking sum of 2 pair of indices passes the time limit. Its time complexity is O(n^2) still it passes. Code: https://mirror.codeforces.com/contest/1501/submission/109901974

My code for div1B got TLE result. submission

After using fread,it accepted. submission

The complexity of the code is $$$O((n+m)log(nm))$$$

So , why is the time limit so hard ?

again my A FST. is it weak pretest or my blunder? A Submission

will someone tell me what is wrong with this code https://mirror.codeforces.com/contest/1501/submission/109882653 ? it is showing runtime error on test 8.

Why aren't results for div 2 out yet?? I see div 1 results are already out.

У меня неверное решение которое получилось загнать https://mirror.codeforces.com/contest/1501/submission/109915155 Добавьте тесты посильнее

[TWO CHANDELIERS] Can someone explain me over what variable you can do binary search? I don't get the solution at all :(

This could just be my own perception, but since restrictions on contest writers were tightened, I have found the contests much more difficult. Today I couldn't solve a single question in Div 1. I think that's the first time that's ever happened, but in general the recent contests have been tough.

Very beautiful, careful and short solution by olympiad participant teraqqq. May help to understand the solution.

https://pastebin.com/uhhe3c4v

Sadly ch_egor have not authored any problem but suffered downwotes for managing the contest and problemset. It is not fair.

In Div2 C, I used an intuitive approach to solve that worked. Basically, I iterated over differences (ax — az) from 0 to k*C/N, where C = 2.5*10^6, N is the input size, and k is some constant (say 2) and then I checked whether four such indices exist or not. My question is how to prove that only checking first k*C/N differences works? Also, what is the tight lower bound for such k?

How are we expected to know that the actual value of n used in the main tests is much smaller than the given constraint in div2-C question? An O(n^2) solution should not be accepted according to the given constraints but many people got away with it due to weak test cases. This should be rectified somehow

I have trouble understanding problem div1 A / div2 C

Why is the condition in the editorial sufficient? If we have 4 pairs such that their sum is equal then there is a solution. However, that doesn't imply that there will always be 4 such pairs if there is a solution to the problem.

In other words, what is the proof that there exists a solution to the problem if and only if there are these 4 pairs that are described in the editorial?

Here is the normal solution of d1a instead of the authors' unobvious solution:

If $$$n<10000$$$ run the $$$n^2$$$ solution, else sort the numbers and find the pair of pairs of adjacent numbers with the same difference, also the indices should be different. It always exists because $$$10000^2 > 2.5 \cdot 10^6$$$.

I submitted the code when the overall evaluation failed in the competition and passed it directly after the competition. The machine was too slow during the overall evaluation, which led to unfair treatment. Please restore it to me！！！！！

during

http://mirror.codeforces.com/contest/1500/submission/109859256

after

http://mirror.codeforces.com/contest/1500/submission/109932270 http://mirror.codeforces.com/contest/1500/submission/109931959 http://mirror.codeforces.com/contest/1500/submission/109931910

Quite the same

How to construct a sequence of number for n = 1570 whose answer is "NO" for div1A/div2C ? I found that 4-th example is that situation, however, I can't construct it. Can someone give me an idea ?

DIV2 C question was hard to think how it works in N^2 approach even N was in that range which generally doesn't fit in N^2 approach .. many of those (not all of them) get accepted to that question without knowing proper reason.. LOL..

Problem C. Going Home. In statement n is <= 200000. So why O(min(n^2,n+C)) doesnt have TLE?

In the problem B, the numbers are distinct which isn't stated in the statements. That's a major issue.

what is "y" in the editorial of div1B/div2D?

They added few more test cases in Div 2 Problem C. Why my previous AC code is giving TLE on Test Case 73?

I haven't seen anyone else do this, but div. 2 B can be solved with Fenwick. 109919812

The idea is basically to keep a BIT of the number of layers of syrup on each layer of cake.

I'm going crazy. Can anyone tell me why my solution gives WA on test 12? problem div2.D and my code, Thanks.

How is C:Going Home Accepted in quadratic time?

div1A I got ac,but my code 110017025 was wrong wrong test: 5 1 1 1 1 4

[Div-1 'B']

If n and m are not coprime, participant can make transition (n,m)→(ngcd(n,m),mgcd(n,m)), solve new equations, and then make reverse transition

How to do that?

Can somebody please tell me why my code:110064321 TLEs in Div.2D and any possible optimization I can do? Thanks.

My solution for d works in O(max(n, m)) time. So first you check if the solution will be found after n*m days(because that will 100% get both sequences lined up again). To do so you take the smaller array and find how many same numbers it will have in every cycle(1 cycle is min(n, m) days) in bigger array. For example if you have 3 2 1 0 and 3 1, at cycle 0 (3 2 : 3 1) you will have 1 same occurance, at cycle 1 also(2 1 : 3 1) and in others 0.To do so fast you find where every element from smaller array belongs in bigger and to get the position of cycle subtract the index of element in smaller array(so 1 is on index 2 in bigger array but because it is second element in smaller it will belong to 2 — 1 = 1 cycle). After that you just n times add number of different elements in cycles (to do so you just have i — cycle you are currently at which is 0 at start and with every iteration it will become (i + m) % n because 1 cycle is m days so you move m elements on bigger array). After you add all the values(lets say into SUM) of numberofdifferentoncyclei you can check if that number is bigger than k and if it is you add to your answer(int)(k / sum) * n * m and subtract from k (int)k / sum * sum so we now know that k < sum. After that we can just do one more iteration over cycles to find at whichn our sum will become greater than k and get our answer. Check the code for better understanding.110062516

For 1500A - Going Home, I found the editorial's solution really hard to optimize to fit into the 2s time limit. However, if we first do an $$$O(n)$$$ pass to filter out the test cases where there is a value with frequency $$$\ge 4$$$, or at least two non-unique values (in those cases, a solution can be easily constructed), we could then know that the solution, if it exists, must involve four distinct values. Thus we only need to store up to one pair for each sum (finding the second disjoint pair will allow us to construct the solution) This significantly improves the constant factor for the solution, and easily passes in Kotlin.

Matrix Sorting's tests can be passed using O(n*m*m) solution.

TL for Div 1 E is tooooooo tight !!!

.