I'm trying to solve problem D.Greedy Game from the SPb SU and SPb AU Contest of Pertozavodsk Winter Training Camp 2016.
Here are the problem statements.
I already searched for any solutions on the internet, I only found this.
The problem with it is that it's in chinese, the translation isn't understandable and I couldn't understand the code.
So can you give me some hints?
What I found so far is that to find the maximal possible sum of values taken by the second player that he can guarantee regardless of the first player’s moves we just have to find the maximal possible sum of values that the second player can take if the first player, when confronted by many items of the same biggest value Ai, picks the one with the biggest Bi value first.
Since that would be the worst case for the second player.
Otherwise all of the approaches I've found are O(n2) ..
Any help is appreciated.