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$$$ largest elements of $$$a$$$ should dominate $$$x$$$ smallest elements of $$$b$$$.
Similarly, some $$$n - x$$$ elements of $$$b$$$ dominate some $$$n- x$$$ elements of $$$a$$$. Therefore, $$$n-x$$$ largest elements of $$$b$$$ should dominate $$$n-x$$$ smallest elements 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).