PROBLEM LINK:DIFFICULTYSIMPLE PREREQUISITESSimple Math, Repeated Squaring PROBLEMHow 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 EXPLANATIONSuppose the sequence was to start with a 0, then all possible sequences of length N1 are valid. Now, if the sequence were to start with a 1, then every odd index in the sequence (assuming the sequence is 1based) will be 1; the rest of the floor(N/2) indices can be either 0 or 1, mutually exclusively. Thus we get the formula
Since N can be as much as 10^{9} we cannot use this recursive formulation as it is. EXPLANATIONSeeing the floor function and division by 2 immediately gives us the insight that we should find the formula for odd and even N. Let
From
Where,
These formulas are already very usable. We can use matrix exponentiation on Let,
Adding all of the above gives us,
Similarly, we want to find the closed form for Let,
Adding all of the above gives us,
Thus we can find the value of To further simplify the formula, you can rewrite the expressions for odd and even N as follows,
Or,
The value of SETTERS SOLUTIONCan be found here TESTERS SOLUTIONCan be found here
This question is marked "community wiki".
asked 11 Sep '12, 15:12

Here is a matrix exponentiation solution if you didn't understand the conversion of recurrence relation into the closed form. Matrix Exponentiation Solution answered 16 Sep '18, 18:08

http://www.codechef.com/viewsolution/1333458 Why this solution is incorrect. I used the same formula. answered 15 Sep '12, 18:50

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

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 = Un1 + floor(N/2) + 1 which gives: U0 = 1 U1 = 2 Un = Un2 + 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

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

@shashank3112 , here the N can have very large values like 10^9 ,hence recursion can't be used answered 17 Dec '17, 18:37

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 : as @mammy suggested, the recurrence formula should be: And this is clearly seen from N = 5: the previous formula gives answers as 14 but the actual answer is 12
I am open to all suggesstions.
link
This answer is marked "community wiki".
answered 30 Mar '18, 01:57

Can someone explain how we get that recurrence relation? thanx in advance. answered 22 Jul '18, 11:27

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((n1)/2)) + n/2  if n is even F(n) = n+1+ 2*S(floor((n1)/2)) if n is odd
Here S(val) will be the sum of numbers from 1 to val. Please have a look on my query. Thanks in Advance !! answered 31 Jul '18, 11:13

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". answered 03 Aug '18, 11:08

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)+(evenalone)+alone); answered 29 Jan, 16:51

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