March 9, 2020 Single Round Match 780 Editorials
Discuss problems here. If there is any problem in the editorial, or any question, feel free to post a comment.
ElevatorButtons
Used as: Division Two – Level One:
| Value | 300 |
| Submission Rate | 174 / 201 (86.57%) |
| Success Rate | 146 / 174 (83.91%) |
| High Score | racsosabe for 296.35 points (3 mins 9 secs) |
| Average Score | 215.21 (for 146 correct submissions) |
Keep a boolean array, toVisit. toVisit[i] is true if and only if the button i is pressed. Now, consider currentDirection = -1, elevator will see floors currentFloor, currentFloor – 1, … to down and then it’ll come up to the highest floor.
public int[] nextStops(int currentFloor, int currentDirection, int[] buttonsPressed) {
boolean[] toVisit = new boolean[1001];
for (int x : buttonsPressed) toVisit[x] = true;
int distinctFloors = 0;
for (boolean v : toVisit) if (v) ++distinctFloors;
int[] answer = new int[distinctFloors];
int idx = 0;
if (currentDirection == 1) {
for (int f=currentFloor+1; f<=1000; ++f) if (toVisit[f]) answer[idx++] = f;
for (int f=currentFloor-1; f>=0; --f) if (toVisit[f]) answer[idx++] = f;
} else {
for (int f=currentFloor-1; f>=0; --f) if (toVisit[f]) answer[idx++] = f;
for (int f=currentFloor+1; f<=1000; ++f) if (toVisit[f]) answer[idx++] = f;
}
return answer;
}
MemoryGame
Used as: Division Two – Level Two:
| Value | 500 |
| Submission Rate | 88 / 201 (43.78%) |
| Success Rate | 59 / 88 (67.05%) |
| High Score | racsosabe for 404.15 points (14 mins 34 secs) |
| Average Score | 279.58 (for 59 correct submissions) |
Follow the procedure in the statement. Note that at every moment, Alex has seen a prefix of cards. Start from the leftmost card, keep track of unmatched cards (seenValue in the code). Each time you pick a card if it’s has been seen before, match it, otherwise, pick the next card.
public long countSteps(int N, int seed) {
int[] location = new int[2*N];
for (int i=0; i<2*N; ++i) location[i] = i / 2;
long state = seed;
for (int i=2*N-1; i>=1; --i) {
int j = (int)(state % (i+1));
int tmp = location[i]; location[i] = location[j]; location[j] = tmp;
state = (state * 1103515245 + 12345) % (1L << 31);
int[] seenValue = new int[N];
for (int n=0; n<N; ++n) seenValue[n] = -1;
int lastSeenLocation = -1;
int matchedPairs = 0;
int stepsTaken = 0;
int knownPair = -1;
while (matchedPairs < N) {
++stepsTaken;
if (knownPair != -1) {
++matchedPairs;
knownPair = -1;
continue;
}
int v1 = location[++lastSeenLocation];
if (seenValue[v1] != -1) {
++matchedPairs;
continue;
}
seenValue[v1] = lastSeenLocation;
int v2 = location[++lastSeenLocation];
if (v1 == v2) {
++matchedPairs;
continue;
}
if (seenValue[v2] != -1) {
knownPair = v2;
} else {
seenValue[v2] = lastSeenLocation;
}
}
return stepsTaken;
}
BeatTheStar
Used as: Division Two – Level Three:
| Value | 1000 |
| Submission Rate | 19 / 201 (9.45%) |
| Success Rate | 14 / 19 (73.68%) |
| High Score | heno239 for 848.12 points (12 mins 29 secs) |
| Average Score | 725.35 (for 14 correct submissions) |
A player will win if his score is strictly more than n * (n + 1) / 4. Reordering games will not change the answer. Consider the game G is played first. We’re interested on scores like s, which s < n * (n + 1) / 4 (so it’s not enough for winning the game) and s + G > n * (n + 1) / 4 (so it’s enough for winning the game).
Now we need dp[i] — probability of gaining i scores in games other than G. It’s a classical knapsack problem.
We can describe the subproblem like the following: We have m items with weights w[1…m]. For a specified weight like W, calculate the probability that if we choose items randomly, the sum of weights of items equals W. The solution uses dynamic programming. dp[i][j] = consider the first i elements, what is the probability that if we choose items randomly, the sum of weights of items equals W. dp[i][j] = dp[i – 1][j] / 2 + dp[i – 1][j – w[i]] / 2.
public double doesItMatter(int N, int G) {
double[] oldpp = {1.};
int maxscore = 0;
for (int n=1; n<=N; ++n) if (n != G) {
double[] newpp = new double[maxscore+n+1];
for (int s=0; s<=maxscore; ++s) {
newpp[s] += oldpp[s] / 2;
newpp[s+n] += oldpp[s] / 2;
}
maxscore += n;
oldpp = newpp;
}
double answer = 0;
int total = N*(N+1) / 2;
for (int s=0; s<=maxscore; ++s) if (2*s < total && 2*(s+G) > total) answer += oldpp[s];
return answer;
}
Prominence
Used as: Division One – Level Two:
| Value | 450 |
| Submission Rate | 98 / 196 (50.00%) |
| Success Rate | 63 / 98 (64.29%) |
| High Score | tourist for 416.62 points (8 mins 10 secs) |
| Average Score | 261.25 (for 63 correct submissions) |
The problem is a combination of two separate problems.
- For each mountain, find the next and previous mountain which is higher.
- Range Minimum Query.
For each mountain, let’s find the previous mountain which is higher. It’s possible with following pseudocode:
for i = 1 to n
while s is not empty and a[s.top()] <= a[i]:
s.pop()
if s is empty:
l[i] = 0 # not found
else:
l[i] = s.top()
s.push(i)
For RMQ problem, check this article.
int[] reversed(int[] seq) {
int[] answer = new int[seq.length];
for (int i=0; i<seq.length; ++i) answer[i] = seq[ seq.length-1-i ];
return answer;
}
int[] getBiggerLeft(int[] H) {
int N = H.length;
int[] answer = new int[N];
int[] idx = new int[N+1];
int[] hei = new int[N+1];
idx[0] = -1;
hei[0] = 1000000007;
int cnt = 1;
for (int n=0; n<N; ++n) {
while (hei[cnt-1] <= H[n]) --cnt;
answer[n] = idx[cnt-1];
hei[cnt] = H[n];
idx[cnt] = n;
++cnt;
}
return answer;
}
int[] getBiggerRight(int[] H) {
int N = H.length;
int[] HR = reversed(H);
int[] BL = getBiggerLeft(HR);
int[] RBL = reversed(BL);
for (int n=0; n<N; ++n) RBL[n] = (N-1) - RBL[n];
return RBL;
}
int L;
int[][] T;
int min_query(int lo, int hi, int r, int c, int tlo, int thi) {
if (thi <= lo || hi <= tlo) return 1000000007;
if (lo <= tlo && thi <= hi) return T[r][c];
return Math.min( min_query(lo,hi,r+1,2*c,tlo,(tlo+thi)/2), min_query(lo,hi,r+1,2*c+1,(tlo+thi)/2,thi) );
}
public long sumOfProminences(int N, int[] coef, int[] idx, int[] val) {
int[] H = new int[N];
for (long i=0; i<N; ++i) {
int parity = (int)(i % 2);
long a = coef[3*parity];
long b = coef[3*parity+1];
long c = coef[3*parity+2];
H[(int)i] = (int)((((a*i + b) % 1000000007L)*i + c) % 1000000007L);
}
for (int j=0; j<idx.length; ++j) H[ idx[j] ] = val[j];
L = 0;
while ((1 << L) < N) ++L;
T = new int[L+1][];
for (int l=0; l<=L; ++l) {
T[l] = new int[1<<l];
for (int i=0; i<(1<<l); ++i) T[l][i] = 1000000007;
}
for (int n=0; n<N; ++n) T[L][n] = H[n];
for (int l=L-1; l>=0; --l) for (int i=0; i<(1<<l); ++i) T[l][i] = Math.min( T[l+1][2*i], T[l+1][2*i+1] );
int[] BL = getBiggerLeft(H);
int[] BR = getBiggerRight(H);
long answer = 0;
int peaks = 0;
for (int n=0; n<N; ++n) if ((n == 0 || H[n] > H[n-1]) && (n+1 == N || H[n] > H[n+1])) {
++peaks;
int bl = BL[n], br = BR[n];
int bottom = 0;
if (bl >= 0) bottom = Math.max( bottom, min_query(bl+1,n,0,0,0,1<<L) );
if (br < N) bottom = Math.max( bottom, min_query(n+1,br,0,0,0,1<<L) );
answer += H[n] - bottom;
}
return answer;
}
RestrictedLeaves
Used as: Division One – Level Three:
| Value | 1000 |
| Submission Rate | 38 / 196 (19.39%) |
| Success Rate | 36 / 38 (94.74%) |
| High Score | tourist for 934.16 points (7 mins 39 secs) |
| Average Score | 708.68 (for 36 correct submissions) |
Let’s remind you about the same problem on tree (without new edges).
We used dp to solve the problem. dp[v][0] = number of independent sets in the subtree of vertex v if we don’t use v. In the same way, dp[v][1] = number of independent sets in the subtree of v if we can use v itself.
The problem is not so much different. What do we need in the subtree of vertex v?
- If the vertex v is chosen.
- If the leftmost leaf of the subtree is chosen.
- If the rightmost leaf of the subtree is chosen.
So, let’s use dp[v][state of v][state of leftmost leaf][state of rightmost leaf]. Updating dp values is straightforward.
int MOD = 1_000_000_007;
int N;
int[] parent;
int[][] children;
long[][][][] dp; // dp[vertex][x][y][z] == # of solutions for the subtree rooted at vertex given that the states of the vertex,
// its leftmost leaf and its rightmost leaf are (x,y,z)
void solve(int root) {
if (children[root].length == 0) {
for (int r=0; r<2; ++r) for (int ll=0; ll<2; ++ll) for (int rl=0; rl<2; ++rl) dp[root][r][ll][rl] = ((r == ll && ll == rl) ? 1 : 0);
return;
}
for (int child : children[root]) solve(child);
long[][][] oldc = new long[2][2][2];
long[][][] newc = new long[2][2][2];
int c0 = children[root][0];
for (int ll=0; ll<2; ++ll) for (int rl=0; rl<2; ++rl) {
oldc[1][ll][rl] = dp[c0][0][ll][rl];
oldc[0][ll][rl] = ( dp[c0][0][ll][rl] + dp[c0][1][ll][rl] ) % MOD;
}
for (int i=1; i<children[root].length; ++i) {
int ci = children[root][i];
for (int ll=0; ll<2; ++ll) for (int rl=0; rl<2; ++rl) {
newc[0][ll][rl] = newc[1][ll][rl] = 0;
for (int x=0; x<2; ++x) for (int y=0; y<2; ++y) if (x+y != 2) {
newc[1][ll][rl] += oldc[1][ll][x] * dp[ci][0][y][rl];
newc[1][ll][rl] %= MOD;
newc[0][ll][rl] += oldc[0][ll][x] * ( dp[ci][0][y][rl] + dp[ci][1][y][rl] );
newc[0][ll][rl] %= MOD;
}
}
for (int r=0; r<2; ++r) for (int ll=0; ll<2; ++ll) for (int rl=0; rl<2; ++rl) oldc[r][ll][rl] = newc[r][ll][rl];
}
for (int r=0; r<2; ++r) for (int ll=0; ll<2; ++ll) for (int rl=0; rl<2; ++rl) dp[root][r][ll][rl] = oldc[r][ll][rl];
// System.out.println("dp " + root + " = " + dp[root][0][0] + " " + dp[root][0][1] + " " + dp[root][1][0] + " " + dp[root][1][1] );
}
public int count(int[] _parent) {
parent = _parent;
N = parent.length;
int[] outdegree = new int[parent.length];
for (int i=1; i<parent.length; ++i) ++outdegree[ parent[i] ];
children = new int[N][];
for (int n=0; n<N; ++n) children[n] = new int[outdegree[n]];
for (int i=parent.length-1; i>=1; --i) children[ parent[i] ][ --outdegree[parent[i]] ] = i;
dp = new long[N][2][2][2];
solve(0);
long answer = 0;
for (int r=0; r<2; ++r) for (int ll=0; ll<2; ++ll) for (int rl=0; rl<2; ++rl) if (ll + rl != 2) answer += dp[0][r][ll][rl];
return (int)(answer % MOD);
}
Guest Blogger
