Keep an array a such that a[i] gives the most valuable coin that is not worth more than i dollars.

Me neither. Can someone kindly explain again ?

Problem E:

Imagine you have N coins. First you put a frequency array for each coin and also a lookup array where NEXT[c] = (greater coin that does not exceed c), both can be done in O(N) precomputation. The thing is this will help us simulate the algorithm in , starting with C (total cost) we can get NEXT[C] and subtract all the coins possible from C this is done with min(FREC[NEXT[C]], C / NEXT[C]). The thing is that all the coins subtracted in each step are different. Since they are different, it is not POSSIBLE to have subtracted more than different number without exceeding C. This can be seen assuming the worst case of numbers subtracting which will sum up to C or more. So our simulation is efficient. Now we need to run the simulation with each coin. The thing is, giving only one coin will give the same result than giving multiples (proof below). So we can run the simulation with each possible coin from 1 to C.

Proof for needing only one coin: If you remove coins in order -> S - c1 - c2 - x - c3 - c4 - c5 - y - c6... then it is proven that instead of subtracting x in step three we can subtract x+y and he will pick the same set of coins. We know for sure that S - c1 - c2 - x - c3 - c4 - c5 >  = y + c6..., accommodating this expression we have S - c1 - c2 - x - y >  = c3 - c4 - c5 - c6... and also choosing y before will not add another coin between y and c3, because the sum at that point is even greater. With this we proved that the set of coins will be the same giving him x+y or (x and y).

You can simply simulate the process. Limak will always try to disqualify the team which has higher number of balloons than him and which can be disqualified with the least cost (cost = weight_of_team — no_of_balloons + 1). Put all the teams with more balloons than Limak's team in a priority queue and keep disqualifying the best choice. When you disqualify a team, the count of Limak's balloons decreases so you may need to push more teams in the priority queue (this can easily be done by maintaining a global sorted list of teams based on non-increasing order of total initial balloons, and you simply need to pop from the back). Do this process until no more teams can be disqualified. The final ans is 1 + minimum size of priority queue during all these steps. I used binary search in my code but it is not needed.

Here are the optimal moves, I will leave the task why is this optimal to you.

Test1: Alice takes [1,4], Bonnie takes [3,1]

Test2: Alice takes [4], Bonnie takes [0], stack one remains untouched.

Test3: Alice takes [0], Bonnie takes [10].

In the a > d case, this is equivalent to deleting the photo and adding a - d to the final answer. Probably I should have written that in the editorial instead as it would be clearer. The method of substituting a different photo just results in slightly shorter code.