Problem of August '21

And here is the problem of August 2021.

Simulation problems are a category in competitive programming. We have very easy to very hard problems in this category. The CircularParking from SRM 811 is one of them. Let’s see why only 28% of attempted participants were able to solve the problem.

We have an interesting problem for Div I competitors at this time. A problem with a low success rate, MergeToSort. The problem is creative and interesting. Also, it has many solutions; at least I discovered three different solutions.

Let’s tackle the CircularParking first:

The brief problem statement:

Given a circular parking, i-th car starts from ((A * i * i + B * i + C) % n)-th parking slot and goes one by one till find an empty parking slot and park there. If a car reaches n - 1 and it is full, the next parking slot will be 0.

Find the sum of parking slots that cars will skip in the process.

It’s very easy to solve this problem using two for loops but it results in O(n^2). We need to somehow improve this solution. In fact, we want to find the next free parking slot faster.

The key is to use a data structure that supports these actions inefficient time:

• Inserting an element.

• Removing an element.

• Given k, find the smallest key that is greater or equal to k.

set in C++, TreeSet in Java, and bisect in Python support these operations.

So we keep a set of free parking slots all the time.

At the first insert all of the numbers in the range [0, n - 1] to the set. Then for each car find the next parking slot using lower_bound (or ceilingEntry in Java). If no free parking slot is found, it shows that the car needs to start from 0. Again use lower_bound to find the first free slot. After the parking slot is found, erase it from the set because this slot is not free anymore.

Java code by Ferrumit:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public long park(int N, int A, int B, int C) {
    TreeMap < Integer, Integer > map = new TreeMap < > ();
    for (int i = 0; i < N; i++)
      map.put(i, 1);

    boolean visited[] = new boolean[N];
    long result = 0;
    long NN = N;
    long AA = A;
    long BB = B;
    long CC = C;

    for (long i = 0; i < N; i++) {
      int pos = (int)((AA * i * i + BB * i + CC) % NN);
      if (visited[pos]) {
        Integer ceiling = map.ceilingKey(pos);
        if (ceiling != null) {
          result += (ceiling - pos);
          visited[ceiling] = true;
          map.remove(ceiling);
        } else {
          ceiling = map.ceilingKey(0);
          result += (NN + ceiling - pos);
          visited[ceiling] = true;
          map.remove(ceiling);
        }
      } else {
        visited[pos] = true;
        map.remove(pos);
      }
    }

Now for MergeToSort:

The problem statement is simple: Given an array, make it sorted. In each operation, you can choose two adjacent elements and replace them with their sum.

A Div. 1 competitor selects the dp path in the first look, as we’re going to do so. Ok what do we need in our dp? For sure dp[i] = answer for the range [0, i). I. e. minimum possible number of operations we need to make the range [0, i) sorted.

When using dp, instead of thinking about what else I need to keep in my dp, I straightly jump to the updating part. Then I discover the other parameters that needed to be added to dp.

So, how to update dp[i] from previous dp’s? Consider we want to update dp[i] from dp[j]. It’s simple to deduce that by update, I mean we’re going to first make the range [0, j) sorted, then we’ll spend i - j - 1 operations to replace elements in the range [j, i) with their sum.

When is it possible to update dp[i] from dp[j]? The only condition is, the sum of the range [j, i) must be greater or equal to the last element of the range [0, j) after operations.

So it seems that we need another value to keep, best[i]. Consider the set s = all of the possible sequences of operations with length dp[i] making the range [0, i) sorted. Let f(seq) be the resulting array of applying seq on the range [0, i) (just the [0, i) part not all of the array). best[i] = the minimum last element of f(seq) for each seq in s. Simply, best[i] is the minimum possible last element in the range [0, i) after operations.

Where sum(j, i) stands for the sum of elements in the range [j, i). Now we have an n^2 solution. Let cum[i] be the cumulative sum of the array, i. e. cum[i] = sum of the range [0, i). Let’s rewrite our dp:

Now the O(n log n) solution is easy using segment tree or sparse table. Put dp[i] - i in (best[i] + cum[i])’s index of segment tree and then

One can optimize this using stack trick to achive O(n) like the code below by uwi:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int minSteps(int n, int[] Aprefix, int seed, int blo, int bhi) {
  int L = Aprefix.length;
  int[] a = new int[n];
  for (int i = 0; i < L; i++) {
    a[i] = Aprefix[i];
  }

  long state = seed;
  for (int i = L; i < n; i++) {
    state = (state * 1103515245 L + 12345) & (1 L << 31) - 1;
    long b = blo + ((state / 1000) % (bhi - blo + 1));
    state = (state * 1103515245 L + 12345) & (1 L << 31) - 1;
    long x = 1 L << b - 1;
    a[i] = (int)(x + ((state / 10) % x));
  }

  long[] cum = new long[n + 1];
  for (int i = 0; i < n; i++) {
    cum[i + 1] = cum[i] + a[i];
  }

  int[] dp = new int[n + 1];
  long[] best = new long[n + 1];
  Arrays.fill(best, Long.MAX_VALUE / 2);
  best[0] = 0;
  PriorityQueue < long[] > yet = new PriorityQueue < > ((x, y) - > {
    return Long.compare(x[0], y[0]);
  });
  long maxj1 = -1;
  long maxb = Long.MAX_VALUE / 2;

  yet.add(new long[] {
    best[0] + cum[0], dp[0] + 1, -cum[0]
  });

  for (int i = 1; i <= n; i++) {
    while (!yet.isEmpty() && cum[i] >= yet.peek()[0]) {
      long[] h = yet.poll();
      if (h[1] > maxj1 || h[1] == maxj1 && h[2] < maxb) {
        maxj1 = h[1];
        maxb = h[2];
      }
    }
    dp[i] = (int) maxj1;
    best[i] = maxb + cum[i];
    yet.add(new long[] {
      best[i] + cum[i], dp[i] + 1, -cum[i]
    });
  }
  return n - dp[n];
}