[Community Puzzle] 3×N Tiling


#1

https://www.codingame.com/training/medium/3n-tiling

Send your feedback or ask for help here!

Created by @CyberLemonade,validated by @R2B2,@damiengif and @JBM.
If you have any issues, feel free to ping them.


#2

I cannot pass 3xN intermediate test case, it fails on 3x12
My logic is:
dp[i] = (dp[i-1] + (i >= 3 ? dp[i-3] : 0) + (i >= 6 ? dp[i-6] * 2 : 0))%mod
it should return 154 but mine return 124, any idea?


#3

You are missing some options that become available at 3x9 (think about whats possible in 2x9 - thats always possible in 3x9 too as you can just add a line of flat length 3 blocks on top of it).


#4

@RoboStac thanks for the response, I managed to get some logic right. This is what I have now:

dpHeight1[0] = 1//height = 1
dpHeight2[0] = 1//height = 2
dpHeight3[0] = 1//height = 3

for (int width=1; width <= n; width++) {
    //take out one 1x3
    dpHeight3[width] = (dpHeight3[width-1])%mod
    
    if width >= 2 {
        dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-2])%mod
    }
    
    if width >= 3 {
        //put 1 time 3x1
        dpHeight1[width] = (dpHeight1[width] + dpHeight1[width-3])%mod
        
        //put 2 vertically stacked 3x1
        dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-3])%mod
        
        //take out 3 vertically stacked times 3x1
        dpHeight3[width] = (dpHeight3[width] + dpHeight3[width-3])%mod
        
        //take out 1 time 2x2 and put it on top of 1 time 3x1
        // or take out 1 time 3x1 and put it on top of 1 time 2x2
        dpHeight3[width] = (dpHeight3[width] + 2 * (dpHeight2[width-2] * dpHeight1[width-3]))%mod
    }
}

Looks like still not quite there, can you please advise what I’m still missing?
Failing on the same testcase:
beyond intermediate 3xn is failing, e.g. 3x12 should be 154 mine is 98.
Any help is really appreciated, have stuck on this for days :frowning_face:
Thanks


#5

For N*3 Intermediate I have found a recurrence relationship, but it seems not right… f(4) = 3 but my relation gives f(4) = 4 with f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2.

I’m kinda lost from now, did I made an obvious mistake ?

f(n) = f(n - 1) + f(n - 3) + 2 * g(n - 3)
g(n) = h(n) + g(n - 3)
h(n) = f(n) + h(n - 3)

I start to compute it from 4 but the result is obviously wrong


#6

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)