ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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.