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