Submission #160332

#	Time	Username	Problem	Language	Result	Execution time	Memory
160332		model_code	Password (RMI18_password)	C11	100 / 100	192 ms	404 KiB

password

/**
 * 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;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20