You are not logged in. Please login at www.codechef.com to post your questions!

×

CKISSHUG - Editorial

9
5

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

This question is marked "community wiki".

asked 11 Sep '12, 15:12

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

edited 25 Dec '12, 14:52

admin's gravatar image

0★admin ♦♦
19.3k348495534

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) never_stop2★

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

link

answered 15 Sep '12, 18:50

saurabh075's gravatar image

2★saurabh075
1
accept rate: 0%

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

link

answered 14 Oct '12, 23:53

FORHAD-SUST-BD's gravatar image

2★FORHAD-SUST-BD
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) gamabunta1★

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

link

answered 19 Jun '16, 16:36

bansal1232's gravatar image

5★bansal1232
2.8k317
accept rate: 16%

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.

link

answered 20 May '17, 13:33

mamay's gravatar image

3★mamay
21
accept rate: 0%

edited 20 May '17, 14:52

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

link

answered 31 Jul '17, 19:51

panky4u's gravatar image

3★panky4u
1
accept rate: 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

link

answered 17 Oct '17, 20:20

shashank3112's gravatar image

3★shashank3112
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) deepak_0975★

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

link

answered 17 Dec '17, 18:37

aetius_98's gravatar image

2★aetius_98
02
accept rate: 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

aky91's gravatar image

2★aky91
0
accept rate: 0%

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

link

answered 22 Jul, 11:27

ashish3805's gravatar image

3★ashish3805
0
accept rate: 0%

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

link

answered 31 Jul, 11:13

srvptk's gravatar image

3★srvptk
01
accept rate: 0%

edited 31 Jul, 11:15

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

link

answered 03 Aug, 11:08

iknerf0712's gravatar image

0★iknerf0712
1
accept rate: 0%

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

link

answered 16 Sep, 18:08

soheb17's gravatar image

5★soheb17
101
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,005
×1,088
×260
×150
×18

question asked: 11 Sep '12, 15:12

question was seen: 9,734 times

last updated: 03 Aug, 11:09