/**
* Count symbol frequencies. Choose a symbol at random and count the
* frequencies of other symbols to its left and right. Then solve each side
* recursively.
*
* The recurrence for the number of queries is
*
* Q(n) = num_symbols_used_in_subproblem - 1 + 2 Q(n / 2)
*
* This performs sigma - 1 queries for larger subproblems, but only n - 1 when
* n < sigma. Computing the sum by hand yields a theoretical maximum of N(2 +
* log sigma), or 33,500 for the given parameters, although in practice it
* never exceeds 24,000.
*
* The implementation wastes a factor of sigma. We could shave it off by
* storing subproblems as pairs <symbol, frequency> for symbols in use (as
* opposed to all the sigma frequencies).
*
* Author: Catalin Francu
**/
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAX_N 5000
#define MAX_SIGMA 26
char q[MAX_N + 1]; /* build queries here */
char sol[MAX_N + 1]; /* build solution here */
int f[MAX_N][MAX_SIGMA];
int lf[MAX_SIGMA]; /* frequencies left of the current subproblem */
int n, s, solLen;
int query(char *q);
/* run s-1 queries to determine element frequencies */
/* the last frequency is computed by difference */
void findFrequencies() {
int remainder = n;
q[n] = '\0';
for (int i = 0; i < s - 1; i++) {
memset(q, 'a' + i, n);
f[0][i] = query(q);
remainder -= f[0][i];
}
f[0][s - 1] = remainder;
}
/* Choose a random character from the current symbol set. If we choose the */
/* 5th occurrence of the 'c' symbol, set *sym = 2, *k = 4 (0-based). */
void chooseRandom(int level, int* sym, int* k) {
/* find the problem size */
int len = 0;
for (int i = 0; i < s; i++) {
len += f[level][i];
}
*k = rand() % len;
*sym = 0;
while (*k >= f[level][*sym]) {
*k -= f[level][*sym];
(*sym)++;
}
}
void solve(int level) {
/* count used symbols */
int numUsed = 0, solc, solf;
for (int i = 0; i < s; i++) {
if (f[level][i]) {
numUsed++;
solc = i;
solf = f[level][i]; /* syntactic sugar */
}
}
if (numUsed == 0) {
return;
}
if (numUsed == 1) {
memset(sol + solLen, 'a' + solc, solf);
solLen += solf;
lf[solc] += solf;
return;
}
int sym, k, answer;
/* choose a random symbol */
chooseRandom(level, &sym, &k);
/* output enough copies of the pivot so that all queries */
/* pass through the pivot */
memset(q, 'a' + sym, lf[sym] + k + 1);
/* compute frequencies of left subproblem */
for (int i = 0; i < s; i++) {
if (i == sym) {
f[level + 1][i] = k;
} else if (f[level][i]) {
/* Run a query to count the number of i symbols right of the pivot. */
/* The query consists of: */
/* - all copies of sym up to the pivot, including those already solved; */
/* - all copies of i except those already solved. */
memset(q + lf[sym] + k + 1, 'a' + i, f[0][i] - lf[i]);
q[lf[sym] + k + 1 + f[0][i] - lf[i]] = '\0';
/* The answer consists of: */
/* - number of sym's up to the pivot */
/* - number of i's to the right of the current problem */
/* - number of i's in the right subproblem */
/* We want the number of i's in the left subproblem, which we can */
/* compute by difference. */
answer = query(q);
answer -= lf[sym] + k + 1; /* keep just the i's */
int left = f[0][i] - answer - lf[i];
f[level + 1][i] = left;
} else {
f[level + 1][i] = 0;
}
}
solve(level + 1);
/* output the pivot itself */
sol[solLen++] = 'a' + sym;
lf[sym]++;
/* compute frequencies of the right subproblem by difference (f[level] */
/* stores the entire problem and f[level + 1] stores the left subproblem) */
for (int i = 0; i < s; i++) {
f[level + 1][i] = f[level][i] - f[level + 1][i];
}
f[level + 1][sym]--; /* subtract the pivot itself */
solve(level + 1);
}
char* guess(int localN, int localS) {
srand(time(NULL));
n = localN;
s = localS;
findFrequencies();
solve(0);
sol[solLen] = '\0';
return sol;
}
