_NLogN_'s blog

By _NLogN_, history, 4 months ago, In English

I was solving this problem Generating sets from the Intel Code Challenge Elimination Round. The editorial doesn't discuss the proof for the idea used. Can anyone help with this? I don't understand the greedy step of why we move the maximum element to the largest possible position.
Also most of the contestants got AC with binary search idea. I considered this idea but couldn't get any head way? I was unable to come up with how to implement a check function which can say whether it is possible to make the maximum $$$\leq x$$$? I read Um_nik's solution and I am unable to figure out why the solution works. Any help is highly appreciated

  • Vote: I like it
  • 0
  • Vote: I do not like it