Wrong constraints in Cook-a-Code (MODME)

1

Problem link: CodeChef: Practical coding for everyone

Solution 1 link (WA): CodeChef: Practical coding for everyone
Solution 2 link (AC): CodeChef: Practical coding for everyone

Both the codes will output the same value for any input for the given constraints.

The only difference is:

if n <= m:
    print('A')
    continue

Which is supposed to work absolutely fine as if N ≤ M, player A can choose N from the range 1 to M.

This will only fail in the case N ≤ 0 but constraints clearly say 1 ≤ N ≤ 10^{18}.

My friend @sarthakmanna submitted this and got NZEC.

What he did is pretty simple: 7 / 0 will raise ZeroDivisionError and will only be called if n == 0

:frowning_face:

2 Likes
2

Already discussed here, though I haven’t seen any plans for dealing with the fallout from it :frowning:

3 Likes
3

I see :sob:

2 Likes
4

I’m unable to understand first test case with N =4, M=2.
Lets say, A will start the game with 0, now he can add any number from 1 to M. Lets say A added 2 to 0, shouts 2 and pass 2 to B.
B can add any number from 1 to M. B adds 2 to 2, resulting it in 4. He shouts 4 which is actually N. So, B must be the winner ?
And many other scenario is possible.

5

The starting value is 0.

If N = 1, the first player can add 1 and win the game.
If N = 2, the first player can add 2 and win the game.

If N = 3, the first player can add 1 or 2:
If he adds 1: The second player can add 2
If he adds 2: The second player can add 1

If N = 4, the first player will add 1

The second player can add 1 or 2:
If he adds 1: The first player can add 2
If he adds 2: The first player can add 1

Therefore, the first player will always win

1 Like
6

This is called game theory.

For N = 10 and M = 5

image
image.png731×189 4.18 KB

Player A can win for 1, 2, 3, 4.

For 5 though, no matter what player A does, player B can capture 5.

But for 6, player A can go to 1. Now, if we calculate all possibilities of player B, it’ll be in the range 2 to 5. Now, A can add 6 minus the value B selected.

For 7, A will start at 2, then B's range would be from 3 to 6. A can add 7 minus the value B selected.

Same for 8, 9.

But for 10, B will win as B will just capture 5 after what A plays. Then A has to select a value from 6 to 9. B will just add 10 minus what A selects.

Same for all other values.

If N % (M + 1) = 0, B wins. Else A.

1 Like
7

If N=4, the first player will add 1

Here, why first player can’t add 2 ? Since it’s written he will add any number from 1 to M, and M being 2. The first 3 case is clear to me.

8

If the first player adds 2, then the second player will also add 2, winning the game.

1 Like
9

Ok, thanks, got it! Point here was A is always trying to win the game and starting first, A has an advantage. I was simply lost in case where why B can’t be a winner, neglecting the normal human behavior of winning if possible.

10

:+1:t4:

The problem also mentions “If both players play optimally”

1 Like