CSUMD - Editorial

editorial
, , , ,
1

PROBLEM LINKS:

Practice
Contest

DIFFICULTY:

Simple-Easy

PREREQUISITES:

Linear Recurrences, Matrix Exponentiation

PROBLEM:

There are infinite coins of two types - of value 1 and of value 2. All coins have two sides - heads and tails. You’re to find out number of ways of arranging some coins such that their sum is equal to N (input) and the first coin is heads up.

QUICK EXPLANATION:

Let f(N) denote number of ways of arranging some coins such that their sum is equal to N and the first coin is heads up. Then it can be shown that f(N) = 2 (f(N-1) + f(N-2) ) with f(1) = 1 and f(2) = 3. Using matrix exponentiation, f(N) can be computed in time O(log N).

DETAILED EXPLANATION:

Let f(n, H) denote the number of ways of arranging coins such that their sum is
n, and the first coin is heads up. Similarly let f(n, T) denote the number of
ways of arranging coins such that their sum is n and first coin is tails up.

Our original problem is to find out f(n, H).

Here are our three claims:

  1. f(n, H) = f(n, T)

  2. f(n, H) = f(n-1, H) + f(n-1, T) + f(n-2, H) + f(n-2, T)

  3. f(n, H) = 2 * ( f(n-1, H) + f(n-2, H) )

Let’s see why each of these claims hold:

  1. f(n, H) = f(n, T)
    This is true because if we invert every coin of an arrangement with sum of n and
    first coin heads up, we get an arrangement with sum of n with first coin tails
    up. It is easy to see that it is infact a bijection. Hence the claim.

  2. f(n, H) = f(n-1, H) + f(n-1, T) + f(n-2, H) + f(n-2, T)
    This is the chief step of the problem : Let’s look at a particular arrangement
    with sum of n and first coin heads up. First coin is either of value 1 or of
    value 2. In first case, sum of remaining coins is n-1 and their first coin could
    be either heads up or heads down. f(n-1, H) + f(n-1, T) account for such case.
    In other case, when first coin is of value 2, sum of remaining coins is n-2 and
    they could either be heads up or tails up. f(n-2, H) + f(n-2, T) account for
    these. So total : f(n, H) = f(n-1, H) + f(n-1, T) + f(n-2, H) + f(n-2, T) holds.

  3. f(n, H) = 2 * ( f(n-1, H) + f(n-2, H) )
    This follows from claims 1 and 2 naturally :slight_smile:

Now we can drop H from the notation to get f(n) = 2 f(n-1) + 2 f(n-2) with base
case of this recurrence as f(1) = 1 and f(2) = 3. We can use matrix
exponentiaion to solve for this recurrence. For those of you who don’t know
this very useful technique, I’m providing a short description here itself.

Let’s write it in form of matrices:

[ f(n) f(n-1) ] = [ f(n-1) f(n-2) ] * | 2 1 |
                                      | 2 0 |

You can verify that this is nothing but the recurrence we just wrote. Special
property of writing it in this form is we [ f(n-1) f(n-2) ] is exactly of the
same form as [ f(n) f(n-1) ] and so we can in turn expand it to get:

[ f(n) f(n-1) ] = [ f(n-2) f(n-3) ] * | 2 1 | * | 2 1 |
                                      | 2 0 |   | 2 0 |

We can continue expanding term on right handside till we get :

[ f(n) f(n-1) ] = [ f(2) f(1) ] *   | 2 1 |^(n-2)
                                    | 2 0 |

We can do a matrix exponentiation in time O(log N) using repeated squaring. So
we can find out f(N) as well in O(log N) time as well. As we’ve to report final
answer modulo (10^9 + 7), we would do all operations modulo (10^9 + 7)

SETTER’S SOLUTION:

Can be found here.

TESTER’S SOLUTION:

Can be found here.

RELATED PROBLEMS:

Codechef- Chess Pushing Game
Codechef - Chef’s New Pet

REFERENCES:

5 Likes
2

Some of us had to use a one-dimensional vector to represent the matrix, because the same approach, when submitted with the matrix represented as a 2x2 vector gave TLE. Could someone provide an explanation for this?

1 Like
3

I think that’s because you used 3 inner loops for multiplication…

4

I think I am missing something here. How is that supposed to matter for a matrix of constant size? I did use 3 nested loops (each of the form for(i=0 to 1)) in my first approach, and none in the second, but the operations executed were about the same in both the cases - 8 additions and 8 multiplications in the first case, and 4 additions and 8 multiplications in the second one. Can 4 additions (and that too to 0), even if they might have taken place multiple times, affect the running time to such extent?

5

But that’s exactly what you did in your AC solution - removed loops…

It was just a tip, because I had similar problem - read here http://discuss.codechef.com/questions/654/digforst-even-setters-solution-got-tle-in-practice

6

I also did it in O(log N) with a different equation.

Y = N - 2

f(N) = f(N/2) * f(N - N/2) + f(Y/2) * f(Y - Y/2)

http://www.codechef.com/viewsolution/1159064

P.S. I think this equation can be derived from above equation.

7

in your code, there is calc(N / 2) * calc(N - N / 2) + 2 * calc(Y / 2) * calc(Y - Y / 2) :wink:

8

any good links/resource to know more about matrix exp.?

1 Like
9

Here’s one they gave in some editorial:
http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

1 Like
10

@codejack:

For me the most important thing to realize (about this method) was to know what is the purpose of matrix exponentiation, because I knew how to use it when I had the matrix, but didn’t know how to find such matrix.

Purpose is simple, when you have few last elements from sequence Fn and Fn-1 in this case, you want to generate new one - Fn+1 and keep the old one Fn (for further calculations).

So we are looking for some matrix

| A B |
| C D |

with property (it says, we want to replace oldest element Fn-1 with new one Fn+1)

| A B | * | Fn   | = | Fn+1 |
| C D |   | Fn-1 |   | Fn   |

If you know how matrix multiplication works, 2nd row is simple: C*Fn + D*Fn-1 = Fn => C = 1, D = 0

If you found the formula for Fn+1, 1st row is also simple: A*Fn + B*Fn-1 = Fn+1, from formula we know that A = 2 and B = 2.

Note: matrix I’m using is different from the one in editorial, but it works same way, you just need to know matrix multiplication.

1 Like
11

@codejack: I tried to describe it a little, you can ask if something is not clear :wink:

12

What would you do if one of the elements of the constructed matrix is negative?? Would u take the mod directly?? Plz reply…

13

can u explain this eqn ??? how does it work ???

14

Detailed explanation of approach by @alphanso.

At first let’s define new function g(N) which is equal to the number of ways of arranging coins with sum N but without constraint that the first one should be heads up. Clearly g(N) = 2 * f(N). So after finding g(n) we can find f(n) by multiplying it by (MOD+1)/2 modulo MOD = 10^9+7 (this number is a modulo inverse of 2 modulo MOD).

Now let’s prove the following general recurrence for g(n):

g(n) = g(k) * g(n-k) + 2 * g(k-1) * g(n-k-1),    1 <= k <= n-1

The proof will be purely combinatorial. Consider some sequence of coin values a(1), ..., a(L) with sum n. There are two independent case possible:

  1. Some prefix of our sequence has sum k:
 a(1) ... a(j)   a(j+1) ... a(L)
|-------------| |---------------|
    sum = k         sum = n-k

By the product rule and definition of g there are g(k) * g(n-k) such sequences.

  1. Some prefix has the sum k-1 while the next coin is 2:
 a(1) ... a(j)  2  a(j+2) ... a(L)
|-------------|   |---------------|
   sum = k-1         sum = n-k-1

(Note that if this prefix is followed by 1 then we are in the first case. Also since each a(j) is either 1 or 2 we can’t have any other cases.)

Here the number of sequences is 2 * g(k-1) * g(n-k-1). The multiplier 2 comes from the two possibilities to flip the middle coin with value 2.

Adding up these two values we get g(n), which finishes the proof.

Now choosing k equals to floor(N/2) we get the recurrence of @alphanso. This recurrence allows to find g(n) in O(log n) time without matrix multiplication. See his solution for details.

And now let’s put k=1 in this formula. Note that g(0) = 1 and g(1) = 2. Hence

g(n) = g(1) * g(n-1) + 2 * g(0) * g(n-2) = 2 * (g(n-1) + g(n-2)).

So we get the recurrence from the editorial. Voilà!

4 Likes
15

good job …

16

My code gives me tle error whats wrong with my code??

http://www.codechef.com/viewsolution/6317457

17

TLE is Time Limit Exceeded. Make your program execute faster