×

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:

REFERENCES:

This question is marked "community wiki".

1243837
accept rate: 0%

19.8k350498541

1

(14 Jul '12, 18:06) 2★
1
(17 Jul '12, 17:06) 6★

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

(17 Jul '12, 19:09)

 5 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à! answered 25 Sep '12, 21:09 6.7k●62●119●138 accept rate: 12% good job ... (27 Sep '12, 12:38)
 1 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? answered 11 Jul '12, 18:34 4★shubh09 117●1●7 accept rate: 0% I think that's because you used 3 inner loops for multiplication... (11 Jul '12, 18:41) 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)
 1 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. answered 17 Jul '12, 19:08 16.9k●49●115●225 accept rate: 11%
 0 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. answered 11 Jul '12, 21:40 2★alphanso 1●1 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) can u explain this eqn ??? how does it work ??? (25 Sep '12, 15:59)
 0 What would you do if one of the elements of the constructed matrix is negative?? Would u take the mod directly?? Plz reply... answered 05 Sep '12, 12:58 20●2 accept rate: 0%
 0 My code gives me tle error whats wrong with my code?? http://www.codechef.com/viewsolution/6317457 answered 19 Feb '15, 21:14 1●1 accept rate: 0% TLE is Time Limit Exceeded. Make your program execute faster (19 Feb '15, 21:33) arun_as1★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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