Editorial for Band for Band

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Hints

Hint 1
Show Hint It is always possible for the player with the most tokens to win the tournament, even if other players have just as many tokens. Explain how they can win.

However, in some scenarios it is also possible that the player with the fewest tokens can win the tournament, even if not all amounts are equal. For example suppose we have [1, 5, 1, 1, 2]. How can a player with 1 token win the tournament?
Hint 2
Answer to Previous Hint If the 1 token players all fight it out first, we can make any one of them end up with 3 tokens. They then fight the 2-token player, and have 5 tokens. Then they have the final fight, which they can win with a coin flip.
Show Hint Suppose that we have the list [1, 6, 1, 5, 3, 6, 4], and we already know that the player with 3 tokens can win the tournament. Who else do we know can definitely win the tournament, without doing any thinking?
Hint 3
Answer to Previous Hint We know that the players with 4, 5 or 6 tokens must also be able to win - if the 3-token player has some sequence of games that works for them, then if we swapped them out for the 4-token player, they would also win every game.
Show Hint Based on the previous hint, if the answer is 4 (there are 4 players that can win), then the 4 players with the most tokens are the ones who can win. So the problem boils down to: how do we find the player with the fewest tokens who can still win?

Solution

View Solution Based on the 3 hints, it would be a good idea to sort the players in increasing order of token count. If I want the i^{\text{th}} player (after sorting) to win, it naturally makes sense that they should:

First, fight all players with fewer tokens than them, so they steal all of their tokens.
 Then, fight all remaining players in order of increasing token amounts.

There are two possible solutions to determine the answer efficiently after sorting.


### Solution 1: Binary Search After sorting the result, we can very quickly tell if a certain player can win the tournament by just simulating the optimal scenario mentioned above. Can they win if they first fight all players with fewer tokens, then fight all other players in increasing token order?

If this player can win, then the player with the fewest tokens that can win is either this player, or someone to the left of them in the sorted array.

If this player can't win, then the player with the fewest tokens that can win is someone to the right of them in the sorted array.

This query fits binary search exactly, which we can use to find the leftmost player that can win the game. Each query of the binary search takes O(n) to simulate the game, so the entire binary search takes O(n\log(n)).


### Solution 2: Prefix Sums Notice that if we handle the players in increasing order of tokens, and do the same simulation mentioned above, the next player will always do at least as well as the previous one - so we don't need to completely restart the simulation. Instead, we can keep track of where this player failed. If the player failed to beat the j^{\text{th}} competitor, then it is impossible for anyone before the j^{\text{th}} competitor to win (as in the optimal strategy, you already have all the tokens from players before the j^{\text{th}} competitor). So we skip everyone in the middle, and now simulate if the j^{\text{th}} competitor can win the game.

As such, after sorting, we'd only do O(n) total work.

Comments

There are no comments at the moment.