Difficult Game Of String

Limits: 1s, 512 MB

Today we will talk about two friends and a difficult game. For this problem, let’s think their names are Mahir and Arnab. Mahir loves his home a lot. So much that if anyone asks him for suggestion to do anything he replies with his legendary dialogue, “Come to my home and we will think about it.”. Whether you ask him about how to go to abroad or how to kill cockroach or what is the mass of the sun, he will reply the same “Come to my home and we will think about it.”. Arnab loves to solve difficult problems a lot. Today he is feeling bored. He wants to play a game which is obviously related to a difficult problem. So an idea hits his mind. Knowing Mahir’s unique characteristic, Arnab calls him and asks whether he can play a game. And BINGO! Mahir falls in the trap! He says, “Come to my home and we will think about it.”. Now as Arnab is in Mahir’s home, Mahir cannot refuse to play. So let’s go to the description of the difficult game we are talking about. In the beginning of the game, there will be N strings. On each turn a player chooses any random string R and performs reduce on all string in the list that has R as a prefix. The player who is left with no string to perform reduce on, loses the game. What is reduce? Well it’s an operation that removes characters from last from selected string till it has R as its prefix. (Example: Given string “abcba” if anyone chooses “abc” then given string becomes “ab”. If anyone chooses “abcb” the given string becomes “abc”. If anyone chooses “a” then given string becomes empty). Remember, Arnab gives the first move and both player play optimally to win the game. No player can choose a string that doesn’t let him perform reduce. (Example: For string ‘abc’, ‘def’, ‘ghi’ he cannot choose ‘xyz’ as it isn’t present as prefix of any of the given strings.)

This is a companion discussion topic for the original entry at https://toph.co/p/difficult-game-of-string