(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)
Can someone explain why even group size will have s/2+1 ways ?
You can think of it like this. Iām representing the numbers that we choose as ones and the others as zeros. So the sequence will look like this.
1 0 1 0 1 0 1 0 1 0 ā¦ 1 0
You can think of the choices for this group as pushing a number of elements (ones) to the right. You can either not push any elements (1 way), or you can push any suffix of ones of length 1 to s / 2 to the right (s / 2 ways).
For example consider 1 0 1 0 (group of size 4),
1st way = 1010 (default order)
2nd way = 0101 (suffix of length 2 is pushed)
3rd way = 1001 (suffix of length 1 is pushed)
Another example, 1 0 1 0 1 0 (group of size 6),
1st way = 101010 (default order)
2nd way = 010101 (suffix length = 3 pushed)
3rd way = 100101 (suffix length = 2 pushed)
4th way = 101001 (suffix length = 1 pushed)
Remember that by suffix of the sequence I donāt mean the actual suffix but only the rightmost ones in the sequence. So by suffix length L, I only mean the rightmost L ones.
So you can pick any suffix of ones and push it to the right. So the total number of choices you have with an even sized group is s / 2 + 1 where s is the size of the group.
Hope this helps 
2 Likes
Thank you so muchā¦!
@shameekagarwal can you please give your accepted solution.I am facing the same problem but i am not able to correct it.
1 Like
https://www.codechef.com/viewsolution/34635625
i just changed flag declaration i.e. declared it as __int128
Thanks
Great Editorial ! It makes a lot of sense when you read an editorial, but can someone suggest some reference or problem set which can help us solve these type of problems in the contest itself ?
@shameekagarwal Hey, I just compared my code to yours for reference. I think that I have done the same thing as yours but getting WA. I tried hard but couldnāt find the mistake. Can you point out the mistake??
My Solution: CodeChef: Practical coding for everyone