A Monte-Carlo based solution of Google Code Jam question "Proper Shuffle" (2014, Round 1A, Question C)

main.cc

#include <stdio.h>
#include <algorithm>
#include <vector>

#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <random>
#include <cmath>

using namespace std;

using vi = vector<int>;
using vvi = vector<vector<int>>;

int N = 1000;
vvi freq(N, vi(N, 0));
std::mt19937 rand_src;

int monte_carlo_rounds = 1000000;
const int sample_size = 10000;

int getInt() {
    int x;
    scanf("%d", &x);
    return x;
}

void random_initialize() {
    // Seed with a real random value, if available
    std::random_device r;
    std::seed_seq seed2{static_cast<unsigned int>(time(0)), r(), r(), r(), r(), r(), r(), r(), r()}; 
    rand_src = std::mt19937(seed2);
}

void good_shuffle(vi& data) {
    int c = (int) data.size();
    for (int i = 0; i < c-1; ++i) {
        uniform_int_distribution<int> dist(i, c-1);
        int j = dist(rand_src);
        swap(data[i], data[j]);
    }
}

void bad_shuffle(vi& data) {
    int c = (int) data.size();
    uniform_int_distribution<int> dist(0, c-1);
    for (int i = 0; i < c-1; ++i) {
        int j = dist(rand_src);
        swap(data[i], data[j]);
    }
}

vi get_rangearray(int n) {
    vi data;
    data.reserve(n);
    for (int i = 0; i < n; ++i)
        data.push_back(i);
    return data;
}

int getscore(const vi& data) {
    int score = 0;
    for (int i = 0; i < N; ++i) {
        if (data[i] < 0 || data[i] >= N) { fprintf(stderr, "out of range at %d\n", data[i]); }
        score += freq[i][data[i]];
    }
    return score;
}

int transform(int x) {
    // return x <= 1 ? 0 : lround(log(x) * 100);
    return x;
}

void prepare_freq_array(int rounds) {
    fprintf(stderr, "Preparing frequency array: %d Monte-Carlo simulations...\n", rounds);

    for (int k = 0; k < rounds; ++k) {
        vi data = get_rangearray(N);
        bad_shuffle(data);
        for (int i = 0; i < N; ++i)
            freq[i][data[i]]++;
    }

    // transform data to improve accuracy
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            freq[i][j] = transform(freq[i][j]);

    fprintf(stderr, "Frequency array finished.\n");
}

int get_cutoff_score() {
    fprintf(stderr, "Calculating cutoff scores...\n");

    vi good_samples;
    good_samples.reserve(sample_size);
    for (int k = 0; k < sample_size; ++k) {
        vi data = get_rangearray(N);
        good_shuffle(data);
        good_samples.push_back(getscore(data));
    }
    sort(good_samples.begin(), good_samples.end(), std::greater<int>());
    
    vi bad_samples;
    bad_samples.reserve(sample_size);
    for (int k = 0; k < sample_size; ++k) {
        vi data = get_rangearray(N);
        bad_shuffle(data);
        bad_samples.push_back(getscore(data));
    }
    sort(bad_samples.begin(), bad_samples.end());

    int badcount;
    for (badcount = 0; badcount < sample_size; ++badcount) {
        if (bad_samples[badcount] > good_samples[badcount])
            break;
    }

    fprintf(stderr, "bad chance=%d/%d, cutoff=%d\n", badcount, sample_size, bad_samples[badcount]);
    return bad_samples[badcount];
}

template<class T>
void solve(int k, T cutoff) {
    printf("Case #%d: ", k+1);

    int N1 = getInt();  // empty read
    if (N != N1) fprintf(stderr, "ERROR\n");
    
    vi data;
    data.reserve(N);
    for (int i = 0; i < N; ++i) {
        data.push_back(getInt());
    }

    T score = getscore(data);

    if (score > cutoff)
        printf("BAD\n");
    else
        printf("GOOD\n");
}

int main(int argc, char** argv) {
    random_initialize();

    if (argc > 1) {
        int n = atoi(argv[1]);
        if (n > 0)
            monte_carlo_rounds = n;
    }
    prepare_freq_array(monte_carlo_rounds);
    int cutoff = get_cutoff_score();
/* Remove to solve the Google Code Jam data set.
    int T = getInt();
    for (int k = 0; k < T; ++k)
        solve(k, cutoff);
*/
    fprintf(stderr, "Finished with cutoff = %d.\n", cutoff);
   
    return 0;
}