Single Round Match 780 Editorials
a.poorakhavan · SRM 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);
}