rng_58's blog

By rng_58, history, 3 months ago, In English,

Recently I solved an interesting constructive task. Can you solve it? I'll reveal the source a bit later.

N(N + 1) soccer players stand in a row. The height of the i-th player is hi. No two of them are of the same height.

Sir Alex wants to remove N(N−1) players from this row leaving a new row of 2N players in which the following N conditions hold:

  • No one stands between the two tallest players,
  • No one stands between the third and fourth tallest players,
  • No one stands between the two shortest players.

Find one possible way to achieve this.

Constraints: 2 ≤ N ≤ 500, 1 ≤ hi ≤ 109, hi are pairwise distinct.

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

»
3 months ago, # |
  Vote: I like it +38 Vote: I do not like it

Hm, hm, what the source could be, I have no idea ;p. Hunter's problem seems even more interesting to me (however I have no idea about it)

»
3 months ago, # |
  Vote: I like it +54 Vote: I do not like it

I saw this in the morning (IMO P5). This could very well be the second easiest/easiest problem on an IOI?

Rough Idea
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I feel like you are very much underestimating the difficulty of this problem.

    In my opinion, most of the easy and medium IOI problems don't really require you to come up with new ideas or solution approaches, but instead just make observations or optimizations. (Not to say they aren't good problems.)

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yeah, now that I think about it, this is not very IOI-ey (definitely not the easy IOI problems). It feels like one of those random elegant POI problems though.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Definitely not easiest, but I think this makes a easy~med IOI problem — for example, 15 sorting / 16 messy. They all require us to come up with new ideas, even though it's simple. I think this problem have similar difficulty.

      People near me generally agreed that this one was kinda easy, although I didn't asked them to compare with other problems.

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Hmm, for me sorting is very standard good IOI problem, does not require much innovative idea. Anyway I agree it's as hard as 16 messy, 3rd easiest problem out of 6.

        I wonder where he found this elegant problem...

        UPD: Finally I realized the problem is originally from IMO this year :p

»
3 months ago, # |
  Vote: I like it +39 Vote: I do not like it

I was stuck on this problem for maybe 2 hours, then I saw rng_58's post and solved it in 10 minutes after that.

I'm not sure how to interpret this. (Maybe it's time for me to change up my problem solving strategy.)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    One is never solving these problems ex nihilo. Cultural ideas about the nature of the competition very much play a role in how one thinks about them.

    Since this is the IMO people expect the answer to take a certain form and never consider the question "if I wanted to compute this reasonably quickly what would I do"?

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

Nice problem. I can't stop myself from thinking of it.

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

    I don't understand the step recursive? Please detail your solution, thanks !

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

a somewhat different solution than the one in the above comments.

Spoiler