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.
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?
This can be done in O(N2logN) 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"?
a somewhat different solution than the one in the above comments.
first 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.