#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;
}
In the solution of question 2, 442244 and 244442 and 424424 all are valid special palindromes but the given code adds all the digits d//2 times together. So, I think only 244442 will be generated but other 2 will not be generated. Correct me if I am wrong.
Yeah you are correct my code is wrong, i need to update it
one more simple solution is to just iterate from 1 to 1 to 1e8 . as only few of them would form the permutation it is feasible ,but this approach of generating palindromes is much optimized though.
This would not pass we have 1e5 test cases also
we would be precomputing then answer each in O(logn)
If we run it till 1e8, the max palindrome we would get will be lesser than 1e17
it would be half of the number 1e15 is 15 digits 1e8 has 8 digits. For every number, if possible, there are some it would take some constant factor of 20 or more. but compiler will optimize the for loop so it did work fast in my system idk about the OA
Can you share your code pls
Auto comment: topic has been updated by Don_quixxote (previous revision, new revision, compare).
The second problem's code is incorrect. What you can do is ---- generate all bitmasks, then generate all permutations of said bitmask's size, if it's a valid bitmask. Create a multiset out of the valid digits. So, assuming all 9 digit nos, you have 512 * 9! permutations in total, which is admittedly pretty high, but actual time complexity will obviously be far far lower, infact of the order of actual valid "special palindromes".
I think no.of ways to arrange will be for half length, (total_digits) !/ (product of factorial of frequency)!. Let's say we want palindrome containing 2 and 4, total ways = 3!/(2!*1!) = 3 (424, 244, 442). So to say 9! ways exist is not correct, imo. In worst case (all included), it will be equal to, 45!/(1!*2!...*9!), idk how much this is or will this pass or not.
you're not passing it if it's more than 9 digits. So, what you're doing is --> generate bitmask -- check if valid (cnt <= 18, no of odd vals <= 1).
in this scenario, you get a multiset with <= 9 digits in all instances. moreover, the uniqueness factor will automatically take care of itself. now simply iterate over all permutations of this multiset, and you have valid nos. all such valid nos will create your collection of special permutations!
TRY THIS CODE. ofc, not including the binary search too, just the generation of "Special Palindromes"
The code looks fine, thanks.
could somebody suggest the best resource to practice these type of questions?
You can go through past oa of different companies, there are multiple websites like joboverflow, desi qna, learnyard...
Auto comment: topic has been updated by Don_quixxote (previous revision, new revision, compare).
(Will improve my explanation later when I get time) For problem 2,
Assume there are 2N digits i.e. the number of digits are even. For i=0...N-1, I will try to create a special palindrome by only changing the digits in the range [N-i,N+1+i] where the digit at position N-i is greater than in the originally provided number. When I find an answer, I will stop as this is the best answer.
Let's fix the value of i. The best answer should have the smallest possible increase in digit value at position N-i followed by as low of digits as possible. We can find if a solution exists using a slightly modified 0/1 knapsack. There are some digits we already need to place in the range [N-i,N+i+1] because that digits occurs outside the range but not the required amount of times. Once you know the amount of digits you can decide upon, run a knapsack on all the even digits that aren't already present in the number with the requirement that at least one of the digits added are >= the digit at position N-i. If you are required to add a digit that is >= the digit at position N-i, you can ignore this requirement.
If you have a knapsack solution, that means you do have a solution. Make sure to keep track of a "parent" vector so you can backtrack to get to a valid answer. How do we perform the knapsack in a way that gives the optimal solution? You should be able to do this by modifying the order in which you add elements. If the >= condition is already satisfied you can just go in decreasing order while overriding the parent vector whenever you get the opportunity. Otherwise, say j is the digit at position N-1. Add all elements less than j in decreasing order, overriding the parent vector whenever you get the opportunity. Then do all elements greater than j in decreasing order, only overriding the parent vector when this is the first visit or if it the end position. The path back using the parent vector should tell you the numbers to use. Simply choose the smallest number greater than j to use first and then build as small as possible using the numbers given to you by the knapsack.
This runs in $$$O(log(N)^2)$$$ I believe.
Won't it TLE, with t = 10^5??
I think you would be right if it were $$$O(\log(N)^3)$$$ which I previously claimed. It's actually $$$O(D\log(N)^2)$$$ where D is the base (10). I would expect this to AC because of low constant factors.
I haven't counted how many special palindromes actually exist here. If it is low enough to actually generate them all, that is probably a better solution. This solution however works for incredibly big N and large bases.
My code says around 7k special palindromes. I'll read your soln again, thanks!