CKISSHUG - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY

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

11 Likes
2

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

3

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

4

Simple question … i only used sum of G.P.(Geometric progression) and some extra calculation…That is very simple…CodeChef: Practical coding for everyone

5

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.

3 Likes
6

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

5 Likes
7

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

8

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

9

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.

5 Likes
10

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

11

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

12

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

13

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
14

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);

15

hey i am not able to submit my solution for this problem.
i clicked problem and it took me to CKISSHUG Problem - CodeChef but neither the problem nor the submit button was present.
plz help

16

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 |
1 Like
17

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.

1 Like
18

Can any one please tell me what’s wrong with this?
https://www.codechef.com/viewsolution/23696888

1 Like
19

i also solved the question using the same formula.But i m getting wrong ans;…
my code:
#include
using namespace std;

long long int POWER(int n,int p)
{
if (p==0)
{
return 1;
}
if(p%2==0)
{
return POWER(nn,p/2)%1000000007;
}
if(p%2!=0)
{
return (nPOWER(n*n,(p-1)/2))%1000000007;
}
}

int main(){
int t;
cin>>t;
for(int i=0;i<t;i++)
{
int n;
cin>>n;
if(n%2==0)
{
int k=POWER(2,n/2);
cout<<(3k-2)%1000000007<<endl;
}
else
{
int k=POWER(2,(n+1)/2);
cout<<(2(k-1))%1000000007<<endl;
}
}
}
please tell the mistake

20

Please somebody help me with the test cases. I am not able to figure out the test cases where my code is not able give AC.
https://www.codechef.com/viewsolution/26748078