Hello,
I am trying to solve this problem . But I didn't get the combinatorics used in this solution .How did he conclude that there are (n+1)! states in total?. Also explain me this part:
After checking this game more accurately I can say that the longest path in the state-graph for n = 10 has length 106, so it is enough to do 106 fights, but solutions that did about 40 millions also passed.
Thank you!
The answer to your question is clearly given in the editorial... and i am quoting...
Cards can be arranged in any one of n! ways. In every of this combination, we must separate first soldier's cards from the second one's. We can separate it in n + 1 places (because we can count the before and after deck case too).
You can check it gives you all possible deck configuration. Also you can derive it Combinatorially,
Idea: take k (..nCk),in one hand and permute (*k!)... and permute in the other hand too(*(n-k)!) do this for all k.
ans=sum[0 to n] (nCk*(k!)*(n-k)!).. which gives (n+1)!.
The solution passes because it fits in the TL. you can always over process while you are in TL. 106 comes from observation as not all states will be visited in the game(say winner wins and then loses the next turn repeatedly ending in loop). so that is a potential solution after you get the observation. However it is safer with state visiting solution.