CKISSHUG - Editorial

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

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

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

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

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

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

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;
long long answer=(odd* (even+alone)+(even*alone)+alone);

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

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

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

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

1 Like

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 (n
POWER(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

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

how to get the recurrence relation?

f(n)=f(n-1)+floor(n/2)+1 yeah this has to be the correct relation as you said earlier.
I was stuck at n=4 and checking with these solutions. Thank You!

HOW RECURRENCE IS REDUCING TIME COMPLEXITY , BECAUSE WE ARE DOING CALCULATION N-1 TIMES ,
BUT IF WE DO DIRECTLY PERMUTATION THEN I THINK TIME SHOULD BE LESS BUT ITS GIVING TLE