## Monday, April 17, 2017

### LeetCode 552 - Student Attendance Record II

https://leetcode.com/problems/student-attendance-record-ii
Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 109 + 7.
A student attendance record is a string that only contains the following three characters:
1. 'A' : Absent.
2. 'L' : Late.
3. 'P' : Present.
A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).
Example 1:
```Input: n = 2
Output: 8
Explanation:
There are 8 records with length 2 will be regarded as rewardable:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" won't be regarded as rewardable owing to more than one absent times.
```
Note: The value of n won't exceed 100,000.
X.

A[i] = P1[i-1] + L1[i-1]
P1[i] = P1[i-1] + L1[i-1]
L1[i] = P1[i-1] + P1[i-2]

A[i] = A[i-1] + A[i-2] + A[i-3]

https://discuss.leetcode.com/topic/86696/share-my-o-n-c-dp-solution-with-thinking-process-and-explanation
Before introducing the way to calculate the number of all possible attendance records with length n, we divide the problem into 3 parts.

As the attendance records is made by 3 charactors ('P', 'L', 'A'), the total number can be divided into

#### Total = ended with P + ended with L + ended with A.

If we define following series

#### A(n) is the total number of all possible attendance records ended with 'A' with length n.

It can be inferred that

#### 2.2 Solve the sub-problems by dynamic programming

As I use dynamic programming, I need to find out the recursive relation in 3 sub-problems.

##### 2.2.1 CALCULATE P(N)

It can be inferred that

#### If we add a 'P' to an attendance records with length n - 1, we will get an attendance records ended with 'P' with length n.

For an attendance record with length n - 1,

which means

#### P(n) = A(n - 1) + P(n - 1) + L(n - 1), n ≥ 2.

and we have initial value for the recursive relation

Similarly,

#### If we add a 'L' to an attendance records with length n - 1, we will get an attendance records ended with 'L' with length n.

But the resulting attendance records must be regared as rewardable!

As the rule is that a record is regarded as rewardable if it doesn't contain

#### more than two continuous 'L' (late).

We need to consider the situations when we can add 'L' to an attendance record with length n - 1 and it's still regared as rewardable.

For an attendance record with length n - 1,

which means

#### L(n) = A(n - 1) + P(n - 1) + A(n - 2) + P(n - 2), n ≥ 3

and we have initial value for the recursive relation

and

Similarly,

#### If we add a 'A' to an attendance records with length n - 1, we will get an attendance records ended with 'A' with length n.

But the resulting attendance records must be regared as rewardable!

As the rule is that a record is regarded as rewardable if it doesn't contain

#### more than one 'A' (absent).

We need to consider the situations when we can add 'A' to an attendance record with length n - 1 and it's still regared as rewardable.

For an attendance record with length n - 1,
• If its (n - 1)th charactor is 'A' ---- CAN NOT add 'A'. ("AA" breaks the rule)
• If its (n - 1)th charactor is 'P' and has no 'A' ---- CAN add 'A'.
• If its (n - 1)th charactor is 'L' and has no 'A' ---- CAN add 'A'.

If we define series

#### noAL(n) is the total number of all possible attendance records ended with 'L' with length n and with no 'A'.

It can be infered that

#### A(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

and we have initial value for the recursive relation

#### noAP(1) = noAL(1) = 1.

##### 2.2.4 CALCULATE NOAP(N) AND NOAL(N)

In 2.2.3, 2 new series noAP(n) and noAL(n) is introduced. Now, we focus on the recursive relation in noAP(n) and noAL(n).

For noAP(n), we need to consider the situations when we can add 'P' to an attendance record with length n - 1 and no 'A' and it's still regared as rewardable.

Since noAP(n) has no 'A', we don't need to consider the situation when its (n - 1)th charactor is 'A'.

For an attendance record with length n - 1, we can get only 2 situations
• If its (n - 1)th charactor is 'P' and has no 'A' ---- CAN add 'P'.
• If its (n - 1)th charactor is 'L' and has no 'A' ---- CAN add 'P'.

which means

#### noAP(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

and we have initial value for the recursive relation

#### noAP(1) = noAL(1) = 1.

For noAL(n), we need to consider the situations when we can add 'L' to an attendance record with length n - 1 and no 'A' and it's still regared as rewardable.

Since noAL(n) has no 'A', we don't need to consider the situation when its (n - 1)th charactor is 'A'.

For an attendance record with length n - 1, we can get
• If its (n - 1)th charactor is 'P' and has no 'A' ---- CAN add 'L'.("PL")
• If its (n - 1)th charactor is 'L' and has no 'A'.
• If its (n - 2)th charactor is 'P' and has no 'A' ---- CAN add 'L'.("PLL")
• If its (n - 2)th charactor is 'L' and has no 'A' ---- CAN NOT add 'L'.("LLL" breaks the rule.)

which means

#### noAL(n) = noAP(n - 1) + noAP(n - 2), n ≥ 3.

and we have initial value for the recursive relation

and

#### 2.3 Recursive relationship summarization

The answer to the whole problem is T(n), and

#### T(n) = A(n) + P(n) + L(n), n ≥ 1.

Recursive formula:

#### noAL(n) = noAP(n - 1) + noAP(n - 2), n ≥ 3.

with Initial value

#### 2.4 Simplifying

When n ≥ 4, the 3 formulas

#### noAL(n) = noAP(n - 1) + noAP(n - 2), n ≥ 3.

can be simplified to

#### A(n) = A(n - 1) + A(n - 2) + A(n - 3), n ≥ 4.

Finally, the recursive formula group becomes

#### A(n) = A(n - 1) + A(n - 2) + A(n - 3), n ≥ 4.

Here, noAP(n) and noAL(n) disappeared.

with Initial value

#### 2.5 Do modulus

The result need to be returned after mod 10⁹ + 7.
Since the result is generated by adding a lot of middle results together, in order to make sure that every middle result and the final result won't exceed INT_MAX, we need to do mod for every middle result, and for every 2-middle-result-addition.

## 3. Complexity Analyse

#### 3.1 Time complexity

Since the algothrim is one-pass from 1 to n.

#### 3.2 Space complexity

Since 3 arrays are used to save P(n), L(n), A(n), the total size is 3n.

#### The space complexity is O(n).

http://blog.csdn.net/zshouyi/article/details/71157585
``````    int checkRecord(int n) {
int m = 1000000007;
int *A = new int [n];
int *P = new int [n];
int *L = new int [n];

P[0] = 1;
L[0] = 1;
L[1] = 3;
A[0] = 1;
A[1] = 2;
A[2] = 4;

if(n == 1) return 3;

for(int i = 1; i < n; i++)
{
A[i - 1] %= m;
P[i - 1] %= m;
L[i - 1] %= m;

P[i] = ((A[i - 1] + P[i - 1]) % m + L[i - 1]) % m;

if(i > 1) L[i] = ((A[i - 1] + P[i - 1]) % m + (A[i - 2] + P[i - 2]) % m) % m;

if(i > 2) A[i] = ((A[i - 1] + A[i - 2]) % m + A[i - 3]) % m;
}

return ((A[n - 1] % m + P[n - 1] % m) % m + L[n - 1] % m) % m;
}``````

X.
http://www.cnblogs.com/grandyang/p/6866756.html

https://discuss.leetcode.com/topic/86526/improving-the-runtime-from-o-n-to-o-log-n
Let `f[i][j][k]` denote the # of valid sequences of length `i` where:
1. There can be at most `j` A's in the entire sequence.
2. There can be at most `k` trailing L's.
We give the recurrence in the following code, which should be self-explanatory, and the final answer is `f[n][1][2]`.
``````public int checkRecord(int n) {
final int MOD = 1000000007;
int[][][] f = new int[n + 1][2][3];

f[0] = new int[][]{{1, 1, 1}, {1, 1, 1}};
for (int i = 1; i <= n; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 3; k++) {
int val = f[i - 1][j][2]; // ...P
if (j > 0) val = (val + f[i - 1][j - 1][2]) % MOD; // ...A
if (k > 0) val = (val + f[i - 1][j][k - 1]) % MOD; // ...L
f[i][j][k] = val;
}
return f[n][1][2];
}
``````
The runtime of this solution is clearly O(n), using linear space (which can be easily optimized to O(1) though). Now, let's see how to further improve the runtime.
In fact, if we treat `f[i][][]` and `f[i-1][][]` as two vectors, we can represent the recurrence of `f[i][j][k]` as follows:
``````f[i][0][0]   | 0 0 1 0 0 0 |   f[i-1][0][0]
f[i][0][1]   | 1 0 1 0 0 0 |   f[i-1][0][1]
f[i][0][2] = | 0 1 1 0 0 0 | * f[i-1][0][2]
f[i][1][0]   | 0 0 1 0 0 1 |   f[i-1][1][0]
f[i][1][1]   | 0 0 1 1 0 1 |   f[i-1][1][1]
f[i][1][2]   | 0 0 1 0 1 1 |   f[i-1][1][2]
``````
Let `A` be the matrix above, then `f[n][][] = A^n * f[0][][]`, where `f[0][][] = [1 1 1 1 1 1]`. The point of this approach is that we can compute `A^n` using exponentiating by squaring (thanks to @StefanPochmann for the name correction), which will take O(6^3 * log n) = O(log n) time. Therefore, the runtime improves to O(log n), which suffices to handle the case for much larger `n`, say 10^18.
Update: The final answer is `f[n][1][2]`, which involves multiplying the last row of `A^n` and the column vector `[1 1 1 1 1 1]`. Interestingly, it is also equal to `A^(n+1)[5][2]` as the third column of `A` is just that vector

``````final int MOD = 1000000007;
final int M = 6;

int[][] mul(int[][] A, int[][] B) {
int[][] C = new int[M][M];
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++)
for (int k = 0; k < M; k++)
C[i][j] = (int) ((C[i][j] + (long) A[i][k] * B[k][j]) % MOD);
return C;
}

int[][] pow(int[][] A, int n) {
int[][] res = new int[M][M];
for (int i = 0; i < M; i++)
res[i][i] = 1;
while (n > 0) {
if (n % 2 == 1)
res = mul(res, A);
A = mul(A, A);
n /= 2;
}
return res;
}

public int checkRecord(int n) {
int[][] A = {
{0, 0, 1, 0, 0, 0},
{1, 0, 1, 0, 0, 0},
{0, 1, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 1},
{0, 0, 1, 1, 0, 1},
{0, 0, 1, 0, 1, 1},
};
return pow(A, n + 1)[5][2];
}``````
https://discuss.leetcode.com/topic/86479/o-n-time-o-1-space-solution

http://code.bitjoy.net/2017/04/26/leetcode-student-attendance-record-ii/

dp[n][0][0]=sum(dp[n-1][0])：要求长度为n、包含0个'A'，且以0个'L'结尾的字符串个数；所以前n-1肯定也只包含0个'A'，但是前n-1可以以0、1或2个'L'结尾，因为我第n个字符不放'L'就能保证前n以0个'L'结尾。所以dp[n][0][0]=sum(dp[n-1][0])。其他的类似分析有：
• dp[n][0][1]=dp[n-1][0][0]
• dp[n][0][2]=dp[n-1][0][1]
• dp[n][1][0]=sum(dp[n-1][0])+sum(dp[n-1][1])
• dp[n][1][1]=dp[n-1][1][0]
• dp[n][1][2]=dp[n-1][1][1]
`    ``long` `long` `getSum(vector<``int``>& v) {`
`        ``long` `long` `ans = 0;`
`        ``for``(``const` `int` `&i : v) ans += i;`
`        ``return` `ans % kMOD;`
`    ``}`

`    ``int` `checkRecord(``int` `n) {`
`        ``vector<vector<``int``>> dp = {{1, 1, 0}, {1, 0, 0}};`
`        ``for``(``int` `i = 2; i <= n; ++i){`
`            ``vector<vector<``int``>> ndp = {{0, 0, 0}, {0, 0, 0}};`
`            ``ndp[0][0] = getSum(dp[0]);`
`            ``ndp[0][1] = dp[0][0];`
`            ``ndp[0][2] = dp[0][1];`
`            ``ndp[1][0] = (getSum(dp[1]) + getSum(dp[0])) % kMOD;`
`            ``ndp[1][1] = dp[1][0];`
`            ``ndp[1][2] = dp[1][1];`
`            ``dp = ndp;`
`        ``}`
`        ``return` `(getSum(dp[0]) + getSum(dp[1])) % kMOD;`
`    ``}`
X. DP

`利用dp[n][A][L]表示长度为n，包含A个字符'A'，以L个连续的'L'结尾的字符串的个数。`

```dp[n][0][0] = sum(dp[n - 1][0])
dp[n][0][1] = dp[n - 1][0][0]
dp[n][0][2] = dp[n - 1][0][1]
dp[n][1][0] = sum(dp[n - 1][0]) + sum(dp[n - 1][1])
dp[n][1][1] = dp[n - 1][1][0]
dp[n][1][2] = dp[n - 1][1][1]

private final int MOD = 1000000007; public long sum(int[] nums) { long ans = 0; for (int n : nums) ans += n; return ans % MOD; } public int checkRecord(int n) { int dp[][] = {{1, 1, 0}, {1, 0, 0}}; for (int i = 2; i <= n; i++) { int ndp[][] = {{0, 0, 0}, {0, 0, 0}}; ndp[0][0] = (int)sum(dp[0]); ndp[0][1] = dp[0][0]; ndp[0][2] = dp[0][1]; ndp[1][0] = (int)((sum(dp[0]) + sum(dp[1])) % MOD); ndp[1][1] = dp[1][0]; ndp[1][2] = dp[1][1]; dp = ndp; } return (int)((sum(dp[0]) + sum(dp[1])) % MOD); }

X.
http://www.cnblogs.com/grandyang/p/6866756.html

https://discuss.leetcode.com/topic/86507/simple-java-o-n-solution
P[i] = PorL[i - 1]; //this line means ending with P, just appending P in PorL
PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M; //P[i] end with P, P[i-1], end with one L(or PL), P[i-2], end with two L(or LL).
and last logic ,res init value with PorL without A, and add one A to the sequence.
long res = PorL[n];
for (int i = 0; i < n; i++) { // inserting A into (n-1)-length strings
long s = (PorL[i] * PorL[n - i - 1]) % M;
res = (res + s) % M;
}
``````static final int M = 1000000007;

public int checkRecord(int n) {
long[] PorL = new long[n + 1]; // ending with P or L, no A
long[] P = new long[n + 1]; // ending with P, no A
PorL[0] = P[0] = 1; PorL[1] = 2; P[1] = 1;

for (int i = 2; i <= n; i++) {
P[i] = PorL[i - 1];
PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M;
}

long res = PorL[n];
for (int i = 0; i < n; i++) { // inserting A into (n-1)-length strings
long s = (PorL[i] * PorL[n - i - 1]) % M;
res = (res + s) % M;
}

return (int) res;
}``````