June 21, 2020 Single Round Match 787 Editorials
Round story
Yeah, nice! The round has now finished. Do not be tired, everyone! The effort of around a month comes down to 1 hour and 35 mins of intensively watching everyone compete. Thanks for taking out time and competing.
First, let me take this opportunity to tell you more about Aqa Asadi.
Aqa means “Sir” in Persian. Abolfazl Asadi (known as Aqa Asadi) is one of the most experienced (maybe the most) olympiad teachers, I have known over the years. Four years ago, when I was preparing for the INOI, he taught me combinatorics at my school.
The important fact about Aqa Asadi, which makes him unique, is that he also taught me ethics, ideology, and lifestyle in addition to combinatorics and graphs. Regardless of his achievements and honors, he’s a worthy idol for students.
So, here is a suitable place to say: “Thank you Aqa Asadi! You helped me be what I am today.”
There’s another teacher who is still playing a big role in my upbringing,“Mojtaba FayazBakhsh”, was and is currently my greatest teacher and mentor.
This contest is to honour my teachers, without their guidance I wouldn’t have been here preparing a round for you.
The Problem Set
The problem set for Div I was in fact harder than it should be. We shifted problems and added a new problem as Div. 1 Medium in the recent days.I’ll use that nice hard problem as soon as possible in another contest.
For Div. 2, it was reversed. Div. 2 Hard was “AqaAsadiTrains”, which was slightly harder. On Friday, after misof’s suggestion, I proposed the new problem, “AqaAsadiGroups”.
[misof] helped me a lot. He proofread statements, verify test cases, implements second solutions, etc. Also, [hmehta] helped me a lot, he’s really kind. Here is a good place to thank the Topcoder Team for their bits of help. The preparation was a smooth process. No stress, no rush, no fear, no concern. It was the most concern-free contest I have authored until today.
I have a written and prepared proposal for another contest to hold on Topcoder. I hope to use your feedback for the next contest.
If you have prepared a contest before, can you guess for which problem the test creation was the hardest? Yes! Correct. Div I Hard!
Div II Easy: AqaAsadiNames
Editorial
The solution is completely described in the problem statement. We discuss implementation details.
Define a function that returns gender.
private static boolean gender(String name){
return !(name.charAt(0) == 'A' || name.charAt(0) == 'O'
|| name.charAt(0) == 'I' || name.charAt(0) == 'U' || name.charAt(0) == 'O' || name.charAt(0) == 'Y');
}
Also split names using space.
For example in Java: String[] DadParts = Dad.split(“\\s+”);
In python: Dad.split()
int space_position = Dad.find(' ');
string Dad1 = Dad.substr(0, space_position);
string Dad2 = Dad.substr(space_position + 1);
The remaining part is easy, just as the problem statement.
private static boolean gender(String name){
return !(name.charAt(0) == 'A' || name.charAt(0) == 'O'
|| name.charAt(0) == 'I' || name.charAt(0) == 'U' || name.charAt(0) == 'O' || name.charAt(0) == 'Y');
}
public static String getName(String Dad, String Mom, String FirstChild, String Gender){
boolean IsBoy = Gender.equals("Boy");
boolean isFirstChildBoy = gender(FirstChild);
String[] DadParts = Dad.split("\\s+");
String[] MomParts = Mom.split("\\s+");
String[] BroParts = FirstChild.split("\\s+");
if(isFirstChildBoy != IsBoy)
if(IsBoy)
return DadParts[1] + " " + DadParts[0];
else
return MomParts[1] + " " + MomParts[0];
else
if(IsBoy)
return DadParts[0] + " " + BroParts[1];
else
return MomParts[0] + " " + BroParts[1];
}
Python Code by misof:
def get_gender(name):
return 'Girl' if name[0] in 'AEIOUY' else 'Boy'
class AqaAsadiNames:
def getName(self, dad, mom, first_child, second_gender):
same_gender_parent = dad if second_gender == 'Boy' else mom
first_gender = get_gender(first_child)
if first_gender == second_gender:
x, _ = same_gender_parent.split()
_, y = first_child.split()
return x + ' ' + y
else:
x, y = same_gender_parent.split()
return y + ' ' + x
Div II Medium: AqaAsadiPlays
Hint
Aqa Asadi keeps some elements from the end in the sorted order.
Editorial
We want to prove that Aqa Asadi keeps some elements from the end in the sorted order. Consider the inverse case. So there is a number x that is chosen in the Ninja team and y > x that is not chosen. For sure, the power of the Ninja team is less than or equal to x, and y > the power of the Ninja team, contradiction!
So sort the students. Iterate from the last element (largest) to the first element, keep track of gcd of seen elements, the answer is maximum sz such that gcd of last sz elements is strictly more than a[n – sz].
public static int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
public static int getMin(int[] A){
Arrays.sort(A);
int g = 0, ans = A.length + 1;
for(int i = A.length - 1; i >= 0; i--){
if(A[i] < g)
ans = i + 1;
g = gcd(g, A[i]);
}
return A.length - ans;
}
Div II Hard: AqaAsadiGroups
Hint
Dynamic programming.
Editorial
dp[i][j] = smallest possible unbalance ratio considering the first i students and using j groups.
Answer is dp[n][k].
public static long minimumDifference(int[] Skills, int k){
int n = Skills.length;
long [][]dp = new long[n + 1][k + 1];
long s = 0;
for (int skill : Skills) s += skill;
for (int i = 1; i <= k; i++)
dp[0][i] = i * s * s;
for(int i = 0; i < n; i++)
for (int j = 1; j <= k; j++){
long cur = 0;
dp[i + 1][j] = Long.MAX_VALUE;
for (int l = i; l >= 0; l--) {
cur += Skills[l];
if(j > 1 || l == 0)
dp[i + 1][j] = min(dp[i + 1][j], dp[l][j - 1] + (cur * k - s) * (cur * k - s));
}
}
return dp[n][k];
}
Div I Easy: AqaAsadiMinimizes
Hint
Sort numbers.
Editorial
Consider answer achieved by i, j, i. e. there is no k, l such that |a[k] – a[l]| / |k – l| < |a[i] – a[j]| / |j – i|.
We suppose that a[i] <= a[j] and i < j (other cases are similarly handeled). Consider there is an index k, where a[i] <= a[k] <= a[j]. If k < i, it is easy to understand that k, j is a better pair, same for k > j.
When i < k < j, let: a = k – i, b = j – k, x = a[k] – a[i], y = a[j] – a[k]. We have inequalities:
As we supposed that i, j is a better pair than k, j: (x+y) / (a+b) < y / b => xb < ay
As we supposed that i, j is a better pair than i, k: (x+y) / (a+b) < x / a => xb > ay
It is a contradiction. So if there is such k one can find a better or equal answer. So candidates are (i, j)’s that are consecutive in sorted order. We sort indices in order of their value and try every two neighbors.
Time complexity: O(n log n).
public final static int mod = (int) (1e9 + 7);
public static double getMin(int[] P, int B0, int X, int Y, int N){
Pair[] a = new Pair[N];
for(int i = 0; i < P.length; i++)
a[i] = new Pair(P[i], i);
if(N > P.length)
a[P.length] = new Pair(B0, P.length);
for(int i = P.length + 1; i < N; i++)
a[i] = new Pair((int) (((long) a[i - 1].val * X + Y) % mod), i);
Arrays.sort(a);
double ans = 1e18;
for(int i = 1; i < N; i++)
ans = min(ans, abs(a[i].val - a[i - 1].val) / (double) abs(a[i].i - a[i - 1].i));
return ans;
}
private static class Pair implements Comparable<Pair>{
int val, i;
public Pair(int val, int i) {
this.val = val;
this.i = i;
}
@Override
public int compareTo(Pair p) {
if(val == p.val)
return 0;
return val < p.val ? -1 : 1;
}
}
Div I Medium: AqaAsadiTrains
Hint
Dp on range (L, R). But it’s not enough, add more data to your dp.
Editorial
The problem is similar to dynamic programming on range problems. But when we want to use dp[L][R], you can see that it is not enough.
Let’s add another dimension, dp[L][R][x] = maximum value we can gain using students in the range [L, R] such that at the end only one student playing in the post x remains.
dp[L][R][x] can be achieved in several ways:
- For some i, we achieve x from [L, i] and we sell the player achieved from [i + 1, R].
- For some i, we achieve x from [i + 1, R] and we sell the player achieved from [L, i].
- For some i, we achieve y from [L, i] and we achieve z from [i + 1, R], then either t[y][z] = x or t[z][y] = x.
There are negative prices, so we should handle cases that we will not sell all of the players. It is possible using a helper dp. dp2[L][R] is the best value we can achieve in the range [L, R].
public static int getMax(int[] C, int[] A, int[] T){
int k = C.length;
int n = A.length;
int[][] t = new int[k][k];
for (int i = 0; i < k; i++)
System.arraycopy(T, i * k, t[i], 0, k);
int [][][]dp = new int[n][n][k];
int [][]dp2 = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int l = 0; l < k; l++)
dp[i][j][l] = Integer.MIN_VALUE / 3;
for(int i = 0; i < n; i++)
dp[i][i][A[i]] = 0;
for(int len = 2; len <= n; len++)
for(int l = 0, r = len - 1; r < n; l++, r++) {
for (int i = l; i < r; i++) {
for (int x = 0; x < k; x++)
for (int y = 0; y < k; y++) {
dp[l][r][t[x][y]] = max(dp[l][r][t[x][y]], dp[l][i][x] + dp[i + 1][r][y]);
dp[l][r][t[y][x]] = max(dp[l][r][t[y][x]], dp[l][i][x] + dp[i + 1][r][y]);
dp[l][r][x] = max(dp[l][r][x], dp[l][i][x] + dp[i + 1][r][y] + C[y]);
dp[l][r][y] = max(dp[l][r][y], dp[l][i][x] + C[x] + dp[i + 1][r][y]);
}
dp2[l][r] = max(dp2[l][r], dp2[l][i] + dp2[i + 1][r]);
}
for (int x = 0; x < k; x++)
dp2[l][r] = max(dp2[l][r], dp[l][r][x] + max(0, C[x]));
}
return dp2[0][n - 1];
}
Div I Hard: AqaAsadiSaves
Hint
When Aqa Asadi adds an edge, edges in a path survive.
Editorial
The damage of non-cut edges is zero. Consider Aqa Asadi adds the edge between v, u, damage of cut edges in the path between v, u becomes zero.
We use binary search. We want to check if it is possible to add an edge such that damage becomes less than or equal to X. To check this, we mark all of the edges with damage > X, they should lie on a path. To check if edges lie on a path we check that there is no vertex that when we root the graph from this vertex, it has marked edges in the subtree of more than two of its children.
public static final int maxn = (int) (2e5 + 14);
public static boolean [] seen, cut;
public static ArrayList<ArrayList<Integer>> g;
private static int[] h;
private static long[] damage;
private static int[] sz, root;
private static int[] par;
public static long minDamage(int N, int M, int []PA, int []PB, int Seed, int X, int Y){
int []a = new int[M], b = new int[M];
h = new int[N];
sz = new int[N];
par = new int[N];
root = new int[N];
damage = new long[N];
seen = new boolean[N];
cut = new boolean[N];
System.arraycopy(PA, 0, a, 0, PA.length);
System.arraycopy(PB, 0, b, 0, PB.length);
for(int i = PA.length; i < M; i++) {
a[i] = Seed;
Seed = (int) (((long) Seed * X + Y) % N);
}
for(int i = PA.length; i < M; i++) {
b[i] = Seed;
Seed = (int) (((long) Seed * X + Y) % N);
}
g = new ArrayList<>(N);
for (int i = 0; i < N; i++)
g.add(new ArrayList<Integer>());
for (int i = 0; i < M; i++) {
g.get(a[i]).add(b[i]);
g.get(b[i]).add(a[i]);
}
for (int i = 0; i < N; i++)
if(!seen[i]){
root[i] = i;
hi(i, -1, N);
}
for (int i = 0; i < N; i++)
if(cut[i])
damage[i] = sz[i] * (long) (sz[root[i]] - sz[i]);
long lo = -1, hi = (long) N * N;
while(hi - lo > 1){
long mid = (lo + hi) / 2;
if(check(N, mid))
hi = mid;
else
lo = mid;
}
return hi;
}
private static boolean check(int N, long mid){
for(int i = 0; i < N; i++)
seen[i] = false;
int cmps = 0;
boolean ok = true;
for(int i = 0; i < N; i++)
if(damage[i] > mid && !seen[i]) {
int back = dfs(i, -1, mid);
if(back > 0)
cmps++;
if(back > 2)
ok = false;
}
return ok && cmps < 2;
}
private static int dfs(int v, int p, long mid) {
int ret = 0;
seen[v] = true;
for(int u : g.get(v))
if(!seen[u]){
int b = dfs(u, v, mid);
if(b > 1)
return Integer.MAX_VALUE;
ret += par[v] == u && damage[v] > mid || b > 0 ? 1 : 0;
}
return max(damage[v] > mid ? 1 : 0, ret);
}
static int hi(int v, int p, int N){
int ret = h[v];
seen[v] = true;
sz[v] = 1;
int parEdge = 0;
for(int u : g.get(v)){
if(!seen[u]){
h[u] = h[v] + 1;
root[u] = root[v];
par[u] = v;
int t = hi(u, v, N);
if(t == h[u])
cut[u] = true;
sz[v] += sz[u];
ret = min(ret, t);
}
else if(u != p && u != v)
ret = min(ret, h[u]);
else if (u == p)
parEdge++;
}
if(parEdge > 1)
ret = min(ret, h[v] - 1);
return ret;
}
Guest Blogger
