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.
If you actually want to know what I did
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.