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

**a.poorakhavan**

Guest Blogger