Sponsored
Sponsored
This approach leverages dynamic programming to count eligible attendance records. We define a function dp[i][a][l], which represents the number of valid sequences of length i with a absences and l consecutive lates. The transitions will account for adding 'P', 'A', or 'L' to existing records, ensuring we respect the problem's constraints.
Time complexity: O(n), Space complexity: O(1), as we use only a fixed amount of space irrespective of n.
1using System;
2
3public class Solution {
4 private const int MOD = 1000000007;
5 public int CheckRecord(int n) {
6 if (n == 0) return 0;
7 int[][][] dp = new int[2][][];
8 for (int i = 0; i < 2; i++) {
9 dp[i] = new int[n + 1][];
10 for (int j = 0; j <= n; j++) {
11 dp[i][j] = new int[3];
12 }
13 }
14 dp[0][0][0] = 1;
15 for (int i = 0; i < n; i++) {
16 for (int a = 0; a <= 1; a++) {
17 for (int l = 0; l < 3; l++) {
18 dp[a][i + 1][0] = (int)((dp[a][i + 1][0] + (long)dp[a][i][l]) % MOD);
19 if (a == 0) {
20 dp[1][i + 1][0] = (int)((dp[1][i + 1][0] + (long)dp[a][i][l]) % MOD);
21 }
22 if (l < 2) {
23 dp[a][i + 1][l + 1] = (int)((dp[a][i + 1][l + 1] + (long)dp[a][i][l]) % MOD);
24 }
25 }
26 }
27 }
28 int total = 0;
29 for (int a = 0; a <= 1; a++) {
30 for (int l = 0; l < 3; l++) {
31 total = (int)((total + (long)dp[a][n][l]) % MOD);
32 }
33 }
34 return total;
35 }
36
37 public static void Main(string[] args) {
38 Solution solution = new Solution();
39 int n = 2;
40 Console.WriteLine(solution.CheckRecord(n));
41 }
42}This C# solution employs a similar 3D array based dynamic programming technique. The idea is to continuously update the state counts based on possible additions of each character, mitigating overflow risks thanks to type conversions.
This approach uses matrix exponentiation to efficiently solve the problem by leveraging the recursive relationship of the transformation matrices, which model the state transitions of the sequences. The matrix exponentiation technique drastically reduces the time complexity by harnessing fast exponentiation properties.
Time complexity: O(log n), Space complexity: O(1), because we only manipulate fixed-size arrays.
1
public class Solution {
private const int MOD = 1000000007;
private static int[][] Multiply(int[][] A, int[][] B) {
int size = A.Length;
var C = new int[size][];
for (int i = 0; i < size; ++i) {
C[i] = new int[size];
for (int j = 0; j < size; ++j) {
for (int k = 0; k < size; ++k) {
C[i][j] = (int)((C[i][j] + (long)A[i][k] * B[k][j]) % MOD);
}
}
}
return C;
}
private static int[][] Power(int[][] F, int n) {
int size = F.Length;
int[][] result = new int[size][];
for (int i = 0; i < size; i++) {
result[i] = new int[size];
result[i][i] = 1;
}
while (n > 0) {
if ((n & 1) == 1) result = Multiply(result, F);
F = Multiply(F, F);
n >>= 1;
}
return result;
}
public int CheckRecord(int n) {
if (n == 1) return 3;
int[][] F = {
new int[] {1, 1, 0, 1, 0, 0},
new int[] {1, 0, 1, 0, 0, 0},
new int[] {0, 1, 0, 0, 0, 0},
new int[] {0, 0, 0, 1, 1, 0},
new int[] {0, 0, 0, 0, 1, 1},
new int[] {0, 0, 0, 0, 0, 1}
};
var result = Power(F, n - 1);
return (int)((2 * result[0][0] + result[0][1] + result[0][3]) % MOD);
}
public static void Main() {
var solution = new Solution();
Console.WriteLine(solution.CheckRecord(2));
}
}The C# solution efficiently reduces computation time through matrix operations for modeling state transitions, maintaining constant matrix sizes and leveraging exponentiation logic.