CKISSHUG - Editorial

editorial
, , , ,
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

21

how to get the recurrence relation?

22

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!

23

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

24

Can anyone guide me how to strengthen my MATHS, to solve these kind of problems on my own ?

Like I could not even think about this solution that I saw in this editorial!

25

K K K H K
H K K K H

these are also solutions,
bcz only for first kiss we need to follow trend which is mentioned in question

26

For n = 4 total combination are 16 and rejected are
KHHH
KHHK
KKHK
KKHH
HKHH
HKKH
KKKH

SO total ans are 9 why your code giving answer 10

What I think is 2^n - Total number where K and H are alternate