aajjbb's blog

The Minima Game
By aajjbb, 11 years ago, In English

Hello, I'm trying to solve this problem from Polish Olympiad of Informatics Link. The problem seems to be straight forward, but I'm not able to figure out the optimal strategy. Currently, I think the optimal strategy is to always let Alice to take only the biggest card, an then, Bob take all the other cards, this, due to the first example which seems that points are not cumulative. Do you have any other clue to the 'optimal' strategy ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

When Bobs win?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    There's no 'win or loose' the optimal strategy is to maximize the difference between their points.

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

I think we need to first sort the array and then Alice takes the biggest number and all numbers equal to it. Then Bob takes second biggest number and all numbers equal to it and so on until last number..

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    well, on 3 2 board you should get both cards

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

      Well, the first example seems a little bit weird. Thinking about optimal strategies, as there's no restriction to the number of cards a player can pick, start picking all cards seems always better, for the first example, Alice should pick 1 + 3 + 1 to get a difference of (5 — 0) which is higher than 2, also, pick 1 + 3 and leave 1 to Bob is higher than 2. Your idea explained below gives this outcomes for the first example.

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

        if we will get 1 + 3 + 1 difference will be 1 — 0. Shouldn't you reread rules?

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

It seems to be true that it's always better to take number out max cards. Ok let's sort in asc order, we always need to take suffix. let dp[n] id answer on prefix. Then dp[n] = max_{i<=n}{a[i]-dp [i-1]}. Let's calculate it for every i from 1 to n. It could be done using segment tree

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

    Sorry but I yet can't understand your dp recurrence.

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

      How many points we will win if we will get cards a[i], a[i + 1], a[i + 2], a[n] ?

      First we'll get a[i] because array is sorted, and than opponent will win dp[i - 1] (it's already calculated). We need to choose maximum.

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

    Do you see any segment tree in my solution, which got accepted :D?

    http://pastebin.com/TyCyK9b4

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

      Well, we can calculate maximum "a bit" easier :)

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      What's behind this '2 * w' trick ?

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

        It's exactly the same what AlexDmitriev said few post above, but slightly different written. I should have written w = max(w, tab[i] — w);

        → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Excuse me, maybe I misunderstood the problem or your solution, but in this case:

    7

    1000 500 499 100 99 10 9

    if Alice and Bob choose maximum number, then Alice get 1000 + 499 + 99 + 9 = 1607 and Bob get 500 + 100 + 10 = 610 point and the difference would be 997, but Because the both Alice and Bob play optimally, after Alice chose 1000 Bob should choose 500 and 499 then Alice should choose 100 and 99 and finally Bob choose 10 and 9 then the difference would be 591.

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

      Maybe I didn't write it clear enough, but I mean one should take some cards (1 or more) so that if he take cards with number x, he also take all cards with numbers greater than x

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks so much for spending time to explain your solution for me.

        → Reply