DMCS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Ke Bi
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra

DIFFICULTY:

Hard

PREREQUISITES:

linear recurrence, matrix exponentiation

PROBLEM:

Given a chocolate of size 2 * 2 * 2 * 2 * n. Find out number of ways of breaking it into 8 n small pieces, each of size 1 * 1 * 1 * 1 * 2.
Print the answer modulo 10^9 + 7.

EXPLANATION:

Think about a smaller problem
Let us first solve version of this problem in lower dimension. Let us fix chocolate size = 2 * n and piece size = 1 * 2.
Let dp[i][mask] denote the number of ways of breaking the chocolate up to coordinate i (in 2nd dimension) and where mask denote the configuration of last row.
Here as a single row will contain 2 elements, so mask will have total (1 << 2) possible values.
We can obtain a recurrence for dp by trying to fill the mask in all possible ways and making transitions to next state.

Now, we can note that dp[i][mask] is dependent on dp[i - 1][mask’]. We can represent this relation by a constant matrix of size 2^2 * 2^2.
So, we can find dp[n][mask = (last row is full)] by matrix exponentiation.

Extending to higher dimenstion
Now in case of higher dimension, the mask will be 2^(16) as a row will have dimesion 2 * 2 * 2 * 2.
Also, we can obtain the transitions in the similar way.
Now, the size of matrix will be 2^16 * 2^16 which is too huge to apply the matrix exponentiation algorithm.

We can make a few observations to reduce the number of states.
We note that some of the configurations (masks) of last row are equivalent or some of them are useless (can never lead to a solution).

  1. Some of them are same w.r.t reflection and rotation.
  2. If there are a odd number of 1s in the state, the dp value of it must be 0.
  3. We can color it like chess board.If the number of black cells with 1s is not equal the number of white cell with 1, the dp value of it must be 0.

After these modifications, number of states will reduce dramatically, (around 561, see author’s solution for details of implementation of this).
Now the time complexity will be around 561^3 log(10^9) per test case, which will lead to TLE.
We need to optimize this.

Linear recurrence
We can notice that matrix is a constant matrix (independent of input n).
So, we can write a linear recurrence for this in the following way
f[n] = coef[1] f[n - 1] + coef[2] f[n-2] + … + coef[561] f[n - 561].
where each coef[i] is a constant.

Finding simplest recurrence relation
Now, if we could find f[n] dependent on last few terms rather than the current (i.e. 561).
So, let us say that we have a sequence of 561 numbers f[1], f[2], f[3], …, f[561].
So, for a given sequence, we need to know the smallest n for which a linear recurrence relation could be obtained.

A method by gaussian elimination
Let us say that we have a sequence 1, 2, 3, 11, 18, 53, 105

Now, we want to check whether this sequence is a 2-recursive formula (i.e. f[n] depending on previous 2 values f[n - 1], f[n - 2]).

We take a look at the Determinant
1 2 3
2 3 11
3 11 18

Det[{{1, 2, 3}, {2, 3, 11}, {3, 11, 18}}]
The value of the Determinant is not zero, which means it does not have a 2-recursive formula.

Now, let us check whether this is a 3-recursive formula.

Det[{{1, 2, 3, 11}, {2, 3, 11, 18}, {3, 11, 18, 53}, {11, 18, 53, 105}}]

The Det is 0.

Therefore, this has a 3-recursive formula.

So, in general for checking whether a formula is k recursive,
we need to make a determinant of following kind

f[1] f[2] … f[k]
f[2] … f[k + 1]
f[3] … f[k + 2]
.
.
f[k] … f[k + k - 1]

So, we will need to 2 * k values of function f.

For, our problem we get value that formula is 71-recursive formula.
So, we obtain these coefficients using gaussian elimination method used for calculating the previous determinant.

Now, each test case can be solved in O(71^3 log N) per test case.

We can calculate value of f[1], …, f[71 * 2] using the slow method discovered earlier and use it to calculate the desired coefficients.

Another solution using Cayley-Hamilton theorem
Given a recurrence relation of type f[n] = coef[1] f[n - 1] + coef[2] f[n-2] + … + coef[k] f[n - k],
we can find f(n) in O(k^2 log n).

You can see this link for details.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

2

Easy-medium? ~_°

And there’s a faster solution. We know that the answer for N is v_N[1] for a vector v_N=A^N v_0; here, A is a matrix M\times M and v_0=(1,0,0,\dots,0). We can precompute powers of A, which allows us to get from v_N to v_{N+2^k} for any k in O(M^2) time - it’s just multiplication matrix * vector. Therefore, we can get any v_N in O(M^2\log{N}) time, which is the time per test case (take M=93 or M=73 or something).

2 Likes
3

Just out of curiosity, would a 93^3log(n) per test case pass?

1 Like
4

My soultion was simmilar to yours with M=93!
For solving it in O(M^2logN) one may refer to this article: https://discuss.codechef.com/questions/49614/linear-recurrence-using-cayley-hamilton-theorem

1 Like
5

This was a fun problem. Probably the most fun I have had on codechef, my approach was a bit different though.

First off, we were told that for n = 1 the answer was 272. I was quite confused of course as to how that answer came about. But what was more peculiar was we weren’t told the answer to any other cases. Which convinced me that another value would shed some light on this mystery.

So instead we consider the problem of 2-d, that is a 2xn chocolate with 1x2 (and 2x1) parts. The answer here for n = 1 is 1.
For the 3-d 2x2xn with 1x1x2 parts and n = 1, the answer will be 2.
For the 4-d problem, it is 9.
And as we have been told for the 5-d problem, it is 272.

So, here we are creating a sequence of answers for the k-d problem with ans = 1. So far we have:

1, 2, 9, 272

Plug that into oeis and you will get this: https://oeis.org/A005271

Which tells you that the answer for the 6-d variant and n = 1 is 589185.

We of course don’t need that, 5-d is quite enough as it is, but more importantly, the 5-d n = 2 answer is the same as 6-d n = 1. In general the k-d variant n = 2 answer is the same as (k + 1)-d’s n = 1 answer.

Now we have the answer to n = 2 as well. We go back to oeis and plug in the two values (272, 589185) and get

https://oeis.org/A028467

Which is precisely what we need. The number of perfect matchings on a Q4 x Pn graph. I was a bit miffed I didn’t recognize it on my own, but was happy enough that I found it anyway.

Now we go through several papers referenced in there, find some mathematica code and arrive at a 93x93 recursion matrix, which of course gives a TLE. I managed to snag a 30 point AC though.

I tried several things to fix this. None of which worked.

Eventually I realized that I was performing about 30k 93^3 operations, which is a bit much.

30 precomputation for each power of two coupled with upto 30 again for each of the 1000 queries. I decided to use base 178 (found while trying to minimize number of multiplications) instead of base 2 for the matrix multiplication. It increased my precomputation to about 800, but per case multiplication went down to 4 at max. Leading to about 4.5k multiplications.

From 30k to 4.5k along with some optimized matrix multiplication I snagged from mugurelionut (Thanks bro) was enough to get that sweet sweet AC.

I see some people managed to do it without all this mumbo jumbo and in base 2 itself. But this was a fun trick to learn anyway for future use.

TL;DR: Had fun.

2 Likes
6

@grebnesieh … During the contest, i also went farther till this step https://oeis.org/A028467 .I then stucked at finding recurrence :confused:

7

This is probably the most time i have spent on codechef to solve a problem, Kudos to the problem setter for such an interesting problem!

My approach:
I started by trying out a dp of n * 2^16 * 2^16 on paper, relating dp[n][i] to dp[n-1][j] for all 0<=i,j<2^16

But all 2^16 masks are not distinct (due to symmetrical cases). we can rule out symmetric cases by trying all permutations and reflections of dimensions, leaving us with 402 masks, out of which, only 93 distinct ‘i’ gave non-zero dp[n][i] for all n.

So, in the end, we have a 93*93 matrix for a dp recursion, which can be solved using cayley-hamilton theorem, as given here .

Time complexity: T * 93^2 * log(n) + 93^4 (for pre-computation)

Submitted Solution

1 Like
8

Maybe it would TLE. This, however, may be helpful:

9

Interesting that editorial says there is still 561 states after the 3 observations, but with just the first two:

  1. Some of them are same w.r.t reflection and rotation.
  2. If there are a odd number of 1s in the state, the dp value of it must be 0.

I got 222 states, which was already fast enough (at least in c++). Wanted to go further and remove all the states that are always 0, but happened to not even need that.

10

I read the linked article about Cayley-Hamilton thorem,but I don’t understand how to get the first row of M^2, M^3, …, M^(k - 1) in O(k^2) time.Any help?

11

After these modifications, number of states will reduce dramatically, (around 561, see author’s solution for details of implementation of this).

Can’t see author’s solution.