rng_58's blog

A Constructive Task
By rng_58, history, 7 years 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

Comments Comments (9)
| Write comment?
»
7 years 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)

→ Reply
»
7 years 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
→ Reply
  • »
    »
    7 years 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.)

    → Reply
    • »
      »
      »
      7 years 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.

      → Reply
    • »
      »
      »
      7 years 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.

      → Reply
      • »
        »
        »
        »
        7 years 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

        → Reply
»
7 years 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.)

→ Reply
  • »
    »
    7 years 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"?

    → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

Spoiler
→ Reply