### rng_58's blog

By rng_58, history, 12 months ago, ,

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.

•
• +124
•

 » 12 months ago, # |   +38 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)
 » 12 months ago, # |   +54 I saw this in the morning (IMO P5). This could very well be the second easiest/easiest problem on an IOI? Rough Idea Partition N * (N + 1) people into N contiguous groups of N + 1 people each. Give every person a marker which is initially set to FALSE. while (every group has at most one person with a TRUE marker): Take the tallest person with a FALSE marker. Let's call him/her n00b. SET n00b's marker to TRUE  Now look at the two people in the same group that have been marked as TRUE. Let these be n00b and rekt. n00b and rekt will 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 is TRUE. Now we have N - 1 groups, each having at least N people. Recurse. This can be done in O(N2logN) easily.
•  » » 12 months ago, # ^ |   +22 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.)
•  » » » 12 months ago, # ^ |   +1 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.
•  » » » 12 months ago, # ^ |   +13 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.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   +5 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
 » 12 months ago, # |   +39 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.)
•  » » 12 months ago, # ^ |   +31 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"?
 » 12 months ago, # |   0 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.
•  » » 12 months ago, # ^ |   0 I don't understand the step recursive? Please detail your solution, thanks !
 » 12 months ago, # |   +10 a somewhat different solution than the one in the above comments. Spoilerfirst put the players in N groups 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 of x and repeat until the row is empty.this will work because the index of x will always be  ≤ (number of current groups + 1) and after every move every group will lose at most one player expect the group of x.