PROBLEM LINK:
Setter-
Tester-
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY-MEDIUM
PRE-REQUISITES:
Game Theory, Grundy Numbers, Sprague Grundy Theorem
RESOURCES:
Before reading the editorial, you MUST have an idea of the pre-requisites involved in order to make sense of what is being done.Hence, in case you are not well versed with the pre-requisites, I recommend that you first learn the pre-requisites from the sites below-
Grundy Numbers- GFG - Please pay close attention to calculation of grundy number for normal Nim.
Sprague Grundy Theorem - Pay some attention to definition and application.
This answer which beautifully deals with Grundy numbers and how to apply them.
This tutorial at Hackerrank in the end.
With this knowledge, now you are more than capable of understanding and appreciating what the editorial will convey to you.
PROBLEM:
It is nothing but a standard Game Theory problem where we need to find winner from initial conditions, assuming both play optimally.
QUICK EXPLANATION:
On careful observation we see that this bracket game is nothing but Nim game with possibly multiple piles. We know that for a game of nim, the Grundy Number is xor of coins in all piles. We hence “convert” the given bracket sequence equivalent piles of coins and proceed to find Grundy Number. If its non-zero, first player (i.e. ATM) wins, else he loses.
EXPLANATION:
So, we are given a valid bracket string, and are told that each player can remove any valid, non-empty sub-string per turn. How do we proceed to find the winner?
The very first instinct which any contestant gets when he encounters a game theory question is to make observations and hence try to find condition which leads to first player winning. But that is just one type of Game Theory question, and the same strategy isn’t applicable here.
If you’ve gone through the resources, you will appreciate that we cannot determine winner in Game of Nim without Grundy numbers. There are simply too many factors, depending solely on observations to determine winning conditions is more or less likely to miss out on something. This is the category of questions where we need to focus on and appreciate the mathematical concepts of Game Theory.
Of course, we have to make some observations at the end of the day. But those observations have a different direction. You will see when you read below.
With above, I hope its clear that why the approach of finding winning conditions by pure observations is not going to work.
First Step towards finding the winner-
Recall the Sprague Grundy Theorem. It states that-
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber.
-wikipedia
So the first step towards solving this is seeing if we can reduce this game to game of nim or not. And if yes, then how?
Converting the game to nim-
So, at first sight it kind of sounds hard. Like, we are given a bracket sequence, and somehow we have to look if we can reduce it to nim or not. But soon you will see, that mere 3 observations and their proper application allow us to easily convert this bracket game to game of nim!
Firstly, let me will categorize brackets into 3 types, for convenience during later explanation-
- Simple
()valid sequence with no other sequence inside it. - A bracket sequence with valid sequence inside it. The valid sequence inside it is NOT concatenation of 2 valid sequences. Eg-
(())or((())). Here, we face no restriction while removing brackets/sequence and can remove any sequence as we wish in a single turn. - A bracket sequence with valid sequence inside it. The valid sequence inside it is concatenation of 2 or more valid sub-sequences. Eg-
(()())or(()()(())). In this case there are some restrictions while removing brackets, eg- We cannot remove()()(())in a single turn.
Now, lets start with the first type of sequence. Lets take and analyse the following exemplar sequences-
-
()- Here we have only 1 bracket sequence, and the only option is to remove it. Just like removing a coin from single pile of Nim! But well, only 1 case doesnt take us anywhere! -
()()- Here we can remove either the first()or second()(in a single turn) but not both. Hmm, its the same situation as if we have 2 piles with 1 coin in each in game of nim! -
()()()- Again, same restriction as above. we can remove exactly 1 of them per turn. It seems so similar to a game of nim with 3 piles of 1 coins!
Observation 1-
The observation to make is that, if we have a sequence of N () brackets concatenated together, its equivalent to N piles with 1 coin in game of nim.
What happens if we add Type 2 brackets as well?
-
(())- Here, we can either remove inner sequence, or outer sequence. Rephrasing that, we can either remove 1 or 2 valid sequences. Following the direction of previous directions, it seems similar to removing coins from a single pile of 2 coins in nim. -
((()))- Again, we can remove 1, 2 or 3 bracket sequences. Exactly same as removing coins from a single pile of 3 coins in nimber. -
(())((()))- As discussed above, it is equivalent to 2 piles of coins with 2,3 coins in them respectively.
Observation 2-
The second observation to make was that, for a single sequence of type 2, which has a total of N valid sequences, then it is equivalent to a single pile with N coins in game of nim. Concatenation of multiple type 2 sequences is equivalent to multiple piles.
Till now, things have been going very easy. We have seen equivalence of type 1 and type 2 bracket sequences with game of nim with some trivial observations. But you will see that things will not be not so comfortable when dealing with type 3 bracket sequence. Why? One may wonder whats so special in it.
Hence, I request the readers to give a try in finding equivalence of type 3 sequence with game of nim. Everyone wants to be a good coder and top the leaderboard. You can do it only when you train yourself to think like them during the contest. Hence, I urge you all to give it a try. The third observation is nothing new. It is just a combination of first and second observation, provided you went through the resources I posted. Hence, I sincerely request to try reducing the third to equivalent game of nim by yourselves first so that you get more involved into the problem and its solution.
Equivalence of Type 3 Brackets with Nim-
.
.
.
.
.
.
.
.
.
Left as an exercise for Reader 
.
.
.
.
(PS: The above line is a joke. The detailed explanation is given below 
)
(PPS: Another observation you can make is that you can never predict whats coming next in my editorial. Is it a detailed explanation? A joke? A flying dinosaur meme? You never know! XD )
If you guys did give a shot in converting third type of brackets to equivalent of nim, you guys would see whats the problem we’re facing. What most of you must have faced is, problem in finding the number of coins in a pile when converting bracket sequence to equivalent nimber game. For type 1 and type 2, it was quite easy to observe. But type 3, we are stuck. Indeed, its not so straightforward to convert (()()(())) into a pile of coins. This is what gives this question a bit of medium difficulty.
As a hint, we will be using the fact that in a game of nim, Grundy number of a pile with N stones is N (The derivation is given in the first link in resources section. So please check it out or have a relook if you need to!)
For now, remove/ignore the outer brackets from (()()(())). So we are left with ()()(()) . We can easily see that its equivalent to a nim game with piles 1 1 2 . We can easily calculate the equivalent Grundy number of this combination. Its 1^1^2=2.
Now comes my favorite part…
We know that in nim, a Grundy number for a pile with N coins is N. We also see that sequence ()()(()) has grundy number of 2. Grundy number of a pile with 2 coins, is also 2. Does this not mean that this combination is having the same effect on game as a single pile with 2 coins? At the end of day we have to find answer by xoring all Grundy numbers. The combination, ordering etc. doesnt matter once we get the Grundy numbers.
So can I not conclude that the sequence ()()(()) has same effect on game as a sequence (()) since both have same Grundy numbers? I can, and this allows me to replace ()()(()) with (()) and have no effect on answer!
Now, we had initially ignored the outer brackets, its time to bring them in! Our original sequence of (()()(())) can be converted to ((())). We can easily find equivalent of this in nim! (In fact we already did that :p) Our final answer is 1+Grundy_Number of inner brackets
Similarly, another example-
In (((()()()((()))))) after peeling off all outer brackets of type 2, we get ()()()((())) , we can again replace this by (()) (Grundy number is 1^1^1^3=1^3=2) and convert it to ((((())))). Here the answer is Grundy number of inner brackets +1+1+1 We are adding 1s equal to number of outer brackets of type 2 which we ignored. Why I wrote it as +1+1+1 instead of +3 will be clear if you see my Recursive solution.
Now we have logic clear, we can discuss the implementation. I have discussed the implementation as comment in my solution, so that the editorial doesnt become verbose. In case you people specifically want more explanation, please comment and I will add it accordingly 
EDITORIALIST’S SOLUTION:
TimeComplexity=O(N)
CHEF VIJJU’S CORNER
Although I have discussed the question in great detail, I made sure to keep some delicious lip smacking mysteries for you guys.
1.Go through the time taken by my recursive and iterative solution. Recursive works in 0.08 while iterative takes 0.52 seconds! Points for anyone coming up with the correct explanation :D.
2.I have said in recursive solution that dont pass string to function as an argument? Why? Well, check out this solution of mine. Its exactly same as the one I gave under Editorialist’s solution, except that here I passed string as an argument and got TLE. This is a very common implementation error we see. Strings are not passed by reference, they are passed by value. This means, for EVERY call of function, entire string is copied again and again. It takes O(N) to copy the string for each function call. And function is called for O(N) times in worst case. So it actually a becomes O({N}^{2}) time complexity!!
3.Now that you have read the editorial and (hopefully) gone through the resources and acquired the required knowledge on game theory, I am sure you all want some questions to strengthen this new found knowledge! There is a good section of problems related to Game Theory here . You can practice all you want there.
4.There are some conceptual questions to feed your brain as well. Give a try at the questions below-
a. The X and the Y axis form four quadrants. I have one coin placed in second quadrant at (-N,M). The graph is infinite. The players can move coins either vertically down or horizontally right. First player to bring coin at origin wins. If player A plays first, what is the condition that he will win?
b. In a game of nim, I have put a restriction that a player can remove only 3,4 or 5 coins. Determine the Grundy numbers for upto N=20. Assume number of pile to be a) 1, b)2 , c)N [Hint: Extend conclusion of base/smaller cases!]
5.There is a 1 liner iterative solution to this problem as well! Just 1 statement inside the for loop. Feeling upto the challenge?
.
.
.
.
Answers of questions above
Left as an exercise to you guys! Seriously! I made sure that if you went through resources, you dont get stuck. Leaving these as open ended questions, anyone answering questions decently gets 10 points :D. (25 if you answer both decently 
)
I will update this section later with best selected answers :).
FURTHER READING ON GAME THEORY:
This paper is beautiful when dealing with Game theory.