GLAYS's blog

Stuck on "Greedy Game" from Petrozavodsk Camp 2016
By GLAYS, 6 years ago, In English

Hello!

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.

Thanks!

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Sort and greedy

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

This problem is equivalent to what Errichto explained in his lecture at minute 29:35 or so. The only diference is that you first sort the array by biggest ai, and break ties by biggest bi (just like you mentioned in your post). Now you know how much each item is worth for you, and you know that the opponent will take always the leftmost item in his turn.

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks to VLamarca I now solved it after watching Errichto's video lectures(part 1 and 2) on the "Exchange Argument" technique, although I'm not sure if this method too can fall inside that technique since it's different from the other problems he solved in his stream.

Here is his blog about it, this exact trick is explained in the 6th problem there, in the part 2 video.

Solution.

→ Reply