Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### orz's blog

By orz, history, 8 months ago,

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.

• +15

 » 8 months ago, # | ← Rev. 2 →   +26 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.
•  » » 8 months ago, # ^ |   +5 Yes, it seems to make sense.
 » 8 months ago, # |   0 Auto comment: topic has been updated by orz (previous revision, new revision, compare).
 » 8 months ago, # |   0 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
 » 8 months ago, # |   0 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
•  » » 8 months ago, # ^ |   0 But how to come up with this approach?
•  » » » 8 months ago, # ^ | ← Rev. 3 →   0 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
 » 8 months ago, # |   0 Auto comment: topic has been updated by orz (previous revision, new revision, compare).