DFS Thought Process
We need to count remainders of mod 3 instead of working with input numbers directly. \n\nHaving those counts, we could come up with some formula, but I could no
We need to count remainders of `mod 3` instead of working with input numbers directly. \n\nHaving those counts, we could come up with some formula, but I could not see it at that time. \n\nSo instead, I went for a generic DFS approach. We start with the counts of numbers with remainders 0, 1, and 2, and track the remainder of the removed stones in `r`.\n- If the remainder `r` is zero (divisible by 3), the current players win so the player who made the last turn loses.\n- If we run out of stones, Bob wins - we need to track who\'s turn it is (`isAlice`).\n- Otherwise, we see if picking 0, 1 or 2 remainder would give us a win.\n\nThis approach initially gave me TLE, and then I realized that, if Alice picks `3`, and Bob responds by picking `6`, it does not affect the remainder of the removed pile. So we should only care whether the count of numbers with `mod 3 == 0` is even or odd. That was sufficient to get this solution AC.\n\n**C++**\n```cpp\nbool dfs(int r0, int r1, int r2, int r, bool isAlice) {\n    if (r == 0 || r0 < 0 || r1 < 0 || r2 < 0)\n        return true;\n    if (r0 == 0 && r1 == 0 && r2 == 0)\n        return !isAlice;\n    return !dfs(r0 - 1, r1, r2, r, !isAlice) \n        || !dfs(r0, r1 - 1, r2, (r + 1) % 3, !isAlice) \n        || !dfs(r0, r1, r2 - 1, (r + 2) % 3, !isAlice);\n}\nbool stoneGameIX(vector<int>& stones) {\n    int r[3] = {};\n    for (auto s : stones)\n        ++r[s % 3];\n    return dfs(r[0] % 2, r[1], r[2], 3, true);\n}\n```\n**Update**\nYou can still get TLE because the count of `r1` and `r2` could be hight. Using the same logic as we did for `r0`, players can keep picking `1` after `2`, and get the same remainder. So, we can reduce both counts by the minimum of two.\n\n```cpp\nbool stoneGameIX(vector<int>& stones) {\n    int r[3] = {};\n    for (auto s : stones)\n        ++r[s % 3];\n    int min12 = min(r[1], r[2]) - (min(r[1], r[2]) == 0 ? 0 : 1) ;\n    return dfs(r[0] % 2, r[1] - min12, r[2] - min12, 3, true);\n}\n```
[]