Sports Fest : Multi DP

#1

My code is giving correct output for the sample test-case but fails to pass all the test cases.
Kindly the the issue.
IDE : https://ide.codingblocks.com/s/202750

#2

IDE : https://ide.codingblocks.com/s/202751

#3

@aman2382000 the code you have is of some other problem ,please provide the code for this problem

#4

IDE : https://ide.codingblocks.com/s/202751

#5

@aman2382000 You are using an array of size 100 when possible value of n is 10^5.
Also Your DP relation is not correct.
let dp[n][3] be our DP array,
d[i][0] // C will be played on i
dp[i][1] // F will be played
dp[i][2] // H will be played on day

Now DP relation would be.
for i>2 (0 indexed)
dp[i][0] =d[i-1][0]+d[i-1][1]+d[i-1][2];
dp[i][1]=dp[i-1][0] + dp[i-1][2];
dp[i][2]= dp[i-3][2]*3 + dp[i-3][1]*2 + dp[i-3][0]*3

For i<=2 (fill them manually (can be done easily))
Now total number of ways for would be sum of dp[n-1][0]+dp[n-1][1]+dp[n-1][2]

Coefficients for the dp[i][2] relation are derived as follow, suppose we have H at i-3 now we need to fill 2 slots, can be done as CC, CF, FC 3 ways, if we have F at i-3 we can have CC, CF, if we have C at i-3 we can have CC, FC, CF
If this resolves your doubt mark it as resolved.

#6

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod=1e9+7;

int32_t main() {
int n;
cin>>n;
if(n==1){
cout<<“3\n”;
}else if(n==2){
cout<<“7\n”;
}else if(n==3){
cout<<“15\n”;
}else{
int dp[n][3];
dp[0][0]=1;
dp[0][1]=1;
dp[0][2]=1;
dp[1][0]=3;
dp[1][1]=2;
dp[1][2]=2;
dp[2][0]=7;
dp[2][1]=5;
dp[2][2]=3;
for(int i=3;i<n;i++){
dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%mod;
dp[i][1]=(dp[i-1][0]+dp[i-1][2])%mod;
dp[i][2]=((((dp[i-3][0]+dp[i-3][2])%mod)*3)%mod+(dp[i-3][1]*2)%mod)%mod;
}
int ans=(dp[n-1][0]+dp[n-1][1]+dp[n-1][2])%mod;
cout<<ans;
}
return 0;
}

#7

@ardhendureja1999 very good approach …please teach me dp

#8

#include<bits/stdc++.h>
#define int long long
using namespace std;
int mod = 1e9+7;
int n;
int dp[100001][5][5];
int way(int i ,int f , int h)
{
if(i>=n) return 1;
int &ans = dp[i][f][h];
if(ans != -1) return ans ;

if(f==0)
{
	if(h==0)// all possible cases c+f+h
		ans = (way(i+1,0,0)+way(i+1,1,0)+way(i+1,0,1))%mod;
	else   //c + f
		ans = (way(i+1,0, (h+1)%3) + way(i+1,1,(h+1)%3))%mod;
}
else if(f==1)//football kheleche ager din
{
	if(h==0) //    c        +     h
		ans = (way(i+1,0,h) + way(i+1,0,h+1))%mod;
	else  // only c
		ans = (way(i+1,0 ,  (h+1)%3 )  )%mod;
}
return ans ;

}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<=n;i++)
for(int j=0;j<5;j++)
for(int k=0;k<5;k++)
dp[i][j][k] = -1;

if(n==1)
	cout << '3'<<'\n';
else if(n==2)
	cout << "7\n";
else
	cout <<way(0,0,0);

return 0;

}

1 Like