Riffle Shuffles

Statement

It is a well-known piece of trivia that seven riffle shuffles are supposedly enough to randomize a deck of cards. In this problem we’ll examine this claim more closely.

We will use the uppercase and lowercase letters of the English alphabet to represent a standard deck of 52 cards. In particular, the string ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz (all the letters sorted according to their ASCII code) will represent the new deck order.

The research from which the popular claim about seven riffle shuffles is derived used the Gilbert-Shannon-Reeds model of a riffle shuffle. According to this model, a riffle shuffle corresponds to the following randomized algorithm:

function riffle_shuffle(deck):
    n = length(deck)
    x = binomial(n, 0.5)       # flip n fair 0/1 coins and sum them
    cut the deck into (A, B) = (top x cards, bottom n-x cards)
    initialize output to an empty sequence of cards
    while both A and B are non-empty:
        a, b = length(A), length(B)
        with probability a/(a+b):
            remove the first card of A and append it to the output
        else:
            remove the first card of B and append it to the output
    append whatever remained of A to the output
    append whatever remained of B to the output

Python implementation of the riffle shuffle: R_shuffle.py

You will be given multiple collections of 1000 decks.

In each collection, all decks started in the new deck order. In some of them, all 1000 decks were shuffled properly, using a shuffle where each possible outcome is equally likely. In others, all 1000 decks were shuffled using seven consecutive riffle shuffles. Your task is to tell which is which.

Input format

The first line of each input file contains the number \(t\) of test cases. The specified number of test cases follows, one after another.

Each test case consists of 1000 lines, each containing a permuted string of our 52 letters (A-Z, a-z).

Output format

For each test case, output a single line with either the string uniform if the decks were shuffled uniformly, or riffle if they were shuffled using riffle shuffles.

Subproblem R1 (50 points, public)

Input file: R1.in

Constraints: \(t=100\) and your output is accepted if at least 99 of the 100 strings in your output are correct.

Subproblem R2 (50 points, secret)

Input file: R2.in

Constraints: \(t=200\) and your output is accepted if at least 195 of the 200 strings in your output are correct.

Example

Example input with \(t=2\): R0_sample.in

The correct output for this example input:

riffle
uniform

I.e., the first 1000 decks are shuffled using seven riffle shuffles, the second 1000 decks using a proper random shuffle.