The Bessie Shuffle

Problems and Contests
#1

For this problem, can someone please explain to me an (easy to understand) solution? I don’t understand what the official solution is trying to say, here is the link to the editorial.

If you have the code for this problem, that would be even better. Thanks.

#2

The idea is to calculate the position each card is going to be after n turns of shuffling using binary lifting.

#3

don’t think they’re asking about the gold solution here buddy

#4

Do you know the solution with pure observations?

#5

Pure observations?

#6

That is the silver solution … Though you don’t actually need binary lifting for the Silver version, as it can be solved in the same way as Swapity Swapity Swap.

#7

The official editorial doesn’t mention binary lifting?

#8

Hi Ben, can you expand on the “functional graph” solution? I know there are 2 different cases, when N >= 2M, and when N < 2M. I already solved the case where N >= 2M (where we process the first M elements using a graph, then the middle elements using an observation, and the last M elements also using the graph). I am stuck for N < 2M, help?

#9

It does, “repeated squaring” = binary lifting

#10

oh ok i’m clowning lol

#11

Repeated squaring is essentially binary lifting?

I don’t know what you’re referring to. The analysis you linked doesn’t distinguish between N < 2M and N >= 2M.

What’s the functional graph solution?

#12

In this case I have no idea why my solution passed:

import java.io.*;
import java.util.*;

// 2013 dec silver
public final class Shuffle {
    public static void main(String[] args) throws IOException {
        long start = System.currentTimeMillis();
        BufferedReader read = new BufferedReader(new FileReader("shuffle.in"));
        StringTokenizer initial = new StringTokenizer(read.readLine());
        // note: cards start w/ 1 at the top and N @ the bottom
        // but bc i like 0-indexing imma just, ya know, make all the cards 0-indexed
        int totalCardNum = Integer.parseInt(initial.nextToken());
        int shuffleCardNum = Integer.parseInt(initial.nextToken());
        int queryNum = Integer.parseInt(initial.nextToken());
        int[] reverseShuffle = new int[shuffleCardNum];
        for (int c = 0; c < shuffleCardNum; c++) {
            reverseShuffle[Integer.parseInt(read.readLine()) - 1] = c;
        }

        PrintWriter written = new PrintWriter("shuffle.out");
        for (int q = 0; q < queryNum; q++) {
            int query = totalCardNum - Integer.parseInt(read.readLine());
            int relPos = Math.max(shuffleCardNum - (totalCardNum - query), 0);  // both of these are 0-indexed
            int absPos = query;
            int windowStart = Math.min(totalCardNum - shuffleCardNum, absPos);
            while (relPos != shuffleCardNum && windowStart >= 0) {
                int nextRelPos = reverseShuffle[relPos];
                absPos += nextRelPos - relPos;
                relPos = nextRelPos + 1;
                windowStart--;
            }
            written.println(absPos + 1);
            System.out.println(absPos + 1);  // turn it back to 1-indexing
        }
        written.close();
        System.out.printf("here it took %d ms are you happy%n", System.currentTimeMillis() - start);
    }
}
#13

Don’t really understand what you just did here? Seems quite concise, can you explain?

#14

Yeah, it’s pretty odd that the constraints were set such that \Theta(NQ) passes.

#15

That’s how I solved 7/10 cases, the functional graph only gives us the answer for the first M elements. For the middle elements, we can observe it increases by 1 overtime from whereever we left off for the first M elements. For the last M elements, we can continue to trace their location, but just from the end of the graph (index = m). Because the last element is in the shuffle once, the second to last is in the shuffle twice…

This solution is quite confusing, so can you explain what you mean by solving it the same way as Swapity swaptity swap.

#16

i would if i understood the code i wrote myself lmao

#17

Ok, I think I see what you mean. The analysis seems pretty clear to me though. Could you specify which of the parts is the one you don’t understand?

Viewing it this way, we always apply the Bessie shuffle to the first M elements and then shift the whole permutation left. These two steps can be viewed as permutations on N elements, and the effect of them taken together (their composition) is also a permutation.

So for the sample case, [1 2 3 4 5] -> [2 3 1 4 5] -> [3 1 4 5 2].

This means we can calculate a single permutation which we need to apply (N-M+1) times to 1…N.

We want to find the 5-3+1=3'rd power of [3 1 4 5 2]. (Here, applying K times to 1\ldots N = K-th power.)

To do this we can use repeated squaring, thus solving the problem in O(N log(N - M)) time.

The relevant powers of [3 1 4 5 2] are:

[3 1 4 5 2]^0 = [1 2 3 4 5]

[3 1 4 5 2]^1 = [3 1 4 5 2] ([3 1 4 5 | 2])

[3 1 4 5 2]^2 = [4 3 5 2 1] ([4 3 5 | 2 1])

[3 1 4 5 2]^3 = [5 4 2 1 3] ([5 4 | 2 1 3])

Of course, we need to cancel those N-M+1 left shifts with an N-M+1 right shift.

To get the final order, we shift [5 4 2 1 3] N-M+1 units to the right to get [2 1 3 5 4]. Then we reverse it to get [4 5 3 1 2], which is what we want.

In that problem we are also computing the K-th power of a permutation.

#18

The analysis is clear, but is there any way that we don’t use repeated squaring? I am not familiar with that concept, so I am trying to only use a functional graph + observations to solve this problem.

#19

In swapity swapity swap we don’t need to use repeated squaring. Same applies to this problem.

#20

Do you know where I can find a solution code with this implementation?