Hi,
I can’t understand why my code is not giving AC for k = 3 subtask.
Please point out where i am getting it wrong.
Problem : https://www.codechef.com/INOIPRAC/problems/INOI2002
Code : https://www.codechef.com/viewsolution/41721110
Thanks in advance
Consider this test case --> k = 3 n = 3
dp[3] = dp[3-1] + dp[3-3],
= 1
This what your code would do...
While the answer is 2 ( using all vertical or using all horizontal tiles)
So what you’re missing is, when k = 3, we can actually tile the upper row or lower row first and now what we’ve is identical to k = 2.
Thus the one more statement to add would be
If upper & bottom rows are tileable by horizontal tiles i.e. n divisible by 3 & k==3.
dp[3, i ] += 2*dp[ 2, i ] - 1,
subtracted 1 so that we don't count the way when we use only horizontal tiles t
twice because they're alike as in the example above.
.
Well, that’s it I guess… I haven’t solved it yet or seen before it, so can’t say if anything else is missing ( although I am highly confident that everything else is fine) but for sure this was something that was missing…
Let me know if it helps or if something wasn’t clear.
Cheers!
and yes don’t wait for the value to get large before taking modulo rather add and modulo simultaneously like this, dp[i] = (dp[i-1]+dp[i])%M, dp[i] = (dp[i-3]+dp[i])%M
Pls look carefully,
In case of n=3 and k=3,
dp[3] is intially 1.
So dp[3] = 2.
.....
}else if(k == 3){
dp[1] = 1LL;
if(n >= 3) dp[3] = 1LL;
if(n >= 6) dp[6] = 2LL;
}
.....
Thanks
You assumed that 2*2 tile can only be used as a triplet
line 43 in your code :-
if(i >= 6) dp[i] += (2*dp[i-6]);
Now check for n=9…
your code gives 31 while answer is 35 due to the above reason
Here is one of those 4 (thanks to my MS paint skills, Lol
).
and you can Trust me (I got AC) 
1 Like
Thanks to you and your MS paint skill 
1 Like