 # 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:

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


#### MemoryGame

Used as: Division Two – Level Two:

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:

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


#### Prominence

Used as: Division One – Level Two:

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:
else:
l[i] = s.top()
s.push(i)



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

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 = -1;
hei = 1000000007;
int cnt = 1;
for (int n=0; n<N; ++n) {
while (hei[cnt-1] <= H[n]) --cnt;
hei[cnt] = H[n];
idx[cnt] = n;
++cnt;
}
}

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



#### RestrictedLeaves

Used as: Division One – Level Three:

Let’s remind you about the same problem on tree (without new edges).

We used dp to solve the problem. dp[v] = number of independent sets in the subtree of vertex v if we don’t use v. In the same way, dp[v] = 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;
long[][][] newc = new long;

int c0 = children[root];
for (int ll=0; ll<2; ++ll) for (int rl=0; rl<2; ++rl) {
oldc[ll][rl] = dp[c0][ll][rl];
oldc[ll][rl] = ( dp[c0][ll][rl] + dp[c0][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[ll][rl] = newc[ll][rl] = 0;
for (int x=0; x<2; ++x) for (int y=0; y<2; ++y) if (x+y != 2) {
newc[ll][rl] += oldc[ll][x] * dp[ci][y][rl];
newc[ll][rl] %= MOD;
newc[ll][rl] += oldc[ll][x] * ( dp[ci][y][rl] + dp[ci][y][rl] );
newc[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] + " " + dp[root] + " " + dp[root] + " " + dp[root] );
}

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];
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[r][ll][rl];
return (int)(answer % MOD);
}



a.poorakhavan

Guest Blogger

categories & Tags

UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close