Java | with picture: Optimal solution vs. simulation w/memoization
Providing two solutions - the first one requiring specific insight into the game rules, while the second is a full simulation of game steps with memoization.\n\
Providing two solutions - the first one requiring specific insight into the game rules, while the second is a full simulation of game steps with memoization.\n\n**1. Optimal solution**\nWe count the numbers with respect to modulo 3 in O(N), based on that we know the outcome in O(1).\nSee picture to gain intuition:\n- only parity of the count of 0 (mod 3) matters\n- problem is symmetric with respect to 1 (mod 3)  and 2 (mod 3) numbers, so consider only count 1 >= count 2\n- Alice needs three 1\'s to form a full cycle 0 -> 1 -> 2 -> 0, on Bob\'s turn\n- consider two cases: a. count 2 == 0 and b. count 2 > 0  \n```\npublic boolean stoneGameIX(int[] stones) {\n        int[] f= new int[3];\n        for(int s:stones) ++f[s%3];\n        // each pair of numbers divisible by 3 cancel each other out, so only parity count of such numbers matters\n\t\tf[0]%= 2;  \n        // assert f1>=f2, as problem is symmetric wrt. 1 and 2 (see picture below)\n        if(f[2]>f[1]) { int t= f[1]; f[1]= f[2]; f[2]= t;}\n\t\t// Alice wins only if sum (mod 3) comes back to 0 on Bob\'s turn, that is:\n\t\t// a) when there are no 2\'s, Alice needs (an unmatched) break (0 = num divisible by 3) and count of 1\'s of at least 3, or\n\t\t// b) when there are 2\'s (at most as many as 1\'s), she wins when Bob can\'t take (an unmatched) break (Alice plays 2 first in such case) \n\t\t//     or the count of 1\'s unmatched by 2\'s is at least 3 (Alice plays 1 first)\n        return f[2]==0 ? f[0]==1 && f[1]>=3 : f[0]==0 || f[1]-f[2]>=3;\n    }\n```\t\n![image](https://assets.leetcode.com/users/images/604f8a86-b041-4c09-a873-f7ca452640fe_1633273530.0525293.png)\n\n**2. Game simulation with memoization**\nWe still need the basic piece of insight to avoid TLE - ignoring all but one (if the count f[0] is odd) numbers divisible by 3:  f[0]%= 2;\n```\nclass Solution {\n    static int A= 0, B= 1;\n    public boolean stoneGameIX(int[] stones) {\n        int[] f= new int[3];\n        for(int s:stones) ++f[s%3];\n        f[0]%= 2;\n        Map<Long, Boolean> memo= new HashMap<>();\n        return f[1]>0 && sim(B, 1, f[0], f[1]-1, f[2], memo) || f[2]>0 && sim(B, 2, f[0], f[1], f[2]-1, memo);\n    }\n    \n    long key(int AB, int sum, int f0, int f1, int f2){\n        return (((AB*10+sum)*10+f0)*100000+f1)*100000+f2;\n    }\n\n    boolean sim(int AB, int sum, int f0, int f1, int f2, Map<Long, Boolean> memo){\n        if(sum==0) return AB==A;\n        if(f0==0 && f1==0 && f2==0) return false;\n        \n\t\tlong memoKey= key(AB, sum, f0, f1, f2);\n        Boolean memoAns= memo.get(memoKey);\n        if(memoAns!=null) return memoAns;\n        \n\t\tboolean ans= f0>0 && sim(1-AB, sum, f0-1, f1, f2, memo)\n            // playing optimally, we don\'t play 1 unless sum!=2 or there is no other numbers (0 or 2) to play\n            || (sum!=2 || f0==0 && f2==0) && f1>0 && sim(1-AB, (sum+1)%3, f0, f1-1, f2, memo)\n            //  playing optimally, we don\'t play 2 unless sum!=1 or there is no other numbers (0 or 1) to play\n            || (sum!=1 || f0==0 && f1==0) && f2>0 && sim(1-AB, (sum+2)%3, f0, f1, f2-1, memo);\n        \n\t\tmemo.put(memoKey, ans);\n        return ans;\n    }\n}\n```
[]