March 24, 2020 Single Round Match 769 Editorials

BallsOnAMeadow 

Used as: Division Two – Level One:

Value250
Submission Rate147 / 165 (89.09%)
Success Rate128 / 147 (87.07%)
High Scoreresh.root for 248.38 points (2 mins 18 secs)
Average Score213.16 (for 128 correct submissions)

The answer is the number of times “(” appears in the meadow + the number of times “)” appears in the meadow – the number of times “()” appears in the meadow.Code by Patrik:

    def count(self, m):
        s = 0
        for i in range(len(m)):
            c = m[i]
            if c == '(':
                s += 1
            elif c == ')' and m[i-1] != '(':
                s +=1
        return s

ReallyMagicSquare 

Used as: Division Two – Level Two:

Value500
Submission Rate56 / 165 (33.94%)
Success Rate45 / 56 (80.36%)
High Scoreqixiao for 452.75 points (9 mins 22 secs)
Average Score275.64 (for 45 correct submissions)

Let’s name the matrix, a. Let’s construct the matrix row by row. The first row is given. How to find the second row?

a[1][1] (0-based) is given. We know a[0][0] + a[1][1] + a[2][2] + … + a[n – 1][n – 1] = a[0][1] + a[1][0] + a[2][2] + … + a[n – 1][n – 1] ⇒ a[0][0] + a[1][1] = a[0][1] + a[1][0]

To generalize the fact, for every r1, r2, c1, c2 ⇒ a[r1][c1] + a[r2][c2] = a[r1][c2] + a[r2][c1].

So a[1][0] = a[0][0] + a[1][1] – a[0][1].

To generalize, for a[1][i] (i > 1): a[1][i] = a[0][i] + a[1][1] – a[0][1].

To generalize for other rows, when i ≠ j, a[i][j]  = a[0][j] + a[i][i] – a[0][i].Code by cntswj (modified):

def reconstruct(self, topRow, mainDiagonal):
  n = len(topRow)
  square = [[None] * n for _ in range(n)]
  square[0] = topRow
  for i in range(1, n):
    square[i][i] = mainDiagonal[i]
    for j in range(n):
      if i != j:
        square[i][j] = square[0][j] + square[i][i] - square[0][i]
  ret = []
  for row in square:
    ret += row
  
  return ret

PrimePruning 

Used as: Division Two – Level Three:

Value1000
Submission Rate9 / 165 (5.45%)
Success Rate0 / 9 (0.00%)
High Scorenull for null points (NONE)
Average ScoreNo correct submissions

Used as: Division One – Level One:

Value250
Submission Rate95 / 116 (81.90%)
Success Rate67 / 95 (70.53%)
High Scoretourist for 236.94 points (6 mins 44 secs)
Average Score174.68 (for 67 correct submissions)

Greedy. We try to make the first character maximum possible. Then try to make the second character maximum possible, …

Let H = N – E.

What is the best option for the first character? Look for the maximum character in the first N – H + 1 characters (choose the first, in case of tie). Similarly for the next characters. The time complexity is O(NH). Although we can improve it to O(N log N), it’s not needed.

The fact comes to mind is, after some N, we always have H “z” characters, so we can choose them all and this is the best possible answer.

Code by tourist:

string maximize(int N, int E) {
  int keep = N - E;
  string s = "";
  vector<int> p;
  int cc = 0;
  for (int i = 2; ; i++) {
    bool prime = true;
    for (int j = 2; j * j <= i; j++) {
      if (i % j == 0) {
        prime = false;
        break;
      }
    }
    if (!prime) {
      continue;
    }
    s += (char) ('a' + i % 26);
    cc += (s.back() == 'z');
    if (cc == keep || (int) s.size() == N) {
      break;
    }
  }
  N = (int) s.size();
  int start = 0;
  string ret = "";
  for (int i = 0; i < keep; i++) {
    int rm = N - start;
    char mx = ' ';
    int pos = -1;
    for (int j = start; j <= N - keep + i; j++) {
      if (s[j] > mx) {
        mx = s[j];
        pos = j;
      }
    }
    ret += s[pos];
    start = pos + 1;
  }
  return ret;  
}

SchedulingWoes 

Used as: Division One – Level Two:

Value500
Submission Rate60 / 116 (51.72%)
Success Rate42 / 60 (70.00%)
High Scoreneal_wu for 469.47 points (7 mins 20 secs)
Average Score345.22 (for 42 correct submissions)

Sort exams by their date. Let’s keep the best answer while iterating exams from the first one to the last one.

Consider till a specific exam like (D, T) we succeed in passing several exams. Now there are two cases to consider:

  • We can add (D, T) to the answer too. It can be checked if we keep the number of mornings we have studied for current passed exams.
  • We can not add (D, T) to the answer. Let’s try to substitute it with another exam in the current answer. The substitution is affordable if there is a passed exam in the current answer which needs more time to pass. So we can remove the unprofitable exam from the answer and add (D, T) to the answer instead. This can be done if we keep exams in a heap (C++ std::set or std::priority_queue).

Total time complexity is O(n log n).Code (neal_wu):

    int study(int N, int seed, vector<int> Dprefix, int maxD, vector<int> Tprefix, int factor) {
        vector<long long> random(2 * N);
        random[0] = seed;
 
        for (int i = 1; i < 2 * N; i++)
            random[i] = (random[i - 1] * 1103515245 + 12345) % (1LL << 31);
 
        vector<long long> D(N), T(N);
 
        for (int i = 0; i < (int) Dprefix.size(); i++) {
            D[i] = Dprefix[i];
            T[i] = Tprefix[i];
        }
 
        for (int i = (int) Dprefix.size(); i < N; i++) {
            D[i] = 1 + random[2 * i] % maxD;
            long long maxT = max(1LL, D[i] / factor);
            T[i] = 1 + random[2 * i + 1] % maxT;
        }
 
        vector<pair<long long, long long>> exams;
 
        for (int i = 0; i < N; i++)
            exams.emplace_back(D[i], T[i]);
 
        sort(exams.begin(), exams.end());
        priority_queue<long long> pq;
        int pass_count = 0;
        long long current_day = 0, free_days = 0;
 
        for (pair<long long, long long> &exam : exams) {
            long long D = exam.first;
            long long T = exam.second;
 
            free_days += D - current_day;
            current_day = D;
 
            if (free_days < T && !pq.empty() && pq.top() > T) {
                free_days += pq.top();
                pass_count--;
                pq.pop();
            }
 
            if (free_days >= T) {
                free_days -= T;
                pass_count++;
                pq.push(T);
            }
        }
 
        return pass_count;
    }

ThreeColorTrees 

Used as: Division One – Level Three:

Value1000
Submission Rate30 / 116 (25.86%)
Success Rate1 / 30 (3.33%)
High ScorePetr for 361.20 points (43 mins 22 secs)
Average Score361.20 (for 1 correct submission)

Let’s start with an easier task. The tree is given, just count the number of ways to color it. Here is it:

static double count(int[] p) {
    if (p[0] != -1) throw new RuntimeException();
    for (int i = 1; i < p.length; ++i) if (p[i] >= i) throw new RuntimeException();
    double[][] res = new double[p.length][4];
    for (int i = 0; i < p.length; ++i) {
        res[i][0] = 2 * DELTA;
        res[i][1] = 1 * DELTA;
    }
    for (int i = p.length - 1; i > 0; --i) {
        double[] nr = new double[4];
        for (int a = 0; a < 4; ++a) {
            for (int b = 0; b < 4; ++b) {
                if ((a & 1) != 0) {
                    if (b != 0) continue;
                }
                if ((a & 2) != 0) {
                    if ((b & 1) != 0) continue;
                }
                nr[(a | (b << 1)) & 3] += res[p[i]][a] * res[i][b] * INVDELTA;
            }
        }
        res[p[i]] = nr;
    }
    double s = 0;
    for (double x : res[0]) s += x;
    return s;
}

The function uses dp on a tree to count the number of ways. To avoid inf values, it uses DELTA = 1e-130 and INVDELTA = 1e130.

Now, we need to check some patterns. Path works for small n’s. Binary tree is not good. Generating some good random trees with small n leads to trees like this:

Trees like ternary tree, but added a vertex on each edge. We can generate them by this code:

        for (int i = 1; i < n; ++i)
            res[i] = i % 2 == 0 ? i - 1 : i / 6;

Check it against any possible n. It doesn’t work for 12, 24, 36. The first idea comes to mind is to change it to:

        for (int i = 1; i < n; ++i)
            res[i] = i % 2 != 0 ? i - 1 : i / 6;

And it works!

Here is the code (by Arpa):

public int[] construct(int n) {
    int[] res = new int[n];
    if(n % 12 == 0)
        for (int i = 1; i < n; ++i)
            res[i] = i % 2 != 0 ? i - 1 : i / 6;
    else
        for (int i = 1; i < n; ++i)
            res[i] = i % 2 == 0 ? i - 1 : i / 6;
    return Arrays.copyOfRange(res, 1, res.length);
}

Also, this code by Petr uses local search and it works:

import java.util.Arrays;
import java.util.Random;
 
public class ThreeColorTrees {
    static double DELTA = 1e-130;
    static double INVDELTA = 1e130;
 
    public int[] construct(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; ++i) res[i] = i - 1;
        double need = (1 + 1e-9) * DELTA;
        for (int i = 0; i < N; ++i) need *= 2.62;
        double sofar = count(res);
        Random random = new Random(754315351351L);
        while (sofar < need) {
            int cur = 2 + random.nextInt(N - 2);
            int dest = random.nextInt(cur);
            if (dest != res[cur]) {
                int saved = res[cur];
                res[cur] = dest;
                double got = count(res);
                if (got > sofar) {
                    sofar = got;
                } else {
                    res[cur] = saved;
                }
            }
        }
        return Arrays.copyOfRange(res, 1, res.length);
    }
 
    static double count(int[] p) {
        if (p[0] != -1) throw new RuntimeException();
        for (int i = 1; i < p.length; ++i) if (p[i] >= i) throw new RuntimeException();
        double[][] res = new double[p.length][4];
        for (int i = 0; i < p.length; ++i) {
            res[i][0] = 2 * DELTA;
            res[i][1] = 1 * DELTA;
        }
        for (int i = p.length - 1; i > 0; --i) {
            double[] nr = new double[4];
            for (int a = 0; a < 4; ++a) {
                for (int b = 0; b < 4; ++b) {
                    if ((a & 1) != 0) {
                        if (b != 0) continue;
                    }
                    if ((a & 2) != 0) {
                        if ((b & 1) != 0) continue;
                    }
                    nr[(a | (b << 1)) & 3] += res[p[i]][a] * res[i][b] * INVDELTA;
                }
            }
            res[p[i]] = nr;
        }
        double s = 0;
        for (double x : res[0]) s += x;
        return s;
    }
 
}

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