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.↵
~~~~~↵
↵
<spoiler summary="hint">↵
Precomputation + Binary Search↵
</spoiler>↵
↵
<spoiPossibler summary="code">↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
// Compare numeric strings by length then lex↵
bool numLess(const string &a, const string &b) {↵
if (a.size() != b.size()) ↵
return a.size() < b.size();↵
return a < b;↵
}↵
↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
// 1) Precompute all special palindromes↵
vector<string> pals;↵
for(int mask = 1; mask < (1<<9); ++mask){↵
// count how many odd digits are selected↵
int oddCount = 0, oddDigit = -1;↵
for(int d = 1; d <= 9; ++d){↵
if (mask & (1<<(d-1))){↵
if (d % 2 == 1) {↵
oddCount++;↵
oddDigit = d;↵
}↵
}↵
}↵
if (oddCount > 1) continue; // can't form palindrome↵
↵
// build half-string: for each selected d, add floor(d/2) copies of '0'+d↵
string half;↵
for(int d = 1; d <= 9; ++d){↵
if (mask & (1<<(d-1))){↵
half.append(d/2, char('0' + d));↵
}↵
}↵
// build the full palindrome↵
string rev = half;↵
reverse(rev.begin(), rev.end());↵
string pal = half;↵
if (oddCount == 1) ↵
pal.push_back(char('0' + oddDigit));↵
pal += rev;↵
↵
pals.push_back(pal);↵
}↵
↵
// 2) Sort by numeric value↵
sort(pals.begin(), pals.end(), numLess);↵
↵
// 3) Answer queries↵
int T;↵
cin >> T;↵
while(T--){↵
string n;↵
cin >> n;↵
// find first palindrome strictly > n↵
auto it = upper_bound(↵
pals.begin(), pals.end(), n,↵
[](const string &a, const string &b){↵
return numLess(a,b);↵
}↵
);↵
// it is guaranteed to exist because the largest precomputed is > 10^17↵
cout << *it << "\n";↵
}↵
return 0;↵
}↵
</spoiler>↵
↵
olution :- Precompute + BinarySearch
↵
~~~~~↵
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.↵
~~~~~↵
<spoiler summary="hint">↵
Precomputation + Binary Search↵
</spoiler>↵
↵
<spoi
#include <bits/stdc++.h>↵
using namespace std;↵
↵
// Compare numeric strings by length then lex↵
bool numLess(const string &a, const string &b) {↵
if (a.size() != b.size()) ↵
return a.size() < b.size();↵
return a < b;↵
}↵
↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
// 1) Precompute all special palindromes↵
vector<string> pals;↵
for(int mask = 1; mask < (1<<9); ++mask){↵
// count how many odd digits are selected↵
int oddCount = 0, oddDigit = -1;↵
for(int d = 1; d <= 9; ++d){↵
if (mask & (1<<(d-1))){↵
if (d % 2 == 1) {↵
oddCount++;↵
oddDigit = d;↵
}↵
}↵
}↵
if (oddCount > 1) continue; // can't form palindrome↵
↵
// build half-string: for each selected d, add floor(d/2) copies of '0'+d↵
string half;↵
for(int d = 1; d <= 9; ++d){↵
if (mask & (1<<(d-1))){↵
half.append(d/2, char('0' + d));↵
}↵
}↵
// build the full palindrome↵
string rev = half;↵
reverse(rev.begin(), rev.end());↵
string pal = half;↵
if (oddCount == 1) ↵
pal.push_back(char('0' + oddDigit));↵
pal += rev;↵
↵
pals.push_back(pal);↵
}↵
↵
// 2) Sort by numeric value↵
sort(pals.begin(), pals.end(), numLess);↵
↵
// 3) Answer queries↵
int T;↵
cin >> T;↵
while(T--){↵
string n;↵
cin >> n;↵
// find first palindrome strictly > n↵
auto it = upper_bound(↵
pals.begin(), pals.end(), n,↵
[](const string &a, const string &b){↵
return numLess(a,b);↵
}↵
);↵
// it is guaranteed to exist because the largest precomputed is > 10^17↵
cout << *it << "\n";↵
}↵
return 0;↵
}↵
</spoiler>↵
↵
