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) ;/.
Could you explain what these statements do?
Thanks in advance.
relation will be
dp[i] = dp[i-1]m - dp[i-3](m-1) for i>3
Here is the video link where I have discussed the algorithm for this question in the best possible time complexity :- YouTube 
:
Please go through it and do like and share if u find it helpful 
1 Like