https://www.codechef.com/viewsolution/29206915
I just implemented the matrix exponentiation approach.
Why this got TLEād for both the subtask?
Thank you!
Actually , f(n,1) is not only the no of sequence of length n having last two element different
but also any three element consecutive element in the sequence is not equal .
this type of sequence can be constructed by (n-1 length sequence of same type and filling the nth position in m-1 ways so that any three element consecutive element in the sequence is not equal also f(n,1) can be constructed from f(n,2) type in similar way)
hence f(n,1) = (m-1)*(f(n,1) + f(n,2))
similarly f(n,2) = f(n-1,1).
1 Like
I used the recurrence
dp[i] = (m-1)*(dp[i-1]+dp[i-2])
it is giving TLE in big caseā¦
https://www.codechef.com/viewsolution/29215921
\begin{bmatrix}
m^2 - m & m-1 \\
m-1 & 0
\end{bmatrix} * \begin{bmatrix} m-1 & 1 \\ m-1 & 0\end{bmatrix}^{n-2}
This is your answer. This works because ā¦
\begin{bmatrix}
dp[i] & dp[i-1] \\
dp[i-1] & dp[i-2]
\end{bmatrix} * \begin{bmatrix} m-1 & 1 \\ m-1 & 0\end{bmatrix} = \begin{bmatrix} dp[i] * (m-1) + dp[i-1] *(m-1) & dp[i]*1 + dp[i-1] * 0 \\ dp[i-1]*(m-1) +dp[i-2] * (m-1) & dp[i-1]\end{bmatrix} = \begin{bmatrix} dp[i+1] & dp[i] \\ dp[i] & dp[i-1]\end{bmatrix}
this forms a recursive. Matrix exponentiation can be done in log n time using the same method as normal modular powers.
1 Like
Glad to hear that 
If there are no three consecutive positions having same element in a sequence, there cannot exist four or more consecutive positions with same value.
Yes I did same, but it still is giving TLE. I think it is because I am using vector instead of martrix. I used same algo for matrix and it gives ac. But for vector it is giving tle
I just wrote an iterative solution of same, and it manages to pass both cases
here: https://www.codechef.com/viewsolution/29217940
According to my very limited knowledge I am guessing it is due to recursion and memory allocation for temp array in each call leads to TLE.
1 Like
Can anyone suggest how to use combinatorics and get an answer in terms of m for n=4??I am able to get answer as m^4 - 2m(m-1)
1 Like
rightly saidā¦
very badly written question in round!! no explanation of input output is given!!!
Can you explain how did you came across this recurrence?
Can somebody please tell me why my code is not working? I have tested on some of my test cases but it fails on the system test case. Thanks for your help.
Here is the line: #include <bits/stdc++.h>using namespace std;#define ms(x, t) memset(x, t, si - Pastebin.com
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector vl;
const int mod = 1e9 + 7;
vector matI(int n) {
vector I(n, vl(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
I[i][j] = 1;
}
}
return I;
}
vector matMul(vector &a, vector &b) {
ll n = a.size();
ll m = b[0].size();
ll l = b.size();
vector c(n, vl(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < l; k++) {
c[i][j] = (c[i][j] + (a[i][k] % mod * b[k][j] % mod) % mod) % mod;
}
}
}
return c;
}
vector matExp(ll n, vector &a) {
int m = a.size();
vector ans = matI(m);
while (n) {
if (n & 1) {
ans = matMul(a, ans);
}
a = matMul(a, a);
n = n >> 1;
}
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin >> t;
while (tā) {
ll n, m;
cin >> n >> m;
// vector<vl> y = {{1, 2, 3}, {4, 5, 6}, {2, 1, 3}};
// vector<vl> z = {{1, 2}, {4, 5}, {2, 1}};
// vector<vl> e = matMul(y, z);
// for (auto x : e) {
// for (auto y : x) {
// cout << y << " ";
// }
// cout << endl;
// }
vector<vl> p = {{m - 1, m - 1}, {1, 0}};
vector<vl> a = {{m}, {0}};
vector<vl> e = matExp(n - 1, p);
vector<vl> res = matMul(e, a);
cout << (res[0][0] + res[1][0]) % mod << endl;
}
return 0;
}
I followed the recursive approach for this problem as mentioned but still couldnāt pass subtask 1, pls help me find the mistake in my code
#include <bits/stdc++.h>
#define modulo 1000000009
using namespace std;
int f(int n, int m,int val){
if(n==1){
if(val==1)
return m% modulo;
else
return 0;
}
if(val==1){
return (((m-1)%modulo)*((f(n-1,m,1)+f(n-1,m,2))))%modulo;
}
if(val ==2){
return f(n-1,m,1)%modulo;
}
}
int main() {
int t;
cin>>t;
while(tā){
int n, m;
cin>>n>>m;
int count=f(n,m,1)+f(n,m,2);
cout<<count<<endl;
}
}
somebody help me to resolve the problem.I had done exactly same as described in the editorial
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<vector>& matrix;
ll mod=1e9+7;
void multiply(matrix A,matrix B){
ll n=A.size();
vector<vector>temp;
temp.resize(n);
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
ll sum=0;
for(ll k=0;k<n;k++){
sum+=A[i][k]*B[k][j];
sum%=mod;
}
temp[i].push_back(sum);
}
}
for(ll i=0;i<n;i++) for(ll j=0;j<n;j++) B[i][j]=temp[i][j];
return;
}
void power(matrix mat,matrix res,ll k){
if(k==0) return;
if(k==1){
ll n=mat.size();
for(ll i=0;i<n;i++) for(ll j=0;j<n;j++) res[i].push_back(mat[i][j]%mod);
return;
}
power(mat,res,k/2);
multiply(res,res);
if(k&1) multiply(mat,res);
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin>>t;
while(tā){
ll n,m;
cin>>n>>m;
if(n==1){
cout<<m%mod<<"\n";
continue;
}
vector<vector>mat{{m-1,m-1},{1,0}},res;
res.resize(2);
power(mat,res,n-1);
ll ans=(res[0][0]+res[1][0])%mod;
ans=(ans*m)%mod;
cout<<ans<<"\n";
}
return 0;
}
Yes sure,
Let f(i) be the count of valid array of length i, then there will be two cases
(i) either arr[i-1]==arr[i-2]
then at ith position we have m-1 choices along with string of length i-3.
which will be equal to f(i-3)*(m-1)
(ii) or arr[i-1]!=arr[i-2]
here we have no restrictions so this will be f(i)*m
finally, f(i) = f(i-1)m + f(i-3)(m-1)
I am not sure whether my solution is correct or not, This is what i came up with during the contest.
1 Like
I think you are using inclusion -excluson principle which is giving wrong results
try n=5 and m=8 which is giving 31352 but answer is 31360
You used too much modulo operations.
I came across the same recurrence canāt comprehend how to solve this in log (n) ;/.