Notifications

Good job! You’re all caught up

Join challenges and check your notification settings if you don’t receive notifications. We’re actively adding new notifications. Read our blog post for more info

Notifications
TOSCA Editor - Web Application Wireframe Challenge (1)
Dismiss notification
Earlier Dismiss All
You have no more notifications

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:

Value300
Submission Rate174 / 201 (86.57%)
Success Rate146 / 174 (83.91%)
High Scoreracsosabe for 296.35 points (3 mins 9 secs)
Average Score215.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:

Value500
Submission Rate88 / 201 (43.78%)
Success Rate59 / 88 (67.05%)
High Scoreracsosabe for 404.15 points (14 mins 34 secs)
Average Score279.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:

Value1000
Submission Rate19 / 201 (9.45%)
Success Rate14 / 19 (73.68%)
High Scoreheno239 for 848.12 points (12 mins 29 secs)
Average Score725.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 &amp;&amp; 2*(s+G) > total) answer += oldpp[s];
        return answer;
    }

Prominence

Used as: Division One – Level Two:

Value450
Submission Rate98 / 196 (50.00%)
Success Rate63 / 98 (64.29%)
High Scoretourist for 416.62 points (8 mins 10 secs)
Average Score261.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 &amp;&amp; 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]) &amp;&amp; (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:

Value1000
Submission Rate38 / 196 (19.39%)
Success Rate36 / 38 (94.74%)
High Scoretourist for 934.16 points (7 mins 39 secs)
Average Score708.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 &amp;&amp; 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


categories & Tags


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

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds