Amr Gamal
BAN USERThe idea is that when you start taking coins and you have "n" coins, you can take the coin at the beginning (at index 0) and you are left with coins [1,n-1], or you can take the coin at position n-1 and you are left with coins [0,n-2]. In either case, you are left with a version of the problem where you have n-1 coins and YOUR OPPONENT STARTS.
Imagine now that you have a total of n-1 coins but your opponent is the one who will start the move. In this case there are two options, either the opponent chooses the coin at the beginning or he chooses the coin at the end. in either case you are now left with a total of n-2 coins and YOU START THE MOVE once again.
In the base case when you have once coin, If it is your turn, you pick it, if it is not your turn you gain nothing.
We can solve this problem using dynamic programming. We will basically have two 2-dimensional arrays. The first one caches the max number of coins you can take for every possible start and end in the original array of coins when YOU START. The other 2-D array caches the max number of coins you can get for every possible start and end in the original array when YOUR OPPONENT starts moving, please find the code below
import java.util.Arrays;
public class coinGame {
public static int solveGame(int[][] whenIStart, int[][] whenIDontStart, int size, int [] array, int start,
int end, boolean IStart){
if(start>= size || end>= size || start > end || start <0 || end <0)
return 0;
if(IStart){
if(whenIStart[start][end]!=-1)
return whenIStart[start][end];
else{
int optionOne = array[start] + solveGame(whenIStart, whenIDontStart, size, array, start+1, end, false);
int optionTwo = array[end] + solveGame(whenIStart, whenIDontStart, size, array, start, end-1, false);
int result = Math.max(optionOne, optionTwo);
whenIStart[start][end] = result;
return result;
}
}
else{
if(whenIDontStart[start][end]!=-1){
return whenIDontStart[start][end];
}
else{
int optionOne = solveGame(whenIStart, whenIDontStart, size, array, start+1, end, true);
int optionTwo = solveGame(whenIStart, whenIDontStart, size, array, start, end-1, true);
int result = Math.max(optionOne, optionTwo);
whenIDontStart[start][end] = result;
return result;
}
}
}
public static int solve(int[]array){
if(array==null || array.length ==0)
return 0;
int[][]whenIStart = createAndFill(array.length);
int[][]whenIDontStart = createAndFill(array.length);
int size = array.length;
int start = 0;
int end = size -1;
boolean IStart = true;
return solveGame(whenIStart,whenIDontStart,size, array,start,
end, IStart);
}
public static int[][] createAndFill(int size){
int[][]array = new int[size][size];
for(int i =0; i<array.length; i++){
for(int j =0; j<array[i].length; j++){
array[i][j] = -1;
}
}
return array;
}
public static void main(String[]args){
int[]ar = {5,2,3};
System.out.println(solve(ar));
}
}
First let's consider the solution of picking 1 coin from the first bucket, 2 from the 2nd, 3 from teh 3rd and so on. This solution won't work as we can't tell the difference if the first and the second bucket both have fake coins (we'll have -0.3 grams) or if the third bucket only had fake coins (-0.3 grams in the final measurment).
Thus This problem reduces to finding a set of 5 numbers such that any subset of them has a unique sum. The first element in this set represents the number of coins to be drawn from the first buckt, 2nd element is the number of coins to be drawn from the second bucket and so on. Thus if every combination of the numbers in this set has a unique sum, we can determine which buckets had the fake coins.
Lets pick one coin from first bucket and two coins from the second bucket. So our set now has the elements {1,2} and sums of all combinations of its elements is {1,2,3} (where the 3 is the 1+2 combination). Thus it is clear the we can't pick 1 or 2 or 3 coins from the 3rd bucket because this will lead to confusion. So let's pick 4 coins from the 3rd bucket. Now the set has elements 1,2,4 and the sums that can be generated are {1,2, 3 (1+2), 4, 5 (1+4), 6 (2+4), 7 (1+2+4)}. So we can't pick any number from 1-7 from the fourth bucket. So let's pick 8. At this point it is clear that numbers follow the pattern of "powers of 2" and we can deduce that we need to draw 16 coins from 5th bucket.
Consider the resultant string to be S1...E1 S2... E2 ................ Sn... En
where Si is the starting character of String i and Ei is the ending character of String i. Here, E1 must be equal to S2 and E2 must be equal to S3 and En-1 must be equal to Sn. But S1 and En donot have any relation with any other character. So consider that the Set of starting characters S = {S1, S2, ...., Sn} and the set of ending characters E = {E1, E2, ..... , En}. We need these sets to differ only by at most one element. This element will be the start of the first String and the end of the last string). But for every other value in Set S, other than the value that differs, there must be a corrsponding value in set E. A way to implement this is to have an array of integers with a cell for each character. First, for every character in set S, we increment its position in the array by one. Then for every character in Set E we decrement its place in the array by one. Afterwards if the array is all zeros (every charcater in the set S had a matching character in set E) or if the array consists of zeros except for one cell having value one and one cell having value negative one (in that case only one character differs between set S and set E) then all strings can be adhered together and there's a solution.
Consider the resultant string to be S1...E1 S2... E2 ................ Sn... En
where Si is the starting character of String i and Ei is the ending character of String i. Here, E1 must be equal to S2 and E2 must be equal to S3 and En-1 must be equal to Sn. But S1 and En donot have any relation with any other character. So consider that the Set of starting characters S = {S1, S2, ...., Sn} and the set of ending characters E = {E1, E2, ..... , En}. We need these sets to differ only by at most one element. This element will be the start of the first String and the end of the last string). But for every other value in Set S, other than the value that differs, there must be a corrsponding value in set E. A way to implement this is to have an array of integers with a cell for each character. First, for every character in set S, we increment its position in the array by one. Then for every character in Set E we decrement its place in the array by one. Afterwards if the array is all zeros (every charcater in the set S had a matching character in set E) or if the array consists of zeros except for one cell having value one and one cell having value negative one (in that case only one character differs between set S and set E) then all strings can be adhered together and there's a solution.
your code doesn't generate some permutations like "abad" for example when I tried the call func(arr,4,0,1);. I believe this is because you start with the permutation "aabb" and then keep incrementing the last character so it becomes "aabz" and then you increment the second from last character and that's how you miss permutations like "abad".
- Amr Gamal September 21, 2013At every cell, there are two diagonals that pass through this cell, one going from top-left corner of the matrix to bottom-right corner and the other going from top-right to bottom-left corner. The idea is to keep a matrix of the same size as the input matrix, each entry represents the the number of consecutive ones in the diagonal going from top-left to bottom-right corner such that the sequence of ones starts at the top left of current cell and ends at the current cell, similarly we keep 3 other matrices, one for sequences of ones in the diagonal going from top-left to bottom-right but starting at a cell that is at the bottom right of the current cell. The other 2 matrices are kept from the other diagonal going from top-right to bottom-left corner.
for example, consider the matrix:
0 1 1 1 0 0 0
0 1 0 0 0 0 0
0 1 1 0 1 0 1
1 0 0 1 1 1 0
1 0 1 1 0 1 0
1 1 1 1 1 0 1
top-left matrix keeping counts of ones starting at top left and ending at each cell:
0 1 1 1 0 0 0
0 1 0 0 0 0 0
0 1 2 0 1 0 1
1 0 0 3 1 2 0
1 0 1 1 0 2 0
1 2 1 2 2 0 3
bottom-left
0 1 2 1 0 0 0
0 1 0 0 0 0 0
0 2 1 0 4 0 2
1 0 0 3 3 1 0
1 0 2 2 0 2 0
1 1 1 1 1 0 1
top-right
0 1 1 1 0 0 0
0 2 0 0 0 0 0
0 1 1 0 1 0 1
2 0 0 2 1 2 0
1 0 3 2 0 1 0
1 4 3 1 2 0 1
bottom-right
0 1 1 1 0 0 0
0 3 0 0 0 0 0
0 1 2 0 2 0 1
1 0 0 1 3 1 0
2 0 2 2 0 2 0
1 1 1 1 1 0 1
and then at each cell[i,j] in the original matrix, get length of sequences of ones ending at the 4 neighboring diagonal cells from the matrices computed above, namely [i-1, j-1], [i-1, j+1], [i+1, j-1], [i+1, j+1], compute "minValue" which is the minimum of these values.
size of an X with center at the current cell is 2*minValue+1.
time complexity O(n*m), space Complexity O(n*m).
This approach won't work in case the word is a compound of 3 or more dictionary words.
- Amr Gamal November 09, 2014