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