You are not logged in. Please login at www.codechef.com to post your questions!

×

MATDYS - Editorial

7
2

Problem Link

Practice
Contest

Author: Alexandru Valeanu
Tester: Hasan Jaddouh
Editorialist: Bhuvnesh Jain

Difficulty

EASY

Prerequisites

Observations

Problem

You are given a pack of $2^N$ cards and you shuffle it in N steps. At step $k$ $(0 ≤ k < N)$ you divide the deck into $2^k$ equal-sized decks. Each one of those decks is reordered by having all the cards that lie on even positions first, followed by all cards that lie on odd positions (the order is preserved in each one of the two subsequences). Then all decks are put back together (again, the order of decks is preserved). Given an unordered deck of size $2^N$, find the position of the card labelled $K$ in the final, shuffled deck.

Quick Explanation

Check the binary representation of $K$ and the final answer. Try to spot some observations.

Explanation

Subtask - 1

Since, $N <= 10$, we can simply simulate the whole process and find the exact order of the cards after all the $N$ shuffles are done. The simply output the $K^{th}$ index in the final array. The complexity of the above solution would be $O(N*{2}^{N})$ because there are total $N$ steps of shuffling and each shuffles uses all the $2^N$ cards. This solution is thus too slow for the remaining subtasks.

Subtask - 2, 3 (Author's Solution)

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.

Subtask - 2, 3 (Editorialist's Solution)

Since, $K$ is of the order od $2^N$, we would like to come up with an logarithmic approach in $K$ or linear in $N$.

According to the way operations are performed, it is easy to see that once, 2 cards are separated into different decks, they can never appear in the same deck again. Thus we try to find how the cards of one deck are related to the other as same kind of operations (separating into decks and then reassembing based on even/odd combinations) is done of both of them.

Consider the operations one by one. Let $K = 0$, Here all the even numbers appear first in increasing order and then the odd numbers appear first. Thus, if we divide the array into 2 equal halves, we can see that numbers in right half are simply $1 (2^0)$, plus the numbers of the left side.

$K = 0$ -> $ 0 2 4 6 | 1 3 5 7$

Now, let $K = 1$. The deck is divided into 4 halves and as per the first observation, cards in left deck of last operation cannot go to right deck of last operation. Thus, we would see how the leftmost 2 decks are related and the rightmost 2 decks are related. One can again see that for both halves, numbers of right deck are simply $2 (2^1)$, plus the numbers of the left side.

$K = 1$ -> $ 0 4 | 2 6 | 1 5 | 3 7$

Thus, if we continue this procedure, we see that number of rigth side after $i$ operations are simply $2^i$ plus the number of left side.

Thus, we now layout our algorithm, which is similar to binary search, as we would reduce our search space to half on each iteration and try to find the contribution of each step to the answer.

A similar problem using the above technique can be found out here

Pseudo Code

i = n-1 while(i >= 0): if (k > 2^i): //means lies of right side ans += 2^(n-1-i) k -= 2^i //move it to left side i -= 1 print(ans)

Some Silly Errors

Most of the participants, although found the correct logic but could not get full score. This is because of overflow in the answer. This is mostly the case in C++/Java users. If we use "long long", the maximum limit is 63 bits on positive side and 63 bits on the negative side. To get full score, one had to use 64-bit representation i.e. "unsigned long long". This should have been a good experience for some to learn about overflow cases in languages. Although python users had an advantage here as there is no overflow there.

Time Complexity

$O(n)$ or $O(\log{K})$

Space Complexity

$O(1)$

Solution Links

Setter's solution
Tester's solution
Editorialist solution

asked 24 Aug '17, 16:10

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 27 Aug '17, 00:56

4

BTW idk why nobody said this, but this is seriously a great editorial @likecs !!

(27 Aug '17, 00:08) vijju123 ♦♦5★

why we need to move the number to the left if it is on right?

(27 Aug '17, 00:15) anno4★
1

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

(27 Aug '17, 00:58) likecs6★
2

Nice question! Inspired by FFT if I'm not wrong? :)

(27 Aug '17, 01:23) meooow ♦6★

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

(27 Aug '17, 01:54) alexvaleanu4★

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.

link

answered 27 Aug '17, 04:26

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

edited 28 Aug '17, 21:33

It feels bad when you skip the dinner for the contest but can only solve one problem ;_;
Grats to problem setter for a great "easy"(not for me though :p) level problem... It was really nerve stretching, at least for me!!

link

answered 26 Aug '17, 23:10

dishant_18's gravatar image

4★dishant_18
61419
accept rate: 12%

edited 26 Aug '17, 23:14

I am sorry this was the case for you!

(26 Aug '17, 23:12) alexvaleanu4★
1

Thanks for such a great problem! Such problems are the cause I give priority to contests over dinner

(26 Aug '17, 23:16) dishant_184★
2

Thank you for your feedback!

(26 Aug '17, 23:21) alexvaleanu4★

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

link

answered 27 Aug '17, 00:48

parthdhar's gravatar image

2★parthdhar
511
accept rate: 0%

edited 27 Aug '17, 00:56

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

link

answered 27 Aug '17, 11:44

alphastar's gravatar image

2★alphastar
295
accept rate: 0%

edited 27 Aug '17, 15:30

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

(27 Aug '17, 12:04) vijju123 ♦♦5★

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

(27 Aug '17, 12:20) alphastar2★
2

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 :(

EDIT: Refer to "//" and "/" operator, and their difference.

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

(27 Aug '17, 13:19) vijju123 ♦♦5★

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

Thanks Vijju123 Got AC

(27 Aug '17, 15:29) alphastar2★

Damn unsigned long long int!

Didnt strike me during contest and was suffering from overflow :( . Switching to python was a savior though :) (Stalking those python codes after long paid off ^_^ )

link

answered 26 Aug '17, 23:06

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 26 Aug '17, 23:06

The idea was to give a small advantage to careful contestants and Python coders.

(26 Aug '17, 23:09) alexvaleanu4★

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 :)

(26 Aug '17, 23:11) vijju123 ♦♦5★

how can i improve my solution : https://www.codechef.com/viewsolution/15131329

link

answered 26 Aug '17, 23:19

ayush_codechef's gravatar image

3★ayush_codechef
517
accept rate: 0%

@alexvaleanu I used unsigned long long int in C++14 but it still couldn't store values as large as 2^64.

Had to resort to BigInteger in Java.

Any ideas why ? Please have a look solution link (I used the Binary Search approach)

link

answered 26 Aug '17, 23:39

rdrsadhu's gravatar image

4★rdrsadhu
1348
accept rate: 11%

You only needed till 2^63, no? And even after summing, its 2^64-1. 2^64 is out of limits, but 2^64-1 is in limit

(26 Aug '17, 23:41) vijju123 ♦♦5★

My point is the solution should've been AC then !! But it threw a RE (SIGFPE) error. WHY ??

(26 Aug '17, 23:45) rdrsadhu4★

It means you are doing infinite loop somewhere. And getting a RE due to this. Like when an array gets involved in a infinite loop.

(26 Aug '17, 23:57) vijju123 ♦♦5★
2

Try this test case

1

64 18446744073709551615

Second number is 2^64-1.

Actually problem is value of total become 2^64 which cannot fit in unsigned long long.

(27 Aug '17, 00:01) dushsingh19954★
1

With that attitude of yours, I'd rather not :) . Go debug yourself, your code is none of my concern.

(27 Aug '17, 00:07) vijju123 ♦♦5★
(27 Aug '17, 00:10) rdrsadhu4★
showing 5 of 6 show all

I used unsigned long long int...but then also got wrong answer...can someone please help https://www.codechef.com/viewsolution/15129654

link

answered 26 Aug '17, 23:51

jha_gaurav98's gravatar image

5★jha_gaurav98
1
accept rate: 0%

I solved it using simple recursion in python

def f(n,k):
    if k==0:
        return 0
    if k%2==0:
        return f(n-1,k//2)
    return f(n-1,k//2)+2**(n-1)

t=int(input())
while t:
    t-=1
    [n,k]=list(map(int,input().split()))
    print(f(n,k))
link

answered 27 Aug '17, 00:22

tarptaeya's gravatar image

4★tarptaeya
392
accept rate: 0%

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

(27 Aug '17, 00:23) vijju123 ♦♦5★

There is a shorted Python solution :) Check mine!

(27 Aug '17, 00:25) alexvaleanu4★

There is even a shorter way to do this. :) https://www.codechef.com/viewsolution/15156758

(29 Aug '17, 06:25) eugalt3★

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

link

answered 27 Aug '17, 02:27

ankitraj1996's gravatar image

3★ankitraj1996
1
accept rate: 0%

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;
link

answered 27 Aug '17, 02:45

shiwam203's gravatar image

5★shiwam203
102
accept rate: 0%

That's reversing the binary representation. And you would usually use << operator to get a power of 2.

(29 Aug '17, 02:42) eugalt3★

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!

link

answered 27 Aug '17, 09:12

akashbhalotia's gravatar image

5★akashbhalotia
875214
accept rate: 10%

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.

link

answered 27 Aug '17, 10:09

dhruvsomani's gravatar image

4★dhruvsomani
1448
accept rate: 8%

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.

link

answered 27 Aug '17, 10:17

dark_shadow13's gravatar image

1★dark_shadow13
1
accept rate: 0%

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

(27 Aug '17, 16:34) likecs6★
Answer is hidden as author is suspended. Click here to view.

answered 27 Aug '17, 10:20

raj79's gravatar image

2★raj79
(suspended)
accept rate: 10%

Whats wrong with my code? Getting wrong answer on test 3 subtask 3.

https://www.codechef.com/viewsolution/15133990

link

answered 27 Aug '17, 20:33

zip_light's gravatar image

3★zip_light
1
accept rate: 0%

overflow issues..didn't you check 2nd sample case given ??

(27 Aug '17, 20:42) srikanth_161★

Is n't the Pseudo Code given wrong?

link

answered 27 Aug '17, 23:35

ayushgoyal1703's gravatar image

4★ayushgoyal1703
222
accept rate: 0%

@ayushgoyal1703, No. You can check my solution(editorialist) as well.

(28 Aug '17, 03:00) likecs6★

Subtask - 2, 3 (Author's Solution)

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

link

answered 28 Aug '17, 13:13

akashkandpal's gravatar image

1★akashkandpal
01
accept rate: 0%

edited 28 Aug '17, 13:16

Can someone explain the author's solution in details ?How he arrived at it.

Thanks in Advance

link

answered 22 Sep '17, 20:53

bhagirathi08's gravatar image

3★bhagirathi08
01
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×3,820
×267
×64
×24

question asked: 24 Aug '17, 16:10

question was seen: 4,817 times

last updated: 22 Sep '17, 20:53