MATDYS - Editorial

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

7 Likes

Damn unsigned long long int!

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

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

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

2 Likes

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

I am sorry this was the case for you!

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

1 Like

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

Thank you for your feedback!

2 Likes

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

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

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

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

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.

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.

2 Likes

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

1 Like

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

4 Likes

THANKS @dushsingh1995

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

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