×

SIMPLE

# PREREQUISITES

Simple Math, Repeated Squaring

# PROBLEM

How many sequences of 0s and 1s (0 meaning a hug, 1 meaning a kiss) of length N are possible, such that after the first 1 appears at index i, every alternate index after i - formally, i+2, i+4, i+6 and so on - is also 1. Note that this constraint is forced only by the first 1 and no subsequent 1s.

# QUICK EXPLANATION

Suppose the sequence was to start with a 0, then all possible sequences of length N-1 are valid.

Now, if the sequence were to start with a 1, then every odd index in the sequence (assuming the sequence is 1-based) will be 1; the rest of the floor(N/2) indices can be either 0 or 1, mutually exclusively.

Thus we get the formula

f(N) = f(N-1) + 2floor(N/2)

Since N can be as much as 109 we cannot use this recursive formulation as it is.
The Explanation section below is about finding a closed form from the above recursive formula

# EXPLANATION

Seeing the floor function and division by 2 immediately gives us the insight that we should find the formula for odd and even N.

Let fo(N) and fe(N) be the functions that are defined for the odd and even values of N respectively. Thus,
f(N) = if N is odd then fo(N) else fe(N)

(1) ... fo(N) = fe(N-1) + 2(N-1)/2
(2) ... fe(N) = fo(N-1) + 2N/2

From (1) and (2) we can derive

(3) ... fo(N) = fo(N-2) + 2(N-1)/2 + 2(N-1)/2
(4) ... fe(N) = fe(N-2) + 2N/2 + 2(N-2)/2

Where,

fo(1) = 2
fe(0) = 1

These formulas are already very usable. We can use matrix exponentiation on fo(N) or fe(N) based on whether N is even or odd. But we can do a little better and find closed form formulas of fo and fe.

Let,

to(N) = fo(N) - fo(N-2) = 2(N-1)/2 + 2(N-1)/2 = 2(N+1)/2

to(3) = 22
to(5) = 23
to(7) = 24
...
to(N) = 2(N+1)/2

Adding all of the above gives us,

fo(N) - fo(1) =[n = 0 to (N+1)/2] 2n - 21 - 20
fo(N) - 2 = 2(N+1)/2 + 1 - 1 - 2 - 1 (summation of Geometric Progression)
fo(N) = 2(N+1)/2 + 1 - 2

Similarly, we want to find the closed form for fe.

Let,

te(N) = fe(N) - fe(N-2) = 2N/2 + 2N/2 - 1

te(2) = 21 + 20
te(4) = 22 + 21
te(6) = 23 + 22
...
te(N) = 2N/2 + 2N/2 - 1

Adding all of the above gives us,

fe(N) - fe(0) =[n = 0 to N/2] 2n - 20 + ∑[n = 0 to (N/2 - 1)] 2n
fe(N) - 1 = 2N/2 + 1 - 1 - 1 + 2N/2 - 1 (summation of Geometric Progression)
fe(N) = 2N/2 + 1 + 2N/2 - 2

Thus we can find the value of f(N) from the following two expressions
f(N) = 2(N+1)/2 + 1 - 2, for odd N
f(N) = 2N/2 + 1 + 2N/2 - 2, for even N

To further simplify the formula, you can rewrite the expressions for odd and even N as follows,

f(N) = 2(N+1)/2 + 2(N+1)/2 - 2, for odd N
f(N) = 2N/2 + 1 + 2N/2 - 2, for even N

Or,

f(N) = 2ceil((N+1)/2) + 2floor((N+1)/2) - 2, for any N

The value of 2n can be found by repeated squaring.

# SETTERS SOLUTION

Can be found here

# TESTERS SOLUTION

Can be found here

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

19.0k348495533

hey i am not able to submit my solution for this problem. i clicked problem and it took me to http://www.codechef.com/problems/CKISSHUG but neither the problem nor the submit button was present. plz help

(11 Sep '12, 18:50)

 0 http://www.codechef.com/viewsolution/1333458 Why this solution is incorrect. I used the same formula. answered 15 Sep '12, 18:50 1 accept rate: 0%
 0 How can solve it using Matrix Expo? What is the Dimension of matrix for this problem? answered 14 Oct '12, 23:53 1 accept rate: 0% Instead of all the analysis to find a closed form, you can use the equations for Fo or Fe based on whether N is even or odd. For example, the Fo equation can be implemented using a 2x2 matrix | Fo(k) 2(k+1)/2 | = | 1 2 | | 0 2 | * | Fo(k-2) 2(k-1)/2 |  (19 Oct '12, 05:06)
 0 Simple question ... i only used sum of G.P.(Geometric progression) and some extra calculation...That is very simple..https://www.codechef.com/viewsolution/10535671 answered 19 Jun '16, 16:36 2.8k●3●16 accept rate: 16%
 0 Now, if the sequence were to start with a 1, then every odd index in the sequence (assuming the sequence is 1-based) will be 1; the rest of the floor(N/2) indices can be either 0 or 1, mutually exclusively. I think this is wrong because the rest even indices must all be 1 after any one that is set to 1: i.e the rest of indices will be: 111..11 or 011..11 or 001..11 or .. 000..00 so there is: 1 + floor(N/2) possibilities not 2^floor(N/2) The correct recursive relation will be: Un = Un-1 + floor(N/2) + 1 which gives: U0 = 1 U1 = 2 Un = Un-2 + n + 1 which gives: U2k+1 = (k+1)(k+2) U2k = (k+1)^2 Please correct me if I am wrong. answered 20 May '17, 13:33 3★mamay 2●1 accept rate: 0%
 0 As per statement "she has a compulsion to necessarily kiss every alternate guest from that first kissed guest. That is if the guests are G1, G2, ..., Gi, Gi+1, ..., Gn and if she first kissed Gi then she must necessarily kiss Gi+2, Gi+4, Gi+6 ... till the last" that makes the editorial wrong if I get it right Ans should be 1 2 2 4 3 6 4 9 5 12 6 16 7 20 8 25 9 30 based on this 0 1 1 1 1 2 10 1 3 11 1 4 100 0 4 101 1 5 110 0 5 111 1 6 1000 0 6 1001 0 6 1010 1 7 1011 1 8 1100 0 8 1101 0 8 1110 0 8 1111 1 9 10000 0 9 10001 0 9 10010 0 9 10011 0 9 10100 0 9 10101 1 10 10110 0 10 10111 1 11 11000 0 11 11001 0 11 11010 0 11 11011 0 11 11100 0 11 11101 0 11 11110 0 11 11111 1 12 100000 0 12 100001 0 12 100010 0 12 100011 0 12 100100 0 12 100101 0 12 100110 0 12 100111 0 12 101000 0 12 101001 0 12 101010 1 13 101011 1 14 101100 0 14 101101 0 14 101110 0 14 101111 1 15 110000 0 15 110001 0 15 110010 0 15 110011 0 15 110100 0 15 110101 0 15 110110 0 15 110111 0 15 111000 0 15 111001 0 15 111010 0 15 111011 0 15 111100 0 15 111101 0 15 111110 0 15 111111 1 16 1000000 0 16 1000001 0 16 1000010 0 16 1000011 0 16 1000100 0 16 1000101 0 16 1000110 0 16 1000111 0 16 1001000 0 16 1001001 0 16 1001010 0 16 1001011 0 16 1001100 0 16 1001101 0 16 1001110 0 16 1001111 0 16 1010000 0 16 1010001 0 16 1010010 0 16 1010011 0 16 1010100 0 16 1010101 1 17 1010110 0 17 1010111 1 18 1011000 0 18 1011001 0 18 1011010 0 18 1011011 0 18 1011100 0 18 1011101 0 18 1011110 0 18 1011111 1 19 1100000 0 19 1100001 0 19 1100010 0 19 1100011 0 19 1100100 0 19 1100101 0 19 1100110 0 19 1100111 0 19 1101000 0 19 1101001 0 19 1101010 0 19 1101011 0 19 1101100 0 19 1101101 0 19 1101110 0 19 1101111 0 19 1110000 0 19 1110001 0 19 1110010 0 19 1110011 0 19 1110100 0 19 1110101 0 19 1110110 0 19 1110111 0 19 1111000 0 19 1111001 0 19 1111010 0 19 1111011 0 19 1111100 0 19 1111101 0 19 1111110 0 19 1111111 1 20 answered 31 Jul '17, 19:51 3★panky4u 1 accept rate: 0%
 0 i used the formula 2^(n/2) + 2^(n-1) where n=2,3,4.... but i am getting WA can anyone tell me the fault? 2^(n/2) is the case when first is K and 2^(n-1) is the case when it is not K so for n-1 places it can be either K or H answered 17 Oct '17, 20:20 1 accept rate: 0% You should take n=4 then find the answer by pen and paper and also calculate using your own derived formula you will surely realise your mistake. (02 Feb, 00:12)
 0 @shashank3112 , here the N can have very large values like 10^9 ,hence recursion can't be used answered 17 Dec '17, 18:37 0●2 accept rate: 0%
 0 Now, if the sequence were to start with a 1, then every odd index in the sequence (assuming the sequence is 1-based) will be 1; the rest of the floor(N/2) indices can be either 0 or 1, mutually exclusively.  If the sequence starts with 1, it is true that every odd index will be one. But the remaining even indices floor(N/2) are also alternating thus they should also follow the given condition. We simply cannot assume that they will form all combinations of 0s and 1s. So instead of : f(N) = f(N-1) + 2^floor(N/2) as @mammy suggested, the recurrence formula should be: f(N) = f(N-1) + floor(N/2) + 1 And this is clearly seen from N = 5: the previous formula gives answers as 14 but the actual answer is 12  1 1 1 1 1 ___________ 1 | H H H H H 2 | K H K H K 3 | K K K K K 4 | K H K K K 5 | H K H K H 6 | H K K K K 7 | H K H K K 8 | H H K H K 9 | H H K K K 10| H H H K H 11| H H H K K 12| H H H H K  I am open to all suggesstions. link This answer is marked "community wiki". answered 30 Mar, 01:57 2★aky91 0 accept rate: 0%
 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:

×14,441
×1,051
×251
×119
×17

question asked: 11 Sep '12, 15:12

question was seen: 9,271 times

last updated: 30 Mar, 01:57