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
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
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.
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
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 |
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.
Can any one please tell me what’s wrong with this?
https://www.codechef.com/viewsolution/23696888
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
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
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!
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