Massive Algorithms: LintCode 394

LintCode 394 - Coins in a Line

There are n coins in a line. Two players take turns to take one or two coins from right side until there are no more coins left. The player who take the last coin wins.

Could you please decide the first play will win or lose?

Example

n = 1, return true.

n = 2, return true.

n = 3, return false.

n = 4, return true.

n = 5, return true.Follow Up Question:

If n is even. Is there any hacky algorithm that can decide whether first player will win or lose in O(1) memory and O(n) time?

This is similar to Coins in a Line II. The only difference is that it's in a 2-d scope.

https://coding-interview-solutions.hackingnote.com/problems/coins-in-a-line.html

    public boolean firstWillWin(int n) {
        if (n % 3 == 0) return false;
        return true;
    }

https://helloyuantechblog.wordpress.com/2016/01/07/lintcode-394-coins-in-a-line-medium/

Finding patterns. When there is 1 or 2 coins, the first player will always win. When there are 3, the second player will always win. When there are 4 or 5, the first play can first take 1 or 2 to make the rest 3, so that the second player will lose. When there are 6, the second player can always transform it to 3, so that he always win. So to generalize, if the coins do not have a factor of 3, the first player will always win.

A more systematic analysis is a top down approach for searching: given n coins, the first play can take either 1 or two, leaving the second player with n-1 or n-2 coins. Then the second player can take 1 or 2, leaving the first player again n-2, n-3 coins (when first player take 1 coin in the first round) or n-3, n-4 coins (when he takes 2). So we can define the problem as given n coins, and the first player is now choosing, whether he can win in the end or not. For him to win, he could either choose 1 or 2, so it is a OR between two situations; no matter what second player chooses, the first player should win, so it is a AND in the secondary level.

The relationship is:

f[n] = (f[n-2] && f[n-3]) || (f[n-3] && f[n-4])

We need to initialize f[0], f[1], f[2] f[3]. The result is then f[n]. This could be optimized using O(1) space.

     bool firstWillWin(int n) {

        // write your code here

        if (n <= 4) {

            return n == 3 || n == 0 ? false : true;

        }

        vector<bool> f(n+1, false);

        f[1] = f[2] = true;

        f[3] = false;

        for(int i = 4; i <= n; i++) {

            f[i] = (f[i-2] && f[i-3]) || (f[i-3] && f[i-4]);

        }

        return f[n];

    }

Space optimization

     bool firstWillWin(int n) {

        // write your code here

        if (n <= 4) {

            return n == 3 || n == 0 ? false : true;

        }

        vector<bool> f(5, false);

        f[1] = f[2] = true;

        f[3] = false;

        for(int i = 4; i <= n; i++) {

            f[i%5] = (f[(i-2)%5] && f[(i-3)%5]) || (f[(i-3)%5] && f[(i-4)%5]);

        }

        return f[n%5];

    }

https://github.com/shawnfan/LintCode/blob/master/Java/Coins%20in%20a%20Line.java
Clarify: '1st play will win' means: if play properly,
1st play will surely have a way to win that 2nd play can't beat.
Make dp[i]: the result when n = i.
fn:
Think back a step, state-1:
When it's play1's turn, there might be 1 or 2 coins left so he can win. so -1, or -2.
THink back a 2nd step, state-2:
Play2 take 1 or 2 to get into state-1. play2 may take 1 or 2 coins. so again, -1 or -2.
So consider i-1, i-2, i-3, or i-4. Note, the next stemp would be for play2, then play1.
However, if left are 1,2 coins for play2, play2 wins; if left are 4 coins, play2 wins; only when left are 3 coins, play2 will surely lose, so play1 win.
Therefore, there is just 1 case to consider: if left are 3 coins, and it's play2's turn, then play1 surely wins.
so fn:
dp[i] = dp[i-3]
Init:
dp[0] = false; dp[1], dp[2] = tru; dp[3] = false;
Result:
dp[n]

public boolean firstWillWin(int n) {
if (n <= 0) {
return false;
}
if (n <= 2) {
return true;
}
boolean[] dp = new boolean[n + 1];
dp[1] = true;
dp[2] = true;
dp[3] = false;
for (int i = 4; i <= n; i++) {
dp[i] = dp[i - 3];
}
return dp[n];
}

http://www.jiuzhang.com/solutions/coins-in-a-line/

    public boolean firstWillWin(int n) {
        // write your code here
        boolean []dp = new boolean[n+1];
        boolean []flag = new boolean[n+1];
        return MemorySearch(n, dp, flag);
    }
    boolean MemorySearch(int i, boolean []dp, boolean []flag) {
        if(flag[i] == true) {
            return dp[i];
        }
        if(i == 0) {
            dp[i] = false;
        } else if(i == 1) {
            dp[i] = true;
        } else if(i == 2) {
            dp[i] = true;
        } else {
            dp[i] = !MemorySearch(i-1, dp, flag) || !MemorySearch(i-2, dp, flag);
        }
        flag[i] =true;
        return dp[i];
    }
}
    /**
     * @param n: an integer
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int n) {
        // write your code here
        int []dp = new int[n+1];
        
        return MemorySearch(n, dp);
        
    }
    boolean MemorySearch(int n, int []dp) { // 0 is empty, 1 is false, 2 is true
        if(dp[n] != 0) {
            if(dp[n] == 1)
                return false;
            else
                return true;
        }
        if(n <= 0) {
            dp[n] = 1;
        } else if(n == 1) {
            dp[n] = 2;
        } else if(n == 2) {
            dp[n] = 2;
        } else if(n == 3) {
            dp[n] = 1;
        } else {
            if((MemorySearch(n-2, dp) && MemorySearch(n-3, dp)) || 
                (MemorySearch(n-3, dp) && MemorySearch(n-4, dp) )) {
                dp[n] = 2;
            } else {
                dp[n] = 1;
            }
        }
        if(dp[n] == 2) 
            return true;
        return false;
    }

Recursive: Complexity is power(2,n).

int firstWillWin(vector<int> &values, int s, int e) {
if(s == e) return values[s];
return max( values[s] - firstWillWin(values, s+1, e),
values[e] - firstWillWin(values, s, e-1) );
}
bool firstWillWin(vector<int> &values) {
int len = values.size();
if(len<=2) return true;
return firstWillWin(values, 0, len-1) > 0;
}

DP:
http://www.danielbit.com/blog/puzzle/leetcode/leetcode-coins-in-a-line
http://www.jiuzhang.com/solutions/coins-in-a-line/

bool firstWillWin(vector<int> &values) {
int len = values.size();
if(len<=2) return true;
vector<vector<int>> f(len, vector<int>(len,0));
for(int i=0;i<len;i++) f[i][i] = values[i];
for(int i=len-2;i>=0;i--)
{
for(int j=i+1;j<len;j++)
{
f[i][j] = max(values[i] - f[i+1][j], values[j] - f[i][j-1]);
}
}
return f[0][len-1] > 0;
}

第三题，是可以从两端取一个，需要把一维数组变成二维，而且注意边界情况

public boolean firstWillWin(int[] A) {
// write your code here7 n; N* a5 L) o% m; f5 [) R
if(A.length <= 2) return true;
int[][] D = new int[A.length+10][A.length+10];+ Z2 x3 X# ~$ M( X+ o
for(int i=0; i<D.length; i++) {7 z' M0 q6 {7 A1 T# O1 S9 l. S" h, e6 S
for(int j=0; j<D[0].length; j++) {8 n% B, D w0 Y+ X1 A
D【i】[j] = Integer.MAX_VALUE/2;$ W6 a! W1 b+ f; U$ j5 I
}6 q9 A9 P2 h2 f
}6 ~) W6 g" k3 a- ~( ?! c
for(int i=1; i<=A.length; i++) {5 F3 j8 P- Q4 Z/ N% s1 ~: ^9 }
D【i】【i】 = A[i-1];1 |& O: E3 X2 d. d# ~ p8 B
}
int sum = 0;
for(int i=A.length; i>=1; i--) {9 L+ L0 o, O( h# s+ @) ?" O
sum += A[i-1];
for(int j=i+1; j<=A.length; j++) {. Y3 Z3 t/ I6 j. r2 ?
D【i】[j] = Math.max(A[i-1] + Math.min(D[i+2][j], D[i+1][j-1]),
A[j-1] + Math.min(D[i+1][j-1], D【i】[j-2]));
}
}; D3 W3 H( t& I& S& _6 l: x, w
return D[1][A.length] > sum - D[1][A.length];+ V1 B. @$ V% U
}

https://codesolutiony.wordpress.com/2015/05/24/lintcode-coins-in-a-line/

    public boolean firstWillWin(int n) {

        return n % 3 != 0;

}

Read full article from (394) Coins in a Line

LintCode 394 - Coins in a Line

Labels

Popular Posts