A future week

The Oct 2 - Oct 8 week contained Codeforces Round 438 (problems, results, top 5 on the left, analysis). With problem G out of reach, the competition turned to the first six problems + challenges, and cubelover has excelled at both — congratulations on the win!

Problem E continued the streak of problems with nice and simple statements. Two players are playing a real-time game on a tree. The first player has one token, and in one second can move it to an adjacent vertex of the tree. The second player has several tokens, and can move them with infinite speed whenever they want. However, as soon as a token of the second player meets the token of the first player, this second player's token is removed from the game. The goal of the first player is to remove all tokens of the second player as fast as possible. How long would it take in worst case? You are given the tree and the starting locations of all tokens. There are at most 50 vertices in the tree, and at most 50 tokens.

In my previous summary, I have mentioned a similarly simple sounding problem: you are given the price of a stock for each of n days. You start with 0 stocks, want to finish with 0 stocks, and do one of three things each day: buy 1 stock, sell 1 stock, or do nothing. How much money you can earn? n is up to 300000.

The solution proceeds as follows. A new day starts, with stock price a. We will then create two futures for this stock: we will remember that we can buy two units of stock at price a (the reason for creating two futures instead of one will become clear soon). Then we will sell one unit of stock at price a. Which one? Of course, we will take the remaining future with the lowest price, act on it (i.e. buy a unit a stock at that price), and then sell it at price a, realizing the profit. Note that this might be the future that we just created, in case all previous ones were more expensive, in which case the buy and sell cancel out.

Note that for each stock, we create one sale and at most two buys via the futures. We can treat the first buy as cancelling the sale, and the second buy as the actual buy — this is the reason we need two futures.

As an example, suppose the stock prices are 4, 3, 6, 5. Then our algorithm proceeds as follows:

• Add two 4s to the futures priority queue, now it has [4, 4].
• Remove the lowest future and pair it with a sale at 4, for a profit of 4-4=0. Our queue is now [4].
• Add two 3s: [3, 3, 4].
• Remove the lowest and pair it with 3: profit is 3-3=0, queue is [3, 4].
• Add two 6s: [3, 4, 6, 6].
• Remove the lowest and pair it with 6: profit is 6-3=3, queue is [4, 6, 6].
• Add two 5s: [4, 5, 5, 6, 6].
• Remove the lowest and pair it with 5: profit is 5-4=1, queue is [5, 5, 6, 6].

The total profit is 0+0+3+1=4, and what happened is that we bought at 4 and 3 and sold at 6 and 5. After careful consideration one can see that all valid sequences of stock sales can be expressed in our framework, and that greedily choosing the cheapest future every time leads to an optimal solution thanks to an exchange argument. Still, I find the fact that this greedy approach works very beautiful!

Thanks for reading, and check back later!