Editorial for Insider Chocolate
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Hints
Hint 1
Show Hint
It is worth considering some cases, and how solutions to "maximum money made in the firstFor example, what is the answer to the question above for the input
Hint 2
Answer to Previous Hint
First 1 workshop: Nothing.First 2 workshops: Buy 1st, sell 2nd.
First 3 workshops: Buy 1st, sell 3rd.
First 4 workshops: Buy 1st, buy 2nd, sell 3rd, sell 4th.
First 5 workshops: Buy 1st, buy 2nd, sell 3rd, sell 5th.
Show Hint
It might sound silly to do, but imagine we have the following abilities:1. Ali can buy and sell a bet on the same day (This has no impact, however, as he buys and sells at the same price.)
2. If Ali buys a bet, he is always able to sell it for the same price at the end of the game (This is equivalent to just never buying the bet).
3. If Ali makes a sale that he later decides was bad, he can always buy it back for the same price (This is equivalent to just never selling it at the original price).
With these tools, we can eagerly buy a bet, even if it isn't worthwhile, and decide against it at the end of the workshops. Similarly with making a sale. The problem now becomes:
1. Keeping track of all of our options
2. Deciding on the most efficient option
With these tools, how can we alter the answer to the previous hint, so that every solution looks like an extension of the previous?
One thing worth noting is that if you have a section of 3 increasing prices, buying the 1st and selling at the 3rd is the same as buying the 1st, selling at the 2nd, buying at the 2nd and selling at the 3rd.
Hint 3
Answer to Previous Hint
First 1 workshop: Nothing.First 2 workshops: Buy 1st, sell 2nd.
First 3 workshops: Buy 1st, sell 2nd, buy 2nd, sell 3rd.
First 4 workshops: Buy 1st, sell 2nd, buy 2nd, sell 3rd, buy back 2nd at original price, sell 4th.
First 5 workshops: Buy 1st, sell 2nd, buy 2nd, sell 3rd, buy back 2nd at original price, sell 4th, buy 4th, sell 5th.
Show Hint
The optimal choice will always be:1. If the cheapest bet we currently own is more expensive than the next market rate (and the same is true of all the sales I could reverse), it doesn't make sense to sell. So just buy on the next day - we can always reverse it by selling at the same price.
2. Otherwise, it is currently optimal to sell one of our bets tomorrow (or buy back a super cheap bet, and sell it at the current rate). But you need to give yourself the option to buy this bet back at a later date.
So your algorithm needs to be able to compute two things:
1. Of the bets I own at the moment (or the ones I could buy back), what is the cheapest?
2. Of the bets I sold, which is the cheapest to buy back?
Solution
View Solution
As the 3rd hint suggests, we need to use two heaps in this solution, one for tracking the bets we own, and another for tracking the bets we have the ability to buy back. Whenever we get to a new market value, we determine if it makes sense to sell one of our existing bets (or to buy back a bet, and sell it immediately at the new price). If it doesn't, we simply buy at the current price, and add this to the owned heap (we can always sell it at the same price later). If it does, however, we pop our best option from the corresponding heap, and put this new bet value on the owned bets, pocketing the difference. We still want the ability to reverse the sale, though, so we add the new price onto the second heap (because we've already pocketed the difference). There are other solutions that do not require two heaps, for example the following:Let's introduce the idea of options to the problem. Instead of having to buy a bet when it is at a given price, each day you gain the option to buy a bet at that day's price, which you can exercise at any time in the future. This way we only need to exercise an option in order to sell it, and we never need to "hold" any bet.
Each day, 2 things happen. First, we get one more option. Second, if there is some option whose price is lower than today's price, we can be sure that we're going to exercise that option. What we don't know is when it's best to sell that option. However, we don't need to know when the best time is to sell - we can just sell it now, but give ourselves the option to buy it back at the price we just sold it for.
As always, be careful with integer overflow, as we are adding many results together!
Comments