CLGAME - Editorial

editorial
, , , ,
1

PROBLEM LINK

Practice
Contest

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

2^x = 1 + \sum_{i=0}^{x-1} 2^i

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

f(i) = \begin{cases} 0 & \text{if } i > m \text{ or all } f(i + x_j) = 1 \text{ for } x_j \in S \\ 1 & \text{else} \end{cases}

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.

5 Likes
2

Can anyone help me figure out why my submission(https://www.codechef.com/viewsolution/23249720 ) gives TLE?

3

if(n == 1){
cout<<“Chef\n”;
continue;
}

This should be done after taking the whole input of that test case.

https://www.codechef.com/viewsolution/23250331 Here is your AC code. Silly error, I know. :frowning:

1 Like
4

Yaa you are right. Thanks :slight_smile:

1 Like
5

awesome problem

6

Can someone explain what do you mean by the state of the stack? I’m not able to figure out the explanation.

7

State of the stack refers to what the stack looks like at any point in the game. The state of the stack can be described by just one integer, the number of discs remaining in the stack.

8

This Code is giving wrong answer. Can anybody help?

9

@joker70 you should check if you can remove exactly s[i] discs or not inside your solve() function.

10

@nilesh, I didn’t get your answer. Can you give me a test case?

11

pls someone check [This code]!

12

As @nilesh8757 said, you cannot remove more discs than what remains on the stack.

13

t=int(input())

while(t>0):

num,d=input().split()

a=list(map(int,num))

mi=min(a)

d=int(d)



l=len(a)

l1=l

if mi < d:

    last=l - a[::-1].index(mi)-1

    c=0

    while(last < l):

        

        cmi=a.count(mi)

        for k in range(cmi):

            print(mi,end='')

            c=c+1

        if(last == l-1):

            break

        a =a[last+1 :]

        mi=min(a)

        if(mi >=d):

            break;

        l=len(a)   

        last=l - a[::-1].index(mi)-1

        

    while c< l1:

        print(d,end='')

        c=c+1

    

else:

    for i  in range(l1):

        print(d,end='')

print()    

t=t-1
14

t=int(input())

while(t>0):

num,d=input().split()

a=list(map(int,num))

mi=min(a)

d=int(d)



l=len(a)

l1=l

if mi < d:

    last=l - a[::-1].index(mi)-1

    c=0

    while(last < l):

        

        cmi=a.count(mi)

        for k in range(cmi):

            print(mi,end='')

            c=c+1

        if(last == l-1):

            break

        a =a[last+1 :]

        mi=min(a)

        if(mi >=d):

            break;

        l=len(a)   

        last=l - a[::-1].index(mi)-1

        

    while c< l1:

        print(d,end='')

        c=c+1

    

else:

    for i  in range(l1):

        print(d,end='')

print()    

t=t-1
15

Thuis is a sentence just for testing.

16

Thsiu is sentenct to test the reply feature.

17

Nice editorial man! great work