CKISSHUG - Editorial

gamabunta · September 11, 2012, 3:12pm

PROBLEM LINK:

DIFFICULTY

SIMPLE

PREREQUISITES

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 10⁹ 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²
t_o(5) = 2³
t_o(7) = 2⁴
...
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ⁿ - 2¹ - 2⁰
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¹ + 2⁰
t_e(4) = 2² + 2¹
t_e(6) = 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ⁿ - 2⁰ + ∑_{[n = 0 to (N/2 - 1)]} 2ⁿ
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ⁿ can be found by repeated squaring.

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

never_stop · September 11, 2012, 6:50pm

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

saurabh075 · September 15, 2012, 6:50pm

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

FORHAD-SUST-BD · October 14, 2012, 11:53pm

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

gamabunta · October 19, 2012, 5:06am

Instead of all the analysis to find a closed form, you can use the equations for F_o or F_e based on whether N is even or odd.

For example, the F_o equation can be implemented using a 2x2 matrix

| F_o(k) 2^(k+1)/2 | = | 1 2 |
                    | 0 2 | * | F_o(k-2) 2^{(k-1)/2 |}

bansal1232 · June 19, 2016, 4:36pm

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

mamay · May 20, 2017, 1:33pm

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.

panky4u · July 31, 2017, 7:51pm

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

shashank3112 · October 17, 2017, 8:20pm

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

aetius_98 · December 17, 2017, 6:37pm

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

deepak_097 · February 2, 2018, 12:12am

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.

aky91 · March 30, 2018, 1:57am

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.

ashish3805 · July 22, 2018, 11:27am

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

srvptk · July 31, 2018, 11:13am

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.
Thanks in Advance !!

iknerf0712 · August 3, 2018, 11:08am

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

soheb17 · September 16, 2018, 6:08pm

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

kamal2908 · January 29, 2019, 4:51pm

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