https://www.codechef.com/problems/FILLBOX

Answer would be : ans = (k-1)*(n-4) + (k-1)*(k-2)+(k-2)

As far as I can see, there’s no closed form answer. Your answer is incorrect as the answer depends on whether p=q. I think the answer is exponential in N, and not polynomial in N. If you want to do it faster, there’s a pretty obvious matrix expo solution.

https://www.codechef.com/viewsolution/31960134

Edit : Actually maybe there is

if p=q

ans=\frac{(k-1)^{n-1} + (-1)^{n-1}(k-1)}{k}

else

ans=\frac{(k-1)^{n-1} + (-1)^n}{k}

Hi, thanks for the quick reply. i just made the typo error in mentioning the answer, i wanted to keep (n-4) term in the power and obviously that would be applicable for n>=4 for any p and q, for n==3 (here p==q matter) there won’t be as much cases, we could simply write down those cases in if statements. K=2 is one the case that i need to handle otherwise.(Thats what i thought)

Could you explain how did you get to this final equation?

I didn’t really do it mathematically.

Firstly, let set the first one to P. Completely ignore Q for the time being.

At each step, we have to choose some value that’s not the previous one, so the total number of ways gets multiplied by k-1. Over time, the effect of P should fade out, So our general template for the answer is

(k-1)^{n-1}/k. Now calculate the answer * k - (k-1)^{n-1} for a few values, and you get the error term.

I put these values in my first code

```
5
3 3 2 3
4 3 2 3
5 3 2 3
6 3 2 3
7 3 2 3
```

And I got

```
-1
1
-1
1
-1
```

I tried for a few more k, and it didn’t depend on k

So obviously the answer when p\neq q

((k-1)^{n-1} + (-1)^{n})/k

Now there are cases k-1 cases where p\neq q

So the answer for p=q is

Total cases - (k-1)* answer when p!=q

(k-1)^{n-1} - (k-1) \frac{(k-1)^{n-1} + (-1)^n}{k}

=(k-1)^{n-1} - \frac{(k-1)^{n} + (k-1)(-1)^n}{k}

= \frac{k(k-1)^{n-1} - (k-1)^{n} - (k-1)(-1)^n}{k}

= \frac{(k-1)^{n-1} + (k-1)(-1)^{n+1}}{k}

And we got our answers.