orz's blog

By orz, history, 8 months ago, In English

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.

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
8 months ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

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, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yes, it seems to make sense.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But how to come up with this approach?

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

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