↵
↵
↵
↵
~~~~~↵
Problem 1.↵
↵
~~~~~↵
Given an array find no. of non-empty subsequences which does not have three consecutive odd or three consecutive even numbers in subsequence. Since answer is large print it modulo 1e9+7. ↵
Expected time complexity is O(N) or (ONlogN).↵
↵
~~~~~↵
↵
↵
↵
<spoiler summary="hint">↵
DP... dp[k][i][j]: number of subsequences using first k elements, where the last two parities are (i, j), with↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
static const long long MOD = 1000000007;↵
↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int n;↵
cin >> n;↵
vector<long long> a(n);↵
for(int i = 0; i < n; i++){↵
cin >> a[i];↵
}↵
↵
// dp[k][i][j]: number of subsequences using first k elements↵
// where the last two parities are (i, j), with:↵
// 0 = none, 1 = even, 2 = odd↵
vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(3, vector<long long>(3, 0)));↵
dp[0][0][0] = 1; // Base case: empty subsequence↵
↵
for(int k = 0; k < n; k++){↵
int p = (a[k] % 2 == 0 ? 1 : 2);↵
for(int i = 0; i < 3; i++){↵
for(int j = 0; j < 3; j++){↵
// Case 1: don't take a[k]↵
dp[k + 1][i][j] = (dp[k + 1][i][j] + dp[k][i][j]) % MOD;↵
↵
// Case 2: take a[k] if it doesn't form 3 same parity↵
if (!(i == j && j == p)) {↵
dp[k + 1][j][p] = (dp[k + 1][j][p] + dp[k][i][j]) % MOD;↵
}↵
}↵
}↵
}↵
↵
// sum over all final dp[n][i][j] and subtract empty subsequence↵
long long ans = 0;↵
for(int i = 0; i < 3; i++){↵
for(int j = 0; j < 3; j++){↵
ans = (ans + dp[n][i][j]) % MOD;↵
}↵
}↵
ans = (ans - 1 + MOD) % MOD;↵
↵
cout << ans << "\n";↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
~~~~~↵
Problem 2.↵
A number X is said to be palindrome special, if every digit i present in X occurs exactly i times and digits of X form a palindrome, you are given t test cases (<=1e5) and in each test case integer N(<=1e17). Find nearest greater no. which is a special palindrome.↵
~~~~~↵
Possible solution :- Precompute + B↵
<spoiler summary="hint">↵
precomputation + Binary Search↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
This is the precomputation part.↵
https://mirror.codeforces.com/blog/entry/144519?#comment-1292738↵
↵
After that just binaryS search to find greater element.↵
</spoiler>↵
↵
↵
↵
↵
~~~~~↵
Problem 1.↵
~~~~~↵
Expected time complexity is O(N) or (ONlogN).↵
↵
~~~~~↵
↵
↵
↵
<spoiler summary="hint">↵
DP... dp[k][i][j]: number of subsequences using first k elements, where the last two parities are (i, j), with↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
static const long long MOD = 1000000007;↵
↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int n;↵
cin >> n;↵
vector<long long> a(n);↵
for(int i = 0; i < n; i++){↵
cin >> a[i];↵
}↵
↵
// dp[k][i][j]: number of subsequences using first k elements↵
// where the last two parities are (i, j), with:↵
// 0 = none, 1 = even, 2 = odd↵
vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(3, vector<long long>(3, 0)));↵
dp[0][0][0] = 1; // Base case: empty subsequence↵
↵
for(int k = 0; k < n; k++){↵
int p = (a[k] % 2 == 0 ? 1 : 2);↵
for(int i = 0; i < 3; i++){↵
for(int j = 0; j < 3; j++){↵
// Case 1: don't take a[k]↵
dp[k + 1][i][j] = (dp[k + 1][i][j] + dp[k][i][j]) % MOD;↵
↵
// Case 2: take a[k] if it doesn't form 3 same parity↵
if (!(i == j && j == p)) {↵
dp[k + 1][j][p] = (dp[k + 1][j][p] + dp[k][i][j]) % MOD;↵
}↵
}↵
}↵
}↵
↵
// sum over all final dp[n][i][j] and subtract empty subsequence↵
long long ans = 0;↵
for(int i = 0; i < 3; i++){↵
for(int j = 0; j < 3; j++){↵
ans = (ans + dp[n][i][j]) % MOD;↵
}↵
}↵
ans = (ans - 1 + MOD) % MOD;↵
↵
cout << ans << "\n";↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
~~~~~↵
Problem 2.↵
A number X is said to be palindrome special, if every digit i present in X occurs exactly i times and digits of X form a palindrome, you are given t test cases (<=1e5) and in each test case integer N(<=1e17). Find nearest greater no. which is a special palindrome.↵
~~~~~↵
<spoiler summary="hint">↵
precomputation + Binary Search↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
This is the precomputation part.↵
https://mirror.codeforces.com/blog/entry/144519?#comment-1292738↵
↵
After that just binary
</spoiler>↵
↵
