Why do you think remaining total is not required as DP states?


  • 0
    H

    Hi, I came up with straightforward DP solution as below, but it obviously violates the time and memory limitation. A different point to you is that my DP solution includes "remaining total" as states. The solution seems to be correct, although the time and space complexity of the solution is bad. At least, I compared some cases to other "right" solutions.

    I still don't understand why you think you can eliminate "remaining total" from DP states?
    For example,
    (1) you can use 2, 3, 4 as a number, and remaining total is 4. The state is winning (by using 4)
    (2) you can use 2, 3, 4 as a number, and remaining total is 5. The state is losing, because whatever number you use, the opponent can win using any remaining number.
    So winning-losing state is dependent to remaining total.

    I hope your answer, thank you!

    #include <bits/stdc++.h>
    using namespace std;
    
    #define ZERO(a) memset(a,0,sizeof(a))
    
    bool used[1<<20][301];
    bool dp[1<<20][301];
    class Solution {
        public:
            int max_m;
            bool dfs(int mask, int d) {
                if (d <= 0) return 0;
                if (used[mask][d]) {
                    return dp[mask][d];
                }
                used[mask][d] = 1;
    
                for (int i = 0; i < max_m; i++) if ((mask & (1 << i)) == 0) {
                    if (d <= i + 1) {
                        return dp[mask][d] = 1;
                    }
                }
                int f = 0;
                for (int i = 0; i < max_m; i++) if ((mask & (1 << i)) == 0) {
                    f |= !dfs(mask | (1 << i), d - (i + 1));
                }
                return dp[mask][d] = f;
            }
            bool canIWin(int m, int d) { // m <= 20, d <= 300
                ZERO(used), ZERO(dp);
                if (d == 0) return 1;
                max_m = m;
                return dfs(0, d);
            }
    };
    

  • 0
    M

    @hamko Your code seems to return d = initial d ー Sum i + 1 (for mask&(1<< i) > 0), so d only depends on mask and initial d.(I only read your code and haven't solved this problem)


  • 0
    H

    @maruoka Ah! You are totally right, thank you!


  • 0
    H

    @hamko

    I could beat 95.31% C++ submission by fixing my code according to your comment!

    #include <bits/stdc++.h>
    using namespace std;
    
    #define rep(i,n) for(char i = 0; i < (char)(n); i++)
    
    int max_m;
    int8_t dp[1<<20];
    class Solution {
        public:
            bool dfs(int32_t mask, int16_t d) {
                if (d <= 0) return 0;
                if (dp[mask] != -1) return dp[mask];
                rep(i, max_m) if ((mask & (1 << i)) == 0)
                    if (d <= i + 1 || !dfs(mask | (1 << i), d - (i + 1)))
                        return dp[mask] = 1;
                return dp[mask] = 0;
            }
            bool canIWin(int m, int d) { // m <= 20, d <= 300
                max_m = m;
                if (d == 0) return 1;
                if (m * (m + 1) / 2 < d) return 0;
                memset(dp, -1, sizeof(dp));
    
                return dfs(0, d);
            }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.