[C++] DFS + Memorization
The min and max round for the two player to meet is determined by the state [n, firstPlayer, secondPlay], where the three number are the number of players, firs
The min and max round for the two player to meet is determined by the state `[n, firstPlayer, secondPlay]`, where the three number are the number of players, first player position and second player position. And for going into next round, we do not need to track the actual player position at the beginning but just their replative position in current round. What we essentially need to is to enumerate the possibilities of the next round state from the current round state. In case of known state, we memorize to dedupe calculation.\n\nComplexity is: O(n^3) (? a guess) for memorization\n\nHere\'s the code\n```\nint memo[29][29][29];\n\nclass Solution {\npublic:    \n    vector<int> earliestAndLatest(int n, int fi, int se) {\n        memset(memo, -1, sizeof(memo));\n        int r1 = dfs(n, fi-1, se-1, true);\n        \n        memset(memo, -1, sizeof(memo));\n        int r2 = dfs(n, fi-1, se-1, false);\n        \n        return {r1 + 1, r2 + 1};\n    }\n    \n    int dfs(int n, int fi, int se, bool find_min) {\n        if (fi + se + 1 == n) return 0;\n        \n        int& res = memo[n][fi][se];\n        if (res != -1) return res;\n        \n\t\t// use to determine if the player is on the left or right\n        int lfi = min(fi, n - fi - 1);\n        int rfi = max(fi, n - fi - 1);\n        int lse = min(se, n - se - 1);\n        int rse = max(se, n - se - 1);\n        \n        int tmp = find_min ? INT_MAX : 0;\n        int m = n / 2;\n\t\t// enumerate all possibilities\n        for (int i = 0; i < pow(2, m); ++i) {\n            // simulate\n            // calculate decrease in pos\n            int dfi = 0, dse = 0;\n            for (int j = 0; j < m; ++j) {\n                // determine winner from enumeration\n                bool rightWin = (((i >> j) & 1) == 1);\n                \n                // overwrite winner if it\'s one of the players\n                if (j == lfi) rightWin = fi == rfi;\n                else if (j == lse) rightWin = se == rse;\n                \n                if (rightWin) {\n                    // right side win\n                    remove(j, fi, se, dfi, dse);\n                } else {\n                    // left side win\n                    remove(n - j - 1, fi, se, dfi, dse);\n                }\n            }\n            \n            if (find_min) tmp = min(tmp, 1 + dfs(m + n % 2, fi + dfi, se + dse, find_min));\n            else tmp = max(tmp, 1 + dfs(m + n % 2, fi + dfi, se + dse, find_min));\n        }\n        \n        return res = tmp;\n    }\n    \n    void remove(int j, int fi, int se, int& dfi, int& dse) {\n        if (j < fi) dfi--;\n        if (j < se) dse--;\n    }\n};\n```
[]