April 11, 2020 Single Round Match 783 Editorials
PosNegDice
Keep two arrays: positiveValueCounts and negativeValueCounts.
In the first array, we will keep positive dices. We will keep negative dices in the second one. Then we will remove positive and negative die with the same value. It is, for each i, we will subtract min(positiveValueCounts[i], negativeValueCounts[i]) from positiveValueCounts[i] and negativeValueCounts[i].
Finally, we check if we have positive positiveValueCounts[i] where i <= T. Also we sum up all negativeValueCounts and return it as a point of stress.
public int[] evaluateRoll(int T, int[] positiveDice, int[] negativeDice) {
// count the number of occurrences for each value
int[] positiveValueCounts = new int[7];
int[] negativeValueCounts = new int[7];
for (int d : positiveDice) ++positiveValueCounts[d];
for (int d : negativeDice) ++negativeValueCounts[d];
// eliminate all equal pairs at once
for (int d=1; d<=6; ++d) {
int eliminated = Math.min( positiveValueCounts[d], negativeValueCounts[d] );
positiveValueCounts[d] -= eliminated;
negativeValueCounts[d] -= eliminated;
}
// compute the answer by examining what remained
int[] answer = {0, 0};
for (int d=1; d<=6; ++d) {
if (d <= T && positiveValueCounts[d] > 0) answer[0] = 1;
answer[1] += negativeValueCounts[d];
}
return answer;
}
BouncingBall
Hint: Simulate the process
From one hill to another, we first fall down and raise up again. We call this process a step. We keep the time and height at the start of each step, then step by step we check if we exceeded from the given time and print the answer.
Note that the maximum number of steps we need to process is not so much and small enough to pass the time limit. One can check it when g = 1000, h = 10, p = 10, t = 50, number of steps is 51.
The below code by misof is enough for understanding the math behind:
Hint: Simulate the process.
double freeFallDuration(double g, double h) {
// given g and h, what is the duration of the free fall from height h to the ground?
// this is then also the time the ball takes when thrown vertically upwards to height h (time reversal argument)
// h = gt^2 / 2 => t = sqrt(2h/g)
return Math.sqrt(2*h/g);
}
double freeFallPosition(double g, double h, double t) {
// given g, h, t such that t <= freeFallPosition(g,h),
// what is the position of the ball t seconds after the free fall from height h started?
return h - g*t*t/2;
}
public double getPosition(int gCm, int h0, int p, int tGoal) {
double t = 0;
double h = h0;
double g = gCm / 100.;
while (true) {
double tFall = freeFallDuration(g,h);
if (t + tFall >= tGoal) {
// we reach the goal time during the fall downwards
double tDuringFall = tGoal - t;
return freeFallPosition(g,h,tDuringFall);
}
t += tFall;
// do the bounce, lose some height
h *= (100 - p) / 100.;
double tRise = freeFallDuration(g,h);
if (t + tRise >= tGoal) {
// we reach the goal time during the rise upwards
double tDuringRise = tGoal - t;
double tDuringFall = tRise - tDuringRise;
return freeFallPosition(g,h,tDuringFall);
}
t += tRise;
}
}
CardboardBoxes
Assume length >= width.
Area of the sides is 2 * height * (width + length).
The other dimension of top flaps will be width/2, so their area is width * (width + length).
The same for the bottom.
So S = 2 * (width + length) * (width + height).
To illustrate this, you can actually cut out such a box from a (2L+2W) * (H+W) cardboard rectangle as shown below. Lines inside are cuts, dots are folds, asterisk edges have to be taped together. This is how you can really produce such boxes with minimum waste.
W L W L
+----+---------+----+---------+
| | | | | W/2
+ .. + . . . . + .. + . . . . +
* . . . *
* . . . * H
* . . . *
* . . . *
+ .. + . . . . + .. + . . . . +
| | | | | W/2
+----+---------+----+---------+
So possible options of width + length are divisors of S / 2. We can find divisors of S / 2 in O(S). After fixing width + length = k, we know that width + height = S/k. Once we choose width the other two dimensions are fixed, and we can compute the number of valid widths in constant time.
Code by misof:
long processKnownLplusW(long S, long LplusW) {
long HplusW = S / LplusW;
long maxW = Math.min( LplusW/2, HplusW-1 );
return maxW;
}
public long count(long S) {
if (S % 2 == 1) return 0;
S /= 2;
long answer = 0;
for (long d=1; d*d <= S; ++d) if (S % d == 0) {
answer += processKnownLplusW(S,d);
if (d < S/d) answer += processKnownLplusW(S,S/d);
}
return answer;
}
ABBAReplace
Hint: Consider a similar process from the end to the beginning.
Direct simulation is ugly. We can visualize the process as “Bs want to go to the left”, but the process is complicated: e.g., there can be Bs that alternately move and have to stay in place.
There are two observations that can really simplify the solution. First, we can relax the original task by allowing some letters to stay in place instead of being swapped. The minimal number of turns clearly remains the same because greedily making all possible swaps produces one possible optimal solution for the new task. However, now there will be other optimal solutions, too, and those will be easier to construct.
Second, consider the new problem backwards. What do we have in the end? Something like “BBB…BAAA…”. Some of these Bs are in their right places, others need to move to the right. The rightmost B can start moving immediately and it will never be blocked. In the second step the rightmost two Bs can move, and so on. In this way, no B will ever get blocked by another one because the ones to its right started moving sooner and go farther right. Hence, we can simply compute each B’s travelling time as (the number of Bs to its right) plus (the number of steps it needs to make).
Code by misof:
public int countSteps(String Sprefix, int N, int seed, int threshold) {
StringBuilder sb = new StringBuilder(Sprefix);
long state = seed;
long modulus = 1L << 31;
while (sb.length() < N) {
state = (state * 1103515245 + 12345) % modulus;
if (state < threshold) sb.append("A"); else sb.append("B");
}
String S = sb.toString();
ArrayList<Integer> bindices = new ArrayList<Integer>();
for (int n=0; n<N; ++n) if (S.charAt(n) == 'B') bindices.add(n);
int BC = bindices.size();
int maxtime = 0;
for (int b=0; b<BC; ++b) {
int bdest = bindices.get(b);
if (bdest == b) continue;
maxtime = Math.max( maxtime, BC-1-b + bdest-b );
}
return maxtime;
}
RecursiveTournament
Hint: Calculate the answer for k = 1.
Let’s think about what a subgraph looks like? It consists of several groups of vertices say a1, a2, …, am, where for each vertex like v in ai, and u in aj v has a directed path to u if and only if i <= j.
It looks like a chain (maybe consists of one group, i. e. m = 1). Vertices in group a1 are strongly connected (similar for a2, a3, …, am), every vertex from a1 has a directed edge toward every vertex in a2, a3, …, am. Every vertex from a2 has a directed edge toward every vertex in a3, a4, …, am. Also, there is no edge from v in ai toward u in aj where i > j, otherwise, they can create a larger group together.
From the constraints, we straightly jump to dp on bitmasks! For each mask, let’s calculate part[mask][]. part[mask][v] (that v is present in the mask) is the group (ai) that v is present in it; when showing the vertices in the mask as the above format.
Let’s calculate part[mask]. Take a vertex like v from the mask. Let omask be a mask excluding v (omask = mask ^ (1 << v)). We need to find the rightmost group (with the largest index) that has a vertex that has an edge toward v, name it R. Similarly, find the leftmost group (with the lowest index) that has a vertex that v has an edge toward it, name it L. If R < L, v creates a new group. Otherwise, v will merge groups [L, R] together and join them.
In the end, we check if part[mask][] is 1 for all of the present vertices then mask is an SCC.
Now, let’s solve the general problem when k is not necessarily 1. Consider an SCC in the input graph with size x: v1, v2, …, vx. In the code below s[x] stands for the number of times it appears in the big tournament graph. What is s[x]?
How many vertices start with v1? b ^ (k – 1). Same for v2, v3, …, vx. We choose a non-empty subset of vertices from vertices starting with v1, another non-empty subset from vertices starting with v2, … . The number of ways to choose x vertices we counted here equals (2 ^ (b ^ (k – 1)) – 1) ^ x. Now we just counted the number of subsets of vertices in the big tournament such that at least two of them differ in the first bit. We go further for the second, third, …, k-th bit. When calculating the number for i-th bit, b ^ (i – 1) * (2 ^ (b ^ (k – i – 1)) – 1) ^ x. We have b ^ (i – 1) ways to choose the prefix for vertices.
In the end, we are able to calculate s[x] for each x in the range [1, n].
Overall time complexity is O(n * 2^n + nk).
Here is the code by lg5293:
int mod = 998244353;
int b;
int k;
long ans;
long[] s;
boolean[][] mat;
int max(int[] arr) {
int ret = arr[0];
for (int x : arr) ret = Math.max(x, ret);
return ret;
}
long mod_exp(long b, long e, long mod) {
long res = 1;
while (e > 0) {
if ((e & 1) == 1)
res = (res * b) % mod;
b = (b * b) % mod;
e >>= 1;
}
return res % mod;
}
public void dfs(int[] part, int mask, int idx) {
if (idx == b) {
if (Integer.bitCount(mask) > 1 && max(part) == 1) {
ans += s[Integer.bitCount(mask)];
if (ans >= mod) ans -= mod;
}
return;
}
dfs(Arrays.copyOf(part, part.length), mask, idx+1);
if (mask == 0) {
part[idx] = 1;
dfs(part, mask | (1 << idx), idx+1);
return;
}
int lowest = b, highest = 0;
for (int i = 0; i < idx; i++) {
if (((mask >> i) & 1) == 1) {
if (mat[i][idx]) lowest = Math.min(lowest, part[i]);
else highest = Math.max(highest, part[i]);
}
}
if (lowest == highest) {
part[idx] = lowest;
} else if (lowest > highest) {
// highest+1 == lowest
for (int i = 0; i < idx; i++) {
if (part[i] >= lowest) part[i]++;
}
part[idx] = highest + 1;
} else { // lowest < highest
for (int i = 0; i < idx; i++) {
if (part[i] >= lowest) {
if (part[i] > highest) {
part[i] += lowest - highest;
} else {
part[i] = lowest;
}
}
}
part[idx] = lowest;
}
dfs(part, mask | (1 << idx), idx + 1);
}
public int count(String[] graph, int k) {
b = graph.length;
mat = new boolean[b][b];
for (int i = 0; i < b; i++) {
for (int j = 0; j < b; j++) {
mat[i][j] = graph[i].charAt(j) == 'Y';
}
}
s = new long[b + 1];
for (int j = 0; j < k; j++) {
long r = mod_exp(b, k - j - 1, mod);
long mult = mod_exp(2, mod_exp(b, j, mod - 1), mod) - 1;
for (int i = 0; i <= b; i++) {
s[i] = (s[i] + r) % mod;
r = r * mult % mod;
}
}
ans = mod_exp(b, k, mod);
dfs(new int[b], 0, 0);
return (int)ans;
}
Guest Blogger
