The editorial does not explain why the binary representation of the answer is the reverse binary representation of K. What happens at every step k is that the rightmost N - k bits in the binary representation are cyclically shifted by one position to the right, so that the bit that was originally at position k from the right ends up at position k from the left.
It was a great contest! One hardly learns much from easier contests, but tough contests give you an opportunity to learn a lot. Kudos to you problem setter!
Here, have a look at my solution. My observation was that once a number gets in a range whic was changed earlier, it never gets out of the range. And the numbers in the new range are always in a sorted order. Therefore, you can just check the index of number in that range, find the new index and reduce the range and repeat it n-1 times.
What does the statement “numbers in right half are simply 1(2^0), plus the numbers of the left side.” mean exactly? Could you please provide examples? Thank you.
reading the editorial, and realizing i was so close ,seriously hurts .already solved k-char problem during the LOC, but when u fail to solve the similar problems just by some distance simple hurts , this teaches me that try till the last minute.
If the K is even then it will go in the left part of the array and its position in the left array will be K/2
If the K is odd then it will go in the right part of array and its position in the right subarray will still be K/2 but it will have whole left subarray before it, hence add length of left subarray in it(store length of left subarray in variable pre)
Now in both the cases divide k by 2 (k/=2) and in odd case add N1 in the pre variable, divide N1=N1/2 because length of subarray will decrease by 2 in each run. Repeat this N times and final answer is pre+K
Let us try to find the binary representation of K
and the final answer and try to spot some observations based on it. (Assume below that all binary representations are N
bit long).
Let N=3
Below is the table :
K ANS
000 000
001 100
010 010
011 110
100 001
101 101
110 011
111 111
Do you spot the relationship between the two of them? Yes, the answer is simply the reverse of K
in binary representation.
Thus, we can simply find the binary representation of K
. Then try to construct the answer from the reverse of the binary representation found.
Can someone provide me an implementation of this approach ?? Thanks in advance
Is this the implementation of the above approach ??
That was graceful. The concept was thoroughly tested. I like it now…although it made me pull my hair during contest cause i JUST couldnt get it right in c++ hahahahah. Should had been careful