Single Round Match 769 Editorials

BallsOnAMeadow 

Used as: Division Two - Level One:

The answer is the number of times “(” appears in the meadow + the number of times “)” appears in the meadow - the number of times “()” appears in the meadow.Code by Patrik:

def count(self, m):
s = 0
for i in range(len(m)):
c = m[i]
if c == '(':
s += 1
elif c == ')' and m[i-1] != '(':
s +=1
return s

ReallyMagicSquare 

Used as: Division Two - Level Two:

Let’s name the matrix, a. Let’s construct the matrix row by row. The first row is given. How to find the second row?

a[1][1] (0-based) is given. We know a[0][0] + a[1][1] + a[2][2] + … + a[n - 1][n - 1] = a[0][1] + a[1][0] + a[2][2] + … + a[n - 1][n - 1] ⇒ a[0][0] + a[1][1] = a[0][1] + a[1][0]

To generalize the fact, for every r1, r2, c1, c2 ⇒ a[r1][c1] + a[r2][c2] = a[r1][c2] + a[r2][c1].

So a[1][0] = a[0][0] + a[1][1] - a[0][1].

To generalize, for a[1][i] (i > 1): a[1][i] = a[0][i] + a[1][1] - a[0][1].

To generalize for other rows, when i ≠ j, a[i][j]  = a[0][j] + a[i][i] - a[0][i].Code by cntswj (modified):

def reconstruct(self, topRow, mainDiagonal):
n = len(topRow)
square = [[None] * n for _ in range(n)]
square[0] = topRow
for i in range(1, n):
square[i][i] = mainDiagonal[i]
for j in range(n):
if i != j:
square[i][j] = square[0][j] + square[i][i] - square[0][i]
ret = []
for row in square:
ret += row

return ret

PrimePruning 

Used as: Division Two - Level Three:

Used as: Division One - Level One:

Greedy. We try to make the first character maximum possible. Then try to make the second character maximum possible, …

Let H = N - E.

What is the best option for the first character? Look for the maximum character in the first N - H + 1 characters (choose the first, in case of tie). Similarly for the next characters. The time complexity is O(NH). Although we can improve it to O(N log N), it’s not needed.

The fact comes to mind is, after some N, we always have H “z” characters, so we can choose them all and this is the best possible answer.

Code by tourist:

string maximize(int N, int E) {
int keep = N - E;
string s = "";
vector<int p;
int cc = 0;
for (int i = 2; ; i++) {
bool prime = true;
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
prime = false;
break;
}
}
if (!prime) {
continue;
}
s += (char) ('a' + i % 26);
cc += (s.back() == 'z');
if (cc == keep || (int) s.size() == N) {
break;
}
}
N = (int) s.size();
int start = 0;
string ret = "";
for (int i = 0; i < keep; i++) {
int rm = N - start;
char mx = ' ';
int pos = -1;
for (int j = start; j <= N - keep + i; j++) {
if (s[j] mx) {
mx = s[j];
pos = j;
}
}
ret += s[pos];
start = pos + 1;
}
return ret;
}

SchedulingWoes 

Used as: Division One - Level Two:

Sort exams by their date. Let’s keep the best answer while iterating exams from the first one to the last one.

Consider till a specific exam like (D, T) we succeed in passing several exams. Now there are two cases to consider:

• We can add (D, T) to the answer too. It can be checked if we keep the number of mornings we have studied for current passed exams.

• We can not add (D, T) to the answer. Let’s try to substitute it with another exam in the current answer. The substitution is affordable if there is a passed exam in the current answer which needs more time to pass. So we can remove the unprofitable exam from the answer and add (D, T) to the answer instead. This can be done if we keep exams in a heap (C++ std::set or std::priority_queue).

Total time complexity is O(n log n).Code (neal_wu):

int study(int N, int seed, vector<int Dprefix, int maxD, vector<int Tprefix, int factor) {
vector<long long random(2 * N);
random[0] = seed;

for (int i = 1; i < 2 * N; i++)
random[i] = (random[i - 1] * 1103515245 + 12345) % (1LL << 31);

vector<long long D(N), T(N);

for (int i = 0; i < (int) Dprefix.size(); i++) {
D[i] = Dprefix[i];
T[i] = Tprefix[i];
}

for (int i = (int) Dprefix.size(); i < N; i++) {
D[i] = 1 + random[2 * i] % maxD;
long long maxT = max(1LL, D[i] / factor);
T[i] = 1 + random[2 * i + 1] % maxT;
}

vector<pair<long long, long long exams;

for (int i = 0; i < N; i++)
exams.emplace_back(D[i], T[i]);

sort(exams.begin(), exams.end());
priority_queue<long long pq;
int pass_count = 0;
long long current_day = 0, free_days = 0;

for (pair<long long, long long &exam : exams) {
long long D = exam.first;
long long T = exam.second;

free_days += D - current_day;
current_day = D;

if (free_days < T && !pq.empty() && pq.top() T) {
free_days += pq.top();
pass_count--;
pq.pop();
}

if (free_days = T) {
free_days -= T;
pass_count++;
pq.push(T);
}
}

return pass_count;
}

ThreeColorTrees 

Used as: Division One - Level Three:

Let’s start with an easier task. The tree is given, just count the number of ways to color it. Here is it:

static double count(int[] p) {
if (p[0] != -1) throw new RuntimeException();
for (int i = 1; i < p.length; ++i) if (p[i] = i) throw new RuntimeException();
double[][] res = new double[p.length][4];
for (int i = 0; i < p.length; ++i) {
res[i][0] = 2 * DELTA;
res[i][1] = 1 * DELTA;
}
for (int i = p.length - 1; i 0; --i) {
double[] nr = new double[4];
for (int a = 0; a < 4; ++a) {
for (int b = 0; b < 4; ++b) {
if ((a & 1) != 0) {
if (b != 0) continue;
}
if ((a & 2) != 0) {
if ((b & 1) != 0) continue;
}
nr[(a | (b << 1)) & 3] += res[p[i]][a] * res[i][b] * INVDELTA;
}
}
res[p[i]] = nr;
}
double s = 0;
for (double x : res[0]) s += x;
return s;
}

The function uses dp on a tree to count the number of ways. To avoid inf values, it uses DELTA = 1e-130 and INVDELTA = 1e130.

Now, we need to check some patterns. Path works for small n’s. Binary tree is not good. Generating some good random trees with small n leads to trees like this:

Trees like ternary tree, but added a vertex on each edge. We can generate them by this code:

for (int i = 1; i < n; ++i)
res[i] = i % 2 == 0 ? i - 1 : i / 6;

Check it against any possible n. It doesn’t work for 12, 24, 36. The first idea comes to mind is to change it to:

for (int i = 1; i < n; ++i)
res[i] = i % 2 != 0 ? i - 1 : i / 6;

And it works!

Here is the code (by Arpa):

public int[] construct(int n) {
int[] res = new int[n];
if(n % 12 == 0)
for (int i = 1; i < n; ++i)
res[i] = i % 2 != 0 ? i - 1 : i / 6;
else
for (int i = 1; i < n; ++i)
res[i] = i % 2 == 0 ? i - 1 : i / 6;
return Arrays.copyOfRange(res, 1, res.length);
}

Also, this code by Petr uses local search and it works:

import java.util.Arrays;
import java.util.Random;

public class ThreeColorTrees {
static double DELTA = 1e-130;
static double INVDELTA = 1e130;

public int[] construct(int N) {
int[] res = new int[N];
for (int i = 0; i < N; ++i) res[i] = i - 1;
double need = (1 + 1e-9) * DELTA;
for (int i = 0; i < N; ++i) need *= 2.62;
double sofar = count(res);
Random random = new Random(754315351351L);
while (sofar < need) {
int cur = 2 + random.nextInt(N - 2);
int dest = random.nextInt(cur);
if (dest != res[cur]) {
int saved = res[cur];
res[cur] = dest;
double got = count(res);
if (got sofar) {
sofar = got;
} else {
res[cur] = saved;
}
}
}
return Arrays.copyOfRange(res, 1, res.length);
}

static double count(int[] p) {
if (p[0] != -1) throw new RuntimeException();
for (int i = 1; i < p.length; ++i) if (p[i] = i) throw new RuntimeException();
double[][] res = new double[p.length][4];
for (int i = 0; i < p.length; ++i) {
res[i][0] = 2 * DELTA;
res[i][1] = 1 * DELTA;
}
for (int i = p.length - 1; i 0; --i) {
double[] nr = new double[4];
for (int a = 0; a < 4; ++a) {
for (int b = 0; b < 4; ++b) {
if ((a & 1) != 0) {
if (b != 0) continue;
}
if ((a & 2) != 0) {
if ((b & 1) != 0) continue;
}
nr[(a | (b << 1)) & 3] += res[p[i]][a] * res[i][b] * INVDELTA;
}
}
res[p[i]] = nr;
}
double s = 0;
for (double x : res[0]) s += x;
return s;
}

}