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 ?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
23:36:28
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
23:36:28
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 17:58:33 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
When Bobs win?
There's no 'win or loose' the optimal strategy is to maximize the difference between their points.
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..
well, on 3 2 board you should get both cards
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.
if we will get 1 + 3 + 1 difference will be 1 — 0. Shouldn't you reread rules?
Damn!
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
Sorry but I yet can't understand your dp recurrence.
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 windp[i - 1](it's already calculated). We need to choose maximum.Do you see any segment tree in my solution, which got accepted :D?
http://pastebin.com/TyCyK9b4
Well, we can calculate maximum "a bit" easier :)
What's behind this '2 * w' trick ?
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);
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.
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 thanxThanks so much for spending time to explain your solution for me.