oj.uz

Submission #160332

# Submission time Handle Problem Language Result Execution time Memory
160332 2019-10-27T02:47:16 Z model_code Password (RMI18_password) C
100 / 100
 192 ms 404 KB 
/**
 * 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Guessed the password with 60 queries.
2 Correct 3 ms 376 KB Guessed the password with 108 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Guessed the password with 28 queries.
2 Correct 3 ms 376 KB Guessed the password with 65 queries.
3 Correct 2 ms 376 KB Guessed the password with 11 queries.
4 Correct 3 ms 376 KB Guessed the password with 105 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 376 KB Guessed the password with 1725 queries.
2 Correct 25 ms 376 KB Guessed the password with 2232 queries.
3 Correct 38 ms 376 KB Guessed the password with 3377 queries.
4 Correct 66 ms 308 KB Guessed the password with 5372 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Guessed the password with 60 queries.
2 Correct 3 ms 376 KB Guessed the password with 108 queries.
3 Correct 2 ms 376 KB Guessed the password with 28 queries.
4 Correct 3 ms 376 KB Guessed the password with 65 queries.
5 Correct 2 ms 376 KB Guessed the password with 11 queries.
6 Correct 3 ms 376 KB Guessed the password with 105 queries.
7 Correct 21 ms 376 KB Guessed the password with 1725 queries.
8 Correct 25 ms 376 KB Guessed the password with 2232 queries.
9 Correct 38 ms 376 KB Guessed the password with 3377 queries.
10 Correct 66 ms 308 KB Guessed the password with 5372 queries.
11 Correct 63 ms 376 KB Guessed the password with 5906 queries.
12 Correct 67 ms 376 KB Guessed the password with 5986 queries.
13 Correct 79 ms 248 KB Guessed the password with 7923 queries.
14 Correct 73 ms 392 KB Guessed the password with 7708 queries.
15 Correct 66 ms 376 KB Guessed the password with 7929 queries.
16 Correct 75 ms 248 KB Guessed the password with 8049 queries.
17 Correct 50 ms 376 KB Guessed the password with 6704 queries.
18 Correct 67 ms 404 KB Guessed the password with 6849 queries.
19 Correct 54 ms 304 KB Guessed the password with 6840 queries.
20 Correct 73 ms 248 KB Guessed the password with 6982 queries.
21 Correct 50 ms 376 KB Guessed the password with 4719 queries.
22 Correct 30 ms 308 KB Guessed the password with 4612 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Guessed the password with 60 queries.
2 Correct 3 ms 376 KB Guessed the password with 108 queries.
3 Correct 2 ms 376 KB Guessed the password with 28 queries.
4 Correct 3 ms 376 KB Guessed the password with 65 queries.
5 Correct 2 ms 376 KB Guessed the password with 11 queries.
6 Correct 3 ms 376 KB Guessed the password with 105 queries.
7 Correct 21 ms 376 KB Guessed the password with 1725 queries.
8 Correct 25 ms 376 KB Guessed the password with 2232 queries.
9 Correct 38 ms 376 KB Guessed the password with 3377 queries.
10 Correct 66 ms 308 KB Guessed the password with 5372 queries.
11 Correct 63 ms 376 KB Guessed the password with 5906 queries.
12 Correct 67 ms 376 KB Guessed the password with 5986 queries.
13 Correct 79 ms 248 KB Guessed the password with 7923 queries.
14 Correct 73 ms 392 KB Guessed the password with 7708 queries.
15 Correct 66 ms 376 KB Guessed the password with 7929 queries.
16 Correct 75 ms 248 KB Guessed the password with 8049 queries.
17 Correct 50 ms 376 KB Guessed the password with 6704 queries.
18 Correct 67 ms 404 KB Guessed the password with 6849 queries.
19 Correct 54 ms 304 KB Guessed the password with 6840 queries.
20 Correct 73 ms 248 KB Guessed the password with 6982 queries.
21 Correct 50 ms 376 KB Guessed the password with 4719 queries.
22 Correct 30 ms 308 KB Guessed the password with 4612 queries.
23 Correct 60 ms 404 KB Guessed the password with 10435 queries.
24 Correct 47 ms 312 KB Guessed the password with 8486 queries.
25 Correct 161 ms 392 KB Guessed the password with 16389 queries.
26 Correct 107 ms 376 KB Guessed the password with 12470 queries.
27 Correct 183 ms 304 KB Guessed the password with 18370 queries.
28 Correct 94 ms 308 KB Guessed the password with 11859 queries.
29 Correct 192 ms 316 KB Guessed the password with 19894 queries.
30 Correct 92 ms 304 KB Guessed the password with 10540 queries.