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.
1#include <stdio.h>
2#define MOD 1000000007
3
4int checkRecord(int n) {
5 int p_dp, a_dp, l_dp[3][3] = {{1}}, i, p_dpOld, a_dpOld;
6 p_dp = 1, a_dp = 0;
7 for (i = 1; i <= n; ++i) {
8 p_dpOld = p_dp;
9 a_dpOld = a_dp;
10 p_dp = ((p_dpOld + a_dpOld) % MOD + (l_dp[0][0] + l_dp[1][0] + l_dp[2][0]) % MOD) % MOD;
11 a_dp = (p_dpOld + (l_dp[0][1] + l_dp[1][1] + l_dp[2][1]) % MOD) % MOD;
12 l_dp[2][0] = l_dp[1][0]; l_dp[1][0] = l_dp[0][0]; l_dp[0][0] = p_dpOld;
13 l_dp[2][1] = l_dp[1][1]; l_dp[1][1] = l_dp[0][1]; l_dp[0][1] = a_dpOld;
14 }
15 return ((l_dp[0][0] + l_dp[1][0] + l_dp[2][0]) % MOD + (l_dp[0][1] + l_dp[1][1] + l_dp[2][1]) % MOD + a_dp + p_dp) % MOD;
16}
17
18int main() {
19 int n = 2;
20 printf("%d\n", checkRecord(n));
21 return 0;
22}The C solution uses a bottom-up dynamic programming approach with space optimization. Arrays l_dp track sequences ending in late days to limit space, and the solution iteratively calculates valid sequences of increasing length up to n.
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#include <vector>
#define MOD 1000000007
typedef std::vector<std::vector<long long>> matrix;
matrix multiply(matrix A, matrix B) {
int size = A.size();
matrix C(size, std::vector<long long>(size));
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
for (int k = 0; k < size; k++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j] % MOD) % MOD;
return C;
}
matrix power(matrix A, int n) {
int size = A.size();
matrix result(size, std::vector<long long>(size));
for (int i = 0; i < size; i++) result[i][i] = 1;
while (n > 0) {
if (n % 2 == 1) result = multiply(result, A);
A = multiply(A, A);
n /= 2;
}
return result;
}
int checkRecord(int n) {
if (n == 1) return 3;
matrix F = { {1, 1, 0, 1, 0, 0}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 1} };
matrix result = power(F, n - 1);
return (2 * result[0][0] + result[0][1] + result[0][3]) % MOD;
}
int main() {
int n = 2;
std::cout << checkRecord(n) << std::endl;
return 0;
}The C++ implementation uses the same matrix exponentiation strategy by utilizing vectors to perform matrix operations efficiently, reducing time complexity drastically.