3XN Tilling Problem

general
, ,
1

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

2

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.

:raised_hands: Cheers!

3

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

4

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

6

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 :rofl:).

tile
tile1153×471 1.05 KB

and you can Trust me (I got AC) :wink:

1 Like
7

Thanks to you and your MS paint skill :slight_smile:

1 Like