722D: Generating Sets

Revision en1, by _Bishop_, 2022-01-21 20:46:44

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English _Bishop_ 2022-01-21 20:46:44 766 Initial revision (published)