## March 24, 2020 Single Round Match 769 Editorials

**BallsOnAMeadow**

Used as: Division Two – Level One:

Value | 250 |

Submission Rate | 147 / 165 (89.09%) |

Success Rate | 128 / 147 (87.07%) |

High Score | resh.root for 248.38 points (2 mins 18 secs) |

Average Score | 213.16 (for 128 correct submissions) |

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:

Value | 500 |

Submission Rate | 56 / 165 (33.94%) |

Success Rate | 45 / 56 (80.36%) |

High Score | qixiao for 452.75 points (9 mins 22 secs) |

Average Score | 275.64 (for 45 correct submissions) |

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:

Value | 1000 |

Submission Rate | 9 / 165 (5.45%) |

Success Rate | 0 / 9 (0.00%) |

High Score | null for null points (NONE) |

Average Score | No correct submissions |

Used as: Division One – Level One:

Value | 250 |

Submission Rate | 95 / 116 (81.90%) |

Success Rate | 67 / 95 (70.53%) |

High Score | tourist for 236.94 points (6 mins 44 secs) |

Average Score | 174.68 (for 67 correct submissions) |

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:

Value | 500 |

Submission Rate | 60 / 116 (51.72%) |

Success Rate | 42 / 60 (70.00%) |

High Score | neal_wu for 469.47 points (7 mins 20 secs) |

Average Score | 345.22 (for 42 correct submissions) |

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:

Value | 1000 |

Submission Rate | 30 / 116 (25.86%) |

Success Rate | 1 / 30 (3.33%) |

High Score | Petr for 361.20 points (43 mins 22 secs) |

Average Score | 361.20 (for 1 correct submission) |

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

**a.poorakhavan**

Guest Blogger