I recorded my participation in CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!), after which I explained the solutions of problems 1896A - Jagged Swaps, 1896B - AB Flipping, 1896C - Matching Arrays, 1896D - Ones and Twos and 1896F - Bracket Xoring. The link to the video is https://youtu.be/xNYdRfbuBQ8, but the video is still processing and will be ready for watching in several minutes.

I guess some of you, who will watch this video, have solved problem C. Could you please share your observations which led to the solution? I believe that the fact presented in the editorial is really unobvious, although I didn't have the worst intuition possible in this problem's plot. Instead I came up with a solution which took a (code)ton of time and featured an intricate way of applying `std::set`

with `upper_bound`

and discrete continuity. Not bad for making the editorial educational, but really inappropriate for succeeding in the actual contest.

**UPD:** the video is uploaded, but is temporarily in low resolution.

**UPDUPD:** the video is now high quality.

My logic was as follows.

If such a permutation exists, then some $$$x$$$ elements of $$$a$$$ dominate some $$$x$$$ elements of $$$b$$$. But this implies that $$$x$$$

largestelements of $$$a$$$ should dominate $$$x$$$smallestelements of $$$b$$$.Similarly, some $$$n - x$$$ elements of $$$b$$$ dominate some $$$n- x$$$ elements of $$$a$$$. Therefore, $$$n-x$$$

largestelements of $$$b$$$ should dominate $$$n-x$$$smallestelements of $$$a$$$.But since these four sets are disjoint, then these two conditions are sufficient.

Yes, it seems to make sense.

Auto comment: topic has been updated by orz (previous revision, new revision, compare).I solved it a brainded way.

Sort the arrays, and increase/decrease the good pairs $$$(a_i > b_i)$$$ depending on the current number of good pairs and $$$x$$$.

234279440

Get max x elements from array a and min x elements from array b lets say x = 3 , a = {9,8,7,6,4} b = {1,2,3,5,6} then for 9 take 3 , 8 take 2 and 7 take 1 this greedy thinking remaining elements for every element get lower_bound for it 6 take 6 and 4 take 5

But how to come up with this approach?

just greedy thinking , the condition a[i]>b[i] yes?

If you get rid of the largest x numbers in array a With the smallest x numbers of array b This would increase your chances of getting b[i]>=a[i] because you remove x max elements from a and x min elements from b

Auto comment: topic has been updated by orz (previous revision, new revision, compare).