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) + 2``floor(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 `f``o``(N)` and `f``e``(N)` be the functions that are defined for the odd and even values of N respectively. Thus,
`f(N) = if N is odd then f``o``(N) else f``e``(N)`

`(1) ... f``o``(N) = f``e``(N-1) + 2``(N-1)/2`
`(2) ... f``e``(N) = f``o``(N-1) + 2``N/2`

From `(1)` and `(2)` we can derive

`(3) ... f``o``(N) = f``o``(N-2) + 2``(N-1)/2` `+ 2``(N-1)/2`
`(4) ... f``e``(N) = f``e``(N-2) + 2``N/2` `+ 2``(N-2)/2`

Where,

`f``o``(1) = 2`
`f``e``(0) = 1`

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

Let,

`t``o``(N)` = `f``o``(N) - f``o``(N-2)` = `2``(N-1)/2` `+ 2``(N-1)/2` = `2``(N+1)/2`

`t``o``(3) = 2``2`
`t``o``(5) = 2``3`
`t``o``(7) = 2``4`
`...`
`t``o``(N) = 2``(N+1)/2`

Adding all of the above gives us,

`f``o``(N) - f``o``(1) =``[n = 0 to (N+1)/2]` `2``n` `- 2``1` `- 2``0`
`f``o``(N) - 2 = 2``(N+1)/2 + 1` `- 1 - 2 - 1` (summation of Geometric Progression)
`f``o``(N) = 2``(N+1)/2 + 1` `- 2`

Similarly, we want to find the closed form for `f``e`.

Let,

`t``e``(N)` = `f``e``(N) - f``e``(N-2)` = `2``N/2` `+ 2``N/2 - 1`

`t``e``(2) = 2``1` `+ 2``0`
`t``e``(4) = 2``2` `+ 2``1`
`t``e``(6) = 2``3` `+ 2``2`
`...`
`t``e``(N) = 2``N/2` `+ 2``N/2 - 1`

Adding all of the above gives us,

`f``e``(N) - f``e``(0) =``[n = 0 to N/2]` `2``n` `- 2``0` + ∑`[n = 0 to (N/2 - 1)]` `2``n`
`f``e``(N) - 1 = 2``N/2 + 1` `- 1 - 1 + 2``N/2` `- 1` (summation of Geometric Progression)
`f``e``(N) = 2``N/2 + 1` `+ 2``N/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) = 2``N/2 + 1` `+ 2``N/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) = 2``N/2 + 1` `+ 2``N/2` `- 2`, for even N

Or,

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

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

# SETTERS SOLUTION

Can be found here

# TESTERS SOLUTION

Can be found here

9 Likes

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

http://www.codechef.com/viewsolution/1333458
Why this solution is incorrect. I used the same formula.

How can solve it using Matrix Expo? What is the Dimension of matrix for this problem?

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 |
```

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

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.

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

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

@shashank3112 , here the N can have very large values like 10^9 ,hence recursion can’t be used

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.

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.

Can someone explain how we get that recurrence relation? thanx in advance.

I think this editorial should be rechecked. How come for n=4 the answer can be 10.
There are only 9 possible outcomes for n=4.

Moreover according to me the recurrence relation should be:

F(n) = n+1+ 2*S(floor((n-1)/2)) + n/2 ----- if n is even

F(n) = n+1+ 2*S(floor((n-1)/2)) ------------if n is odd

``````result = (F(n))%mod
``````

Here S(val) will be the sum of numbers from 1 to val.

Please have a look on my query.

I joined few days ago and started with this example.

I am reading the comments and for the “ak91” I think that for N = 5 we have 14 answers and not 12, like you stated and showed in the table.

Here I am missing 2 combinations: “H K K K H” and “K K K H K”.

Here is a matrix exponentiation solution if you didn’t understand the conversion of recurrence relation into the closed form.
Matrix Exponentiation Solution

1 Like

why this is not working???
long long int odd=(n+1)/2;
long long int even=n/2;
long long int alone=1;