Alice and Bob
So many of these problems…
Sometimes simple, sometimes DP, sometimes the really hard game theory stuff.
Problems
Number Game https://codeforces.com/contest/1749/problem/C
- Here, it seems like the optimal thing to do would be for Bob to just greedily do things. And in my head, I had convinced myself that greedy is optimal.
- my rough proof was the following:
- Assume by contradiction that bob increases by for a smaller value, which results in a lower score than choosing the greater value (the greedy strategy). And that smaller value contributes more to hurting alice’s score. But doing it to the greater score would contribute equally or more. Contradiction.
- But this proof is only correct if all values are unique. But that is not the case here…
- All values here are not unique. So BOB choosing the greater value can be “wasted” time, whereas he can focus on the lower thing
- After reading editorial: WTF, you can just take the smallest value?? How does that work?? I’m so confused.
- yea, i think im just tired, getting problems confused with other problems