I am stuck at the problem. not able to think bout the approach.
Help needed!!
First tell us what you have tried. What previous values do you think are important?
1 Like
The day and the last 2 activities ,ig.
Close enough. Only the last activity matters. So for each day, we have to find the maximum for A done last, B done last, and C done last.
What do you think will be the dp relation then?
In case you don’t understand why only last, Think of the following
BA - 20 points
CA - 30 points
Is there any possibility that would make BA better than CA?
Is there any possible next value that will be allowed for BA but not for CA?
what if AA-40 points?
As Taro gets bored easily, he cannot do the same activities for two or more consecutive days.
However, If you misinterpreted the Question, and thought more than 2 days, Your previous Dp state was correct.
Sorry for the inconvenience. I misinterpreted the question.
In case of more than 2, I thought that for i’th day and jth activity, I would first get the maximum of dp[i-1] ( for all the cases except jTH activity for the last 2 days) and then add a[i][j].
Am I on the right way??
Yes, but it can be optimised a little more. If it was not more than k days, and you have m choices, your algorithm works in O(m^k n), but it can be done it O(mkn). Remember the main question to ask is what reallly matters.
spoiler
Just store which choice was last, and how many times it has been consecutively chosen already.
Thank you!! 
I need some help in this too.
i thought about storing number of ways to distribute x candies, but couldn’t find out how to play with the maximum candies one can have.
Let dp[i][j] denote the number of ways to distribute j candies to the first i people. Now since we can give any number of candies from 0 to a_i to this person
dp[i][j] = dp[i-1][j] + dp[i-1][j-1]+ \dots+ dp[i-1][j-a_i] \\= \sum_{k=0}^{a_i} dp[i-1][j-k]. We can calculate this sum quicker if we find the prefix sums from before.
Thanks for helping!!
I wrote this but got 4/16 WA, rest were AC.
Can u take a look once?
#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
int MOD=1e9+7;
signed main()
{
faster;
{
int n,k;
cin>>n>>k;
int a[n+1];
for (int i=1;i<=n;i++)
cin>>a[i];
long long dp[n+1][k+1];
long long pre[n+1][k+1];
for (int i=0;i<=n;i++)
for (int j=0;j<=k;j++)
dp[i][j]=0;
for (int i=0;i<=a[1];i++)
dp[1][i]=1;
pre[1][0]=dp[1][0];
for (int i=1;i<=k;i++)
pre[1][i]=(pre[1][i-1]+dp[1][i])%MOD;
for (int i=2;i<=n;i++)
{
for (int j=0;j<=k;j++)
{
int x=max(j-a[i],0);
if (x>0)
dp[i][j]=pre[i-1][j]-pre[i-1][x-1];
else
dp[i][j]=pre[i-1][j];
}
pre[i][0]=dp[i][0];
for (int j=1;j<=k;j++)
pre[i][j]=(pre[i][j-1]+dp[i][j])%MOD;
}
cout<<dp[n][k];
}
}
try assert(dp[n][k]>=0 && dp[n][k]<MOD);
Just in case you didn’t know, assert will produce a runtime error if the condition is not satisfied.
In 2 TC dp[n][k]<0.
The other 2 got accepted.(printed dp[n][k]%MOD) but I did the modulo while calculating prefix sum. I didn’t understand why do I need to do modulo at the last.
thanks for assistance.
1 Like
If dp can become negative, so can prefix sum, and you are subtracting a negative value so dp[n][k] may become larger than mod, but lesser than 2*mod.
Got the error.
for (int j=1;j<=k;j++)
pre[i][j]=(pre[i][j-1]+dp[i][j])%MOD;
pre should be exact and modulo should not be done.
let us assume pre[i][j-1]=10e9+6 and dp[i][j]=2;
then according to the above mentioned eq., pre[i][j]=1 But it should be 10e9+8.
Thanks!!
Doing that also fixes the answer(assuming you put a %mod in your dp calculation), but both 10^9 + 8 and 1 are equivalent. it’s not wrong, but you may have intermediate negative values, which isn’t really a problem. You could do cout<<(dp[n][k]%mod + mod)%mod<<"\n"; and that will normalise the value to the correct range at the end.
Got it. Thanks!