ASTRGAME - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This game is a modification to the game of Kayles. Like other impartial games, this problem can be solved using Sprague-Grundy theorem.

Let’s define a game as a substring of S. For convenience, we refer to a substring by its left and right index S(i, j). Note that after a player erases a substring S(a, b), in S(i, j), the game is split into two subgames, S(i, a-1) and S(b+1, j). Because a player can choose any game in his/her turn, the Grundy number of the game is simply the XOR of the Grundy numbers of the two subgames.

Let G(i, j) be the Grundy number of the substring S(i, j). Then G(i, j) = mex({G(i, a-1) XOR G(b+1, j) : S(a, b) exists in the dictionary and is a substring of S(i, j)}

A game is losing iff its Grundy number is zero. So, Teddy, the first player, will win if G(1, |S|) is not zero. On the other hand, Tracy will win if G(1, |S|) is zero.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

for complete noobs like me, this might help a bit http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames

“both players play optimally”… what does optimally mean here… delete the shortest word in the dictionary first or the longest or some thing else ?

It means playing in the way that makes them win.

I’ve created a tutorial for this problem.

2 Likes

Link of setter and tester solution is not working

1 Like

Interesting to work out how for say “fearchoparchfearchop” and a dictionary of (“fear”, “chop”, “arch”) the starting player needs to take the middle instance of “arch” (of the 3 available) to win.

I don’t see this problem as “Easy”. Needs a bit of structure and theory. Can you explain why the XOR operation works?

Some accepted submissions fail to find Teddy’s winning first move when reducing PAWPAWPAWPAW by the one-word dictionary PAWPAW. I doubt that would be hard to fix for them though, once pointed out.

https://www.codechef.com/viewsolution/19971456

My solution works for all testcases that i can think . But still I get a wrong answer.Please help…