MATDYS - Editorial

editorial
, , , ,
21

My code was a simply while loop :stuck_out_tongue: , but our ideas are same . First time solved a Q in less than 15 lines XD

22

There is a shorted Python solution :slight_smile:
Check mine!

23

Another O(N) approach:

The 2^n numbers can be divided into 2^{n-1} pairs mod 2^{n-1}. Observe that these modular residues pairs are arranged in the same order as the final ordering N = n-1.

For example - The final ordering for N=3 is \{0, 4, 2, 6, 1, 5, 3, 7\} which is equivalent to \{0,0,2,2,1,1,3,3\} (mod 4). This is the same as the final ordering for N = 2 i.e. \{0,2,1,3\}

With a recursive approach, we use the ordering for N=n-1 to obtain the ordering of the modulo pairs for N=n. Within the pair, the smaller number (which is strictly less than 2^{n-1}) comes first.

define f(n, k):
    if n==2:
        //Base case. Return the answer using the final ordering {0, 2, 1, 3}
    else:
        power = 2^(n-1) //use (1LL)<<(n-1)
        position = f(n-1, k % power) //recursion
        return 2*position + k/power //to handle ordering in the modulo pair
//n = 1 is handled separately

C++ code can be found here

1 Like
24

@anno, we are now actually moving number from left to right. It is just that calculating the number of left side is easier. So, we the number lies on right, we know that in i step it is 2^i plus that on left side. Thus, we add this contribution. I would recommend you to try some more examples on paper and also try to solve the problem mentioned in the link.

1 Like
25

Iterate from the least significant bit to the most significant one,and use binary search to find position of number

1 Like
26

Nice question! Inspired by FFT if I’m not wrong? :slight_smile:

2 Likes
27

@meooow Thank you! You are the first one to notice the FFT part. Yes, sorting by reverse_bits is the first step in the iterative implementation of FFT.

28

I am a newbie here,
As my answer my wrong, but I want to know, what was wrong with this:-
Initial array:-{0,1,2,3,4,5,6,7}
n=3
for any k, which is greater than or equal to n, the least size of the block will be 2.
Now after all the rearrangements the final array is {0,4,2,6,1,5,3,7}
Now my point is to swap the arr[1] with arr[1+pow(2,n-1)-1] and similarly with arr[3] until 1+pow(2,n-1)-1 < n.
Can anyone help??

29

Here is a simple O(logK) approach. It uses binary representation of K.

    #define ull unsigned long long

    int i=1;
    ull ans=0;
    while(k){
        if(k&1){
            ans+=(ull)pow(2,n-i);
        }
        k>>=1;
        i++;
    }
    cout<<ans;
30

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.

Here is the implementation of this algorithm.

3 Likes
31

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!

32

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.

Solution.

33

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.

34

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.

35

Edit: Fixed by Vijju123 Corrected code https://www.codechef.com/viewsolution/15138756

Original:

What’s wrong with my code/logic It fails on subtask 3 and runs on 1&2 (Lang Python 3) https://www.codechef.com/viewsolution/15128686

My logic:
Let N1=2^(N-1){length of subarrays}

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

1 Like
36

Try changing this while i<int(li2[0]): to while i<=int(li2[0]):

37

Didn’t work with that too. Still AC on 1&2 subtask and WA on 3rd

38

Suffering from floating errors. If you use “K>>=1” and “N!>>=1” instead of dividing K by 2, you will get AC. Still looking why your K behaves weirdly, but I am no python user :frowning:

EDIT: Refer to “//” and “/” operator, and their difference.

Floating point divison has an error of about {10}^{-9} ,and that matters a LOT here :frowning:

2 Likes
39

Got another reason to hate python :frowning: c++ is my regular one.

Thanks Vijju123 Got AC

40

0246|1357. See 1 = 0+1, 3 = 2+1 and so on. Similar for other iterations. See the ‘|’ in editorial to indicate blocks.