Lesson 15: NumberSolitaire (Number Solitaire)
Python Solution: http://www.martinkysel.com/codility-numbersolitaire-solution/
Please read full article from Lesson 15: NumberSolitaire (Number Solitaire)
A game for one player is played on a board consisting of N consecutive squares, numbered from 0 to N − 1. There is a number written on each square. A non-empty zero-indexed array A of N integers contains the numbers written on the squares. Moreover, some squares can be marked during the game.
At the beginning of the game, there is a pebble on square number 0 and this is the only square on the board which is marked. The goal of the game is to move the pebble to square number N − 1.
During each turn we throw a six-sided die, with numbers from 1 to 6 on its faces, and consider the number K, which shows on the upper face after the die comes to rest. Then we move the pebble standing on square number I to square number I + K, providing that square number I + K exists. If square number I + K does not exist, we throw the die again until we obtain a valid move. Finally, we mark square number I + K.
After the game finishes (when the pebble is standing on square number N − 1), we calculate the result. The result of the game is the sum of the numbers written on all marked squares.
For example, given the following array:
A[0] = 1
A[1] = -2
A[2] = 0
A[3] = 9
A[4] = -1
A[5] = -2
one possible game could be as follows:
- the pebble is on square number 0, which is marked;
- we throw 3; the pebble moves from square number 0 to square number 3; we mark square number 3;
- we throw 5; the pebble does not move, since there is no square number 8 on the board;
- we throw 2; the pebble moves to square number 5; we mark this square and the game ends.
The marked squares are 0, 3 and 5, so the result of the game is 1 + 9 + (−2) = 8. This is the maximal possible result that can be achieved on this board.
Write a function:
int solution(int A[], int N);
that, given a non-empty zero-indexed array A of N integers, returns the maximal result that can be achieved on the board represented by array A.
For example, given the array
A[0] = 1
A[1] = -2
A[2] = 0
A[3] = 9
A[4] = -1
A[5] = -2
the function should return 8, as explained above.
Assume that:
- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [−10,000..10,000].
Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
一个游戏是从一排N个格子开始，格子编号0..N - 1，起初，棋子在A[0]，每个格子里有一个整数（可能正，可能负）。你在格子I，你扔骰子，得到点数X = [1..6]，然后走到编号为I + X的格子，如果这个格子不存在就再投一次骰子，直到I + X号格子存在。你走到N - 1号格子时，游戏结束。你所经过格子里的整数的和是你的得分，求最大可能得分？
数据范围： N [2..10^5]， 格子里的数的范围 [-10000, +10000]。
要求复杂度： 时间O(N),空间O(N)
分析： 一个显然的dp dp[i] = A[i] + max(dp[i - x]) 1<=x<=min(6,i)
- int solution(vector<int> &A) {
- const int inf = 2000000000;
- int n = A.size();
- vector<int> dp(n);
- dp[0] = A[0];
- for (int i = 1; i < n; ++i) {
- dp[i] = -inf;
- for (int j = min(6 , i); j; --j) {
- dp[i] = max(dp[i], dp[i - j]);
- }
- dp[i] += A[i];
- }
- return dp[n - 1];
- }
Anyway, what we do is the almost the same as in the FibFrog problem.
We prepare the array max_val[] and then initialize it with INT_MIN, which is smaller than the possible minimum value in the given conditions, except max_val[0], which is set the initial point we get when we start at A[0].
We begin from the position 0 and take the value at max_val[0]. Then, we add this point with the points we can obtain at each cell we can reach by the next jump and update the maximum value if it is larger than one that we obtained so far at the cell.
We repeat this until the cell we can perform the last jump (at the position N - 2, right before the goal).
We prepare the array max_val[] and then initialize it with INT_MIN, which is smaller than the possible minimum value in the given conditions, except max_val[0], which is set the initial point we get when we start at A[0].
We begin from the position 0 and take the value at max_val[0]. Then, we add this point with the points we can obtain at each cell we can reach by the next jump and update the maximum value if it is larger than one that we obtained so far at the cell.
We repeat this until the cell we can perform the last jump (at the position N - 2, right before the goal).
public int solution(int[] A) {
int[] dp = new int[A.length];
dp[0] = A[0];
for (int i = 1; i < A.length; i++) dp[i] = Integer.MIN_VALUE;
for (int i = 0; i < A.length; i++) {
for (int k = 1; k <= 6 && i + k < A.length; k++) {
dp[i + k] = Math.max(dp[i + k], dp[i] + A[i + k]);
}
}
return dp[A.length - 1];
}
int solution(int A[], int N)
{
int memsize = sizeof(int) * N;
int* max_val = (int*)alloca(memsize);
//initialize the each cell with INT_MIN except the first one.
max_val[0] = A[0];
for (int i = 1; i < N; i++){
max_val[i] = INT_MIN;
}
//do dynamic programming for jump
for (int pos = 0; pos < N - 1; pos++){
//throw the dice (1-6)
for (int j = 1; j <= 6; j++){
//if out of range, neglect.
int jump_pos = pos + j;
//not to jump out of the range.
if (jump_pos >= N){
continue;
}
//update each cell's max value.
int tmp = A[pos + j] + max_val[pos];
max_val[jump_pos] = max_val[jump_pos] < tmp ? tmp : max_val[jump_pos];
}
}
return max_val[N - 1];
}
Python Solution: http://www.martinkysel.com/codility-numbersolitaire-solution/
Please read full article from Lesson 15: NumberSolitaire (Number Solitaire)
