# PROBLEM LINK

**Author:** Sarthak Manna

**Tester and Editorialist:** Soumik Sarkar

# DIFFICULTY

Easy

# PREREQUISITES

Observation, dynamic programming

# PROBLEM

A stack contains n discs, each with a distinct number A_i. A set of moves S exists. Two players take alternate turns removing discs from the stack, the number of discs removed must equal some element in set S. Removing disc i adds 2^{A_i} to the player’s score. Determine who has the larger score if both play optimally.

# EXPLANATION

Since all A_i are distinct, you can observe that only the disc with maximum A_i matters, let this be for i = m.

It is known that

So, even if the other player gathers all discs except disc m, he will have a lesser sum than A_m. The game always ends in favor of the one who gets disc m, there are no ties.

Since each state of the stack is either a winning or losing state, dynamic programming can be used to calculate who wins. If it is possible to get to any losing state from the current state, the current state is a winning state. The converse is also true, if the current state only leads to winning states, it is a losing state. All states from which it is not possible to get disc m is a losing state.

Let f(i) = 1 if the stack state with i discs remaining is a winning state and 0 otherwise. Then

The time complexity is \mathcal{O}(NK).

# AUTHOR’S AND TESTER’S SOLUTIONS

Author’s solution can be found here.

Tester’s solution can be found here.