ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1513. Lemon Tale

Explain why my sol is incorrect
Posted by Mahilewets 21 Apr 2017 18:24
I have implemented the following thing.
There are two arrays:
dp1[j] and dp2[j].
It contains count of such sequenses that they end at exactly j lemons.
dp1[0] is always 1.
dp1[1] is 1 iff K>0.
There is a loop from i=2 to N.
On the j-th iteration I calculate answer for length j.
But it does not works at all!!
And I do not have any clue why.
Help me understand why.

#include <stdio.h>

int main(){
unsigned long long dp1[10001];
unsigned long long dp2[10001];
for(int j=1; j<=10000;++j)
dp1[j]=0, dp2[j]=0;
dp1[0]=1;
dp2[0]=0;
int N,K;
scanf("%d %d",&N,&K);
if(K>0) dp1[1]=1;
for(int j=2;j<=N;++j){
for(int k=1; k<=K && k<=j;++k)
dp2[k]=dp1[k-1];
for(int k=0; k<=K && k<=j-1;++k)
dp2[0]+=dp1[k];
for(int k=0; k<=K && k<=j;++k)
dp1[k]=dp2[k];
}
unsigned long long ans=0;
for(int k=0; k<=K ;++k)
ans+=dp1[k];
printf("%llu",ans);
return 0;
}
Re: Explain why my sol is incorrect
Posted by Mahilewets 20 May 2017 17:53
It was because I didn't update dp2.
Re: Explain why my sol is incorrect
Posted by Mahilewets 20 May 2017 18:34
Very cute problem!
My code was TERRIBLE.
I completely rewrote it and got AC 0.2 seconds with Python3.