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 *h*_{i}. 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 2*N* 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 ≤ *h*_{i} ≤ 10^{9}, *h*_{i} are pairwise distinct.

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)

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

Rough IdeaN* (N+ 1) people intoNcontiguous groups ofN+ 1 people each.FALSE.TRUE. Let these ben00bandrekt.n00bandrektwill be in the same position in our final solution. Kick them out for now and everyone else in their group. Also kick out everyone who's marker isTRUE.N- 1 groups, each having at leastNpeople.This can be done in

O(N^{2}logN) easily.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.)

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.

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.

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

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.)

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"?

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

ideaFirst, divide N(N+1) players into N segments, each with N+1 consecutive players.

Consider the second shortest player in each segment, choose the shortest one, suppose he is in segment X and his height is H.

Then remove whole segment X except two shortest players, and the (one) shortest player in each other segments. After that, all shortest player in other segments must be taller than H. (As H is the smallest second shortest)

Now we have (N-1)N players and going to choose N-1 pairs, it went recursive.

O(N^2logN) due to sorting issues.

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

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

Spoilerfirst put the players in

Ngroups where the first group contains the (N+ 1) shortest players, and the second group contains the second (N+ 1) shortest players and so on.let's find the leftmost player such that this player has exactly one player to his left in the same group as him and call him

x, those two players will be included in the answer, now remove all the the people in this group and all the people to the left ofxand repeat until the row is empty.this will work because the index of

xwill always be ≤ (number of current groups + 1) and after every move every group will lose at most one player expect the group ofx.