You are not logged in. Please login at www.codechef.com to post your questions!

×

CSUMD - Editorial

8
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 :)

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:

This question is marked "community wiki".

asked 11 Jul '12, 16:02

yellow_agony's gravatar image

4★yellow_agony ♦♦
1243837
accept rate: 0%

edited 11 Jul '12, 18:00

admin's gravatar image

0★admin ♦♦
19.8k350498541

1

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

(14 Jul '12, 18:06) codejack2★
1
(17 Jul '12, 17:06) nihalpi16★

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

(17 Jul '12, 19:09) betlista ♦♦3★

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.

2) 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à!

link

answered 25 Sep '12, 21:09

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138
accept rate: 12%

edited 25 Sep '12, 21:10

good job ...

(27 Sep '12, 12:38) siddharthjh3★

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?

link

answered 11 Jul '12, 18:34

shubh09's gravatar image

4★shubh09
11717
accept rate: 0%

I think that's because you used 3 inner loops for multiplication...

(11 Jul '12, 18:41) betlista ♦♦3★

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?

(11 Jul '12, 19:41) shubh094★

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

(11 Jul '12, 19:53) betlista ♦♦3★

@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.

link

answered 17 Jul '12, 19:08

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

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.

link

answered 11 Jul '12, 21:40

alphanso's gravatar image

2★alphanso
11
accept rate: 0%

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

(12 Jul '12, 14:17) betlista ♦♦3★

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

(25 Sep '12, 15:59) siddharthjh3★

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

link

answered 05 Sep '12, 12:58

nitish712's gravatar image

4★nitish712
202
accept rate: 0%

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

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

link

answered 19 Feb '15, 21:14

clonegamer's gravatar image

0★clonegamer
11
accept rate: 0%

TLE is Time Limit Exceeded. Make your program execute faster

(19 Feb '15, 21:33) arun_as1★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,639
×3,746
×285
×116
×13

question asked: 11 Jul '12, 16:02

question was seen: 7,979 times

last updated: 19 Feb '15, 21:33