Shuffler

TCO18 India Fun · 2018-04-20 · by misof

TCO18 India Fun · 2018-04-20 · by misof · Graph Theory, Greedy, Simple Math

Show categories

Class Name: Shuffler

Return Type: String

Method Name: findShuffles

Arg Types: (string)

Problem Statement

Brian is an aspiring magician. Recently, he spent half of a year learning how to do the perfect shuffle. A perfect shuffle is an operation performed on a deck that has an even number of cards. The shuffle consists of the following steps:

Brian splits the deck exactly in the middle, producing two equally large halves.
Then he places the two halves of the deck next to each other and mashes them together so that their cards interleave perfectly.

There are two ways to perform a perfect shuffle: either the top card stays on top of the deck, or it doesn't. We will call them "type 1" and "type 2".

For example, suppose Brian only has 6 cards, labeled A through F and ordered so that the deck reads "ABCDEF" from top to bottom. Then a type-1 shuffle looks as follows:

Brian splits the deck into two piles: "ABC" and "DEF".
Brian interleaves the two piles perfectly, while keeping card A on top. This produces a new deck that reads "ADBECF" from top to bottom.

And a type-2 shuffle looks as follows:

Again, Brian splits the deck into two piles: "ABC" and "DEF".
Brian interleaves the two piles perfectly, but now card A does not remain on top. This produces a new deck that reads "DAEBFC" from top to bottom.

Brian's actual deck has exactly 26 cards. At the beginning of a trick they are labeled A through Z from the top to the bottom of the deck. Brian now wants to perform a magic trick. For the trick he asks a randomly selected spectator to tell him their name. Then, he will perform a series of steps. In each step, he will either perform a type-1 shuffle, perform a type-2 shuffle, or he will reveal the card that is currently on the top of the deck. He wants to perform the steps in such a way that the revealed cards will spell the spectator's name.

You are given the String name: the name of the spectator. The name has at most 50 characters. Find any sequence of at most 314 steps that spells the given name. You may assume that such a sequence always exists. If there are multiple such sequences, you may output any of them.

Return the sequence as a String of characters '1', '2', and 'R'. (Characters '1' and '2' represent the corresponding shuffles and 'R' represents a step in which Brian reveals the top card.)

Constraints

name will contain between 1 and 50 characters, inclusive.
Each character in name will be an uppercase English letter ('A'-'Z').

Examples

"ANN"
Returns: "R2RR"

Brian should do a reveal (showing the 'A'), a type-2 shuffle to bring the card 'N' to the top, and two reveals to show 'N' twice. Note that he must reveal the card multiple times if there are consecutive copies of the same letter in name. The return value "R2R" is not correct.

"Z"
Returns: "22112R"

Getting the 'Z' card all the way from the bottom to the top of the deck is not easy. The example output shows one way of doing so in five consecutive shuffles. Remember that this is just one of many possible correct outputs.

"ZUZA"
Returns: "22112R1212R21112R22112R"

This example solution starts by bringing 'Z' to the top in the same way as before. Next, we need to bring 'U' from its current position in the deck to the top. Afterwards, we want to see 'Z' again. Note that at this moment 'Z' is not at the bottom of the deck, so the sequence of shuffles we use for the second 'Z' is different from the sequence we used for the first 'Z'.

"AAAAAA"
Returns: "RRRRRR"

"TOPCODER"
Returns: "12R11122R2122R1212R12222R12R212R22212R"

Submissions are judged against all 160 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Shuffler with a public method string findShuffles(string name) · 160 test cases · 2 s / 256 MB per case