March 24, 2020 Single Round Match 772 Editorials

PlusCastle 

Used as: Division Two – Level One:

Value250
Submission Rate100 / 146 (68.49%)
Success Rate42 / 100 (42.00%)
High Scoregravito12345 for 238.62 points (6 mins 15 secs)
Average Score172.98 (for 42 correct submissions)

The first fact is spaces are not useful. Deleting a space doesn’t reduce the number of closed figures.

Now consider count is a complete square number, i. e. count = x * x. We create a full square with a side of length x. So the answer is (x – 1)^2. It also works for non-complete square counts.
Code by agw02010:

    def maximiseClosedFigures(self, k):
        ret = int((k ** 0.5 - 1) ** 2)
        return ret

PermutationAndMultiplication 

Used as: Division Two – Level Two:

Value500
Submission Rate70 / 146 (47.95%)
Success Rate25 / 70 (35.71%)
High ScoreBKM009 for 464.92 points (7 mins 55 secs)
Average Score299.49 (for 25 correct submissions)

We can remove additional trailing zeros from A it will not affect the answer. Now, A = 2^ones-1 and B = 2^(ones+zeros-1) + 2 ^ (ones – 1) – 1⇒ A * B = 2^(ones+ones+zeros-1) + 2^(ones+ones-1) – 2^ones – (2^(ones+zeros-1) + 2 ^ (ones – 1) – 1).

Adding (and subtracting) two numbers can be done in O(n).

Code by BKM009:

    public static int multiplyAndCount(int m, int n)
    {
        if (m == 1)
        {
            return 1;
        }
        if (m <= n)
        {
            return 2 * m;
        }
        if (m == 2 && n == 1)
        {
            return 4;
        }
        if (n == 1)
        {
            return m + 1;
        }
        return m;
    }

AntiprimeNumbers 

Used as: Division Two – Level Three:

Value1000
Submission Rate9 / 146 (6.16%)
Success Rate3 / 9 (33.33%)
High Scoremoririn2528 for 590.15 points (28 mins 11 secs)
Average Score545.22 (for 3 correct submissions)

We solve the problem for D = 8. We can create 3^N numbers with digits 4, 6, 8. Let’s involve digit “1”. “1” could be never placed after “1”, “4”, or “6”. Also, “1” could be never placed after two “8”s. We have 3^(n-1) options with placing 1 at the start of the string and fill the remaining with 4, 6, 8. Also, we have 3^(n-2) options to start with “81” and fill the remaining with 4, 6, 8.Code by Tomii9273:

    def countAntiPrimes(self, N, D):
        s = int(N)
        d = D
 
        mod = 10**9+7
        def pow(x, y):
            if y==0:
                return 1
            ans = 1
            while y > 0:
                if y % 2 == 1:
                    ans = (ans * x) % mod
                x = (x * x) % mod
                y //= 2
            return ans
 
        if d < 4:
            if s == 1:
                ans = 1
            else:
                ans = 0
        elif d < 6:
            ans = 2
        elif d < 8:
            if s == 1:
                ans = 3
            else:
                ans = (pow(2, s-1) * 3) % mod
        else:
            if s == 1:
                ans = 4
            elif s == 2:
                ans = 13
            else:
                ans = (4*pow(3, s-1) + pow(3, s-2)) % mod
        return ans

SmoothPermutations 

Used as: Division One – Level One:

Value250
Submission Rate91 / 126 (72.22%)
Success Rate64 / 91 (70.33%)
High Scoresquare1001 for 233.16 points (7 mins 44 secs)
Average Score146.01 (for 64 correct submissions)

Let f(n, k, x) be the number of permutations of numbers 1 to n such that the largest element among the first k elements is at most equal to x.

f(n, k, x) = (n – k) * (n – 1 – k) * (n – 2 – k) * … * (x + 1 – k) * x * (x – 1) * (x – 2) * … * 1.

But there are a lot of queries. We need to calculate it faster. It’s possible with a segment tree or a sparse table. Let sp(i, j) be i * (i + 1) * (i + 2) * … * (i + 2 ^ j – 1) and precompute this function. Now calculating of every L * (L + 1) * (L + 2) * … * R is possible using this values in O(log).

Total complexity is O(T * log(MX)).Code by square1001:

  int sz, mod;
  vector<int> seg;
  int query(int a, int b, int k, int l, int r) {
    if (a <= l && r <= b) return seg[k];
    if (r <= a || b <= l) return 1;
    int lc = query(a, b, k * 2, l, (l + r) >> 1);
    int rc = query(a, b, k * 2 + 1, (l + r) >> 1, r);
    return 1LL * lc * rc % mod;
  }
  int query(int a, int b) {
    if (a <= 0) return 0;
    return query(a, b, 1, 0, sz);
  }
  long long countPermutations(int T, int M, int MX, int seed, vector<int> prefN, vector<int> prefK, vector<int> prefX) {
    mod = M;
    vector<int> A(3 * T);
    A[0] = seed;
    for (int i = 1; i < 3 * T; ++i) {
      A[i] = (A[i - 1] * 1103515245LL + 12345) % 2147483648LL;
    }
    vector<int> N(T), K(T), X(T);
    int LEN = prefN.size();
    for (int i = 0; i < LEN; ++i) {
      N[i] = prefN[i];
      K[i] = prefK[i];
      X[i] = prefX[i];
    }
    for (int i = LEN; i < T; ++i) {
      N[i] = (A[i] % MX) + 1;
      K[i] = (A[T + i] % N[i]) + 1;
      X[i] = (A[2 * T + i] % N[i]) + 1;
    }
    sz = 1;
    while (sz <= MX) sz *= 2;
    seg.resize(sz * 2);
    for (int i = 0; i < sz; ++i) {
      seg[i + sz] = i;
    }
    for (int i = sz - 1; i >= 1; --i) {
      seg[i] = 1LL * seg[2 * i] * seg[2 * i + 1] % mod;
    }
    long long ans = 0;
    for (int i = 0; i < T; ++i) {
      int lc = query(X[i] - K[i] + 1, X[i] + 1);
      int rc = query(1, N[i] - K[i] + 1);
      int sub = 1LL * lc * rc % M;
      ans += sub;
    }
    return ans;
  }

MaxPoints 

Used as: Division One – Level Two:

Value500
Submission Rate25 / 126 (19.84%)
Success Rate23 / 25 (92.00%)
High Scoretourist for 432.96 points (11 mins 33 secs)
Average Score308.40 (for 23 correct submissions)

Let’s reform the validation formula. Let s be the total sum between every two points. Let overall(S) be the sum of all pairwise distances between any point in S and any other point (in S or not in S).

Now, inside(S) – outside(S) = overall(S) – s. Why? Let divide pair of points to three parts:

  • One from S, another from S: in overall(S), this distance counted twice. In s, it subtracted once.
  • One from S, another from outside of S: counted once in overall(S), subtracted once in s.
  • One from outside of S, another from outside of S: never counted in overall(S), once counted in s.

Let’s calculate sum[i], the sum of distances from i to every point. Sort points. sweep from left to right and for each point calculate its x difference to all other points. Same for y.

Now, sort points by their sum. Add them one by one while overall(S) – s <= k.

Code by tourist:

int MaxPoints::findMaxPoints(int N, vector <int> XG, vector <int> YG, long long K, int seedX, int seedY) {
  vector<long long> A(N);
  A[0] = seedX;
  for (int i = 1; i < N; i++) {
    A[i] = (A[i - 1] * 1103515245 + 12345) % 2147483648LL;
  }
  vector<int> X(N);
  for (int i = 0; i < (int) XG.size(); i++) {
    X[i] = XG[i];
  }
  for (int i = (int) XG.size(); i < N; i++) {
    X[i] = (A[i] % 2000001) - 1000000;
  }
  vector<long long> B(N);
  B[0] = seedY;
  for (int i = 1; i < N; i++) {
    B[i] = (B[i - 1] * 1103515245 + 12345) % 2147483648LL;
  }
  vector<int> Y(N);
  for (int i = 0; i < (int) YG.size(); i++) {
    Y[i] = YG[i];
  }
  for (int i = (int) YG.size(); i < N; i++) {
    Y[i] = (B[i] % 2000001) -  1000000;
  }
  vector<long long> sum(N);
  for (int rot = 0; rot < 2; rot++) {
    vector<pair<int, int>> xs(N);
    for (int i = 0; i < N; i++) {
      xs[i] = make_pair(rot == 0 ? X[i] : Y[i], i);
    }
    sort(xs.begin(), xs.end());
    long long s = 0;
    for (int i = 1; i < N; i++) {
      s += xs[i].first - xs[0].first;
    }
    for (int i = 0; i < N; i++) {
      sum[xs[i].second] += s;
      if (i < N - 1) {
        s += (xs[i + 1].first - xs[i].first) * 1LL * (i + 1 - (N - i - 1));
      }
    }
  }
  sort(sum.begin(), sum.end());
  long long cur = -accumulate(sum.begin(), sum.end(), 0LL) / 2;
  if (cur > K) {
    return -1;
  }
  int ans = 0;
  for (long long s : sum) {
    if (cur + s <= K) {
      cur += s;
      ++ans;
    }
  }
  return ans;
}

Guest Blogger


categories & Tags


Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds