April 15, 2019 Single Round Match 755 Editorials

SRM 755 was held on April 15, 2019. Thanks to misof for setting the problems and writing the editorials.

OneHandScheduling

We need to determine whether the time intervals given in the input are disjoint. If they are, Misof can do everything, if they aren’t, he cannot.

One possible solution is to look at each pair of intervals and check whether they overlap. Depending on the implementation, this may be tricky, as there are multiple different ways in which two intervals may overlap. Probably the easiest way is the following: suppose we have two closed intervals [a,b] and [c,d]. The earliest time at which both of them started is max(a,c), the latest time at which neither has ended is min(b,d). Clearly, there is an overlap if and only if max(a,c) <= min(b,d).

Another, less error-prone solution is to simply look at all integer times between 0 and 10^6, inclusive. If each of them belongs to at most one of the given intervals, they obviously have to be disjoint, and if you find a time that belongs to two or more intervals, you know that the intervals are not disjoint.

public String checkSchedule(int[] tStart, int[] tEnd) {
  for (int t = 0; t <= 1 _000_000; ++t) {
    int inside = 0;
    for (int i = 0; i < tStart.length; ++i)
      if (tStart[i] <= t && t <= tEnd[i]) ++inside;
    }
    if (inside > 1) return "impossible";
  }
  return "possible";
}

OneHandSort

There are many different ways to sort the given sequence. The simplest one is probably the one where you consider each slot on the shelf from the left to the right. If the slot contains the correct element, you do nothing. Otherwise, you put the current element from that slot to slot N, then you move the correct element to the current (now empty) slot, and then you return the arbitrary element from slot N to the empty slot you just created.

def sortShelf(target):
	N = len(target)
	target.append(-1) # add the empty slot
	answer = []
	for n in range(N):
		if n == target[n]: continue
		correct = target.index(n)
		answer.append( n )
		answer.append( correct )
		answer.append( N )
		target[correct] = target[n]
		target[n] = n
	return answer

OneHandSort2

In this problem we have the same setting as in OneHandSort, but there are two notable differences. First, we need to actually generate a huge input, and second, we need to solve it in an optimal number of moves.

In order to generate the input, we need an efficient way to answer the query “what is the smallest unused number that is greater than or equal to x?”. In order to do this, we can use an ordered set data structure, such as “set” in C++ or “TreeSet” in Java. We will store all unused numbers in this data structure, and remove them as we assign them to the input array. Whenever we get a query, we simply use the corresponding method of the data structure — e.g., “lower_bound” in C++ or “ceiling” in Java.

In order to solve the input optimally, note that what we have is a permutation of numbers 0 through N-1. For each permutation there is a unique way to split that permutation into cycles. (E.g., if element in slot 3 wants to go to slot 7, element in slot 7 wants to go to slot 42, and element in slot 42 wants to go to slot 3, this is one cycle.)

If we have a cycle of length 1, we don’t have to do anything: this is an element that is in its correct slot.

For any other cycle, note that when we move one of its elements for the first time, we cannot put it into the correct slot, as it is currently occupied. Hence, for a cycle of length x we need at least x+1 moves.

On the other hand, it’s easy to solve a cycle of length x in exactly x+1 moves: just move any one of its elements into the empty slot N, then do exactly x-1 moves in which you move the element that belongs to the currently empty slot into that slot (thereby freeing a slot for another element) and finally return the element from slot N into its correct slot that is now empty.

In the above example of a cycle, we would move “element 7” (meaning “the element that belongs into the slot 7”) from slot 3 to slot N, then element 3 from slot 42 to slot 3, then element 42 from slot 7 to slot 42, and finally element 7 from slot N to slot 7.

Hence, once we have the permutation, we split it into cycles and then compute the answer by looking at their lengths.

If we use the algorithm described above, the permutation can be generated in O(n log n) time. We can easily decompose a permutation into cycles in O(n) time, so the total time complexity remains O(n log n).

public int minMoves(int N, int[] targetPrefix, int a, int b) {
    TreeSet<Integer> unused = new TreeSet<Integer>();
    for (int n=0; n<N; ++n) unused.add(n);
    int[] target = new int[N];
    for (int n=0; n<targetPrefix.length; ++n) {
        target[n] = targetPrefix[n];
        unused.remove( target[n] );
    }
    for (int n=targetPrefix.length; n<N; ++n) {
        long nextll = target[n-1];
        nextll = (nextll * a + b) % N;
        int next = (int)nextll;
        Integer tmp = unused.ceiling(next);
        if (tmp == null) tmp = unused.ceiling(0);
        target[n] = tmp;
        unused.remove( target[n] );
    }
    boolean[] seen = new boolean[N];
    for (int n=0; n<N; ++n) seen[n] = false;
    int answer = 0;
    for (int n=0; n<N; ++n) if (!seen[n]) {
        int cycleLength = 1;
        seen[n] = true;
        int where = n;
        while (true) {
            where = target[where];
            if (seen[where]) break;
            seen[where] = true;
            ++cycleLength;
        }
        if (cycleLength > 1) answer += cycleLength + 1;
    }
    return answer;
}

OneHandRoadPainting

This problem is solvable greedily — but note that not all greedy solutions work.

A correct solution can be made using the following observations:

• There is always an optimal solution that consists of multiple trips such that in each trip Misof begins in his home, takes the paint, walks somewhere, turns around, and on his way home he paints some segments. (It doesn’t make sense to walk across the same section twice in the same direction. Whatever you do during the second pass you could do during the first pass. It doesn’t matter whether you paint on your way there or on your way back.)
• Consider the point farthest away from the home that needs to be painted. This point has to be painted in some trip, which means that it has to be visited in some trip. Now comes the greedy observation: in that trip, we can paint the paintPerBrush meters of the road that need painting and are farthest away from the home.

In order to prove the greedy observation, we can do a switching argument. Suppose you have an optimal solution S. If it has a trip that matches our greedy observation, we are done. Otherwise, consider the trip that visits the farthest point in S. While this trip uses fewer paint than paintPerBrush, take some painting away from some other trip and assign it to this trip. Clearly this doesn’t change the value of the solution, so we still have an optimal solution, but now the trip that visits the farthest point uses all available paint. Now, if it still doesn’t match our greedy observation, there has to be a segment (or a collection of them) closer to home that we do paint during this trip, and a segment (or a collection of them) farther from home that we don’t. Find any trip that paints anything in the second part and swap it for something in the first part. This can never worsen our solution, because our special trip remains of the same length, and on the other trip we swapped a segment for some other segment closer to home. Thus, we can change any optimal solution into one where our greedy observation works.

All that remains is to implement the greedy strategy in an efficient way. The only catch is that we cannot simulate one trip at a time: in the worst case, there can be up to 2*10^9 trips.

Thus, we do the following. Look at the last segment that needs to be painted. If it requires more than one trip using the greedy strategy, do all the trips at once, except for the last one. More precisely, we will do (segmentLength div paintPerBrush) trips. The total distances traveled during these trips form an arithmetic series and we can sum them up easily using a formula. This leaves us with the case where the length of the last segment is strictly smaller than paintPerBrush. We handle it by simulating one trip. In this trip we consider the segments from the back to the front. As long as we have enough paint to paint the current segment, we paint it and forget about it. Eventually, we will either run out of segments (in which case we are done) or we will run out of paint (in which case we’ll use the last remaining paint on our brush to paint the tail of the currently active segment).

This gives us a solution that runs in O(number of segments).

public long fastest(int[] dStart, int[] dEnd, int paintPerBrush) {
    long answer = 0;
    int active = dStart.length - 1;
    while (active >= 0) {
        long fullRuns = (dEnd[active] - dStart[active]) / paintPerBrush;
        if (fullRuns > 0) {
            answer += (2L*dEnd[active] - (fullRuns-1)*paintPerBrush) * fullRuns;
            dEnd[active] -= fullRuns * paintPerBrush;
        }
        if (dStart[active] == dEnd[active]) { --active; continue; }
        answer += 2L*dEnd[active];
        long paintRemaining = paintPerBrush;
        while (true) {
            long paintNeeded = dEnd[active] - dStart[active];
            if (paintNeeded <= paintRemaining) {
                paintRemaining -= paintNeeded;
                --active;
                if (active == -1) break;
            } else {
                dEnd[active] -= paintRemaining;
                break;
            }
        }
        if (active == -1) break;
    }
    return answer;
}

DejaVu

The first thing we do is that we go through the movie and build a data structure that maps each scene to the indices in the movie at which it occurs.

Consider an array A as long as the movie. Set all its elements to 0. Then, for each scene, set the element that corresponds to its second occurrence (if it exists) to +1, and its third occurrence (if it exists) to -1. The key observation is that the number of deja vus in the first X scenes of the movie is the sum of the first X elements of this sequence.

If we want to start watching at the beginning and we are looking for the optimal moment when to stop watching, we want to find the largest among all the prefix sums of the array A. We could answer this easily in linear time, but instead of doing that we will use a data structure. The reason why we do so will become apparent in a moment.

In particular, the data structure we’ll use will be a simple interval tree (a.k.a. range tree or tournament tree) built on top of the array A. Each inner node of this tree represents some contiguous segment of A. In each inner node we will store two values: the sum of that segment, and the largest of all prefix sums for that segment only.

These values are easy to propagate along the tree. For any inner node, its sum is the sum of the sums of its children, and its largest prefix sum is either the largest prefix sum of the left child, or the sum of the left child plus the largest prefix sum of the right child.

In order to find the best end for the movie, we simply look into the root of the tree and report the maximum prefix sum found there.

Why did we choose this data structure? Well, duh, because it’s easy to update. Now that we know the optimal end, consider what happens if we shift the beginning of the movie one scene to the right. That is, the scene M[0] stopped being in the movie. What do we have to change in the array A? It turns out that we only need to update three cells: the ones corresponding to the second, third, and fourth occurrence of that same scene in the movie. Now they become the first, second, and third occurrence, and as such their contribution to the number of deja vus changes from +1, -1, 0 to 0, +1, -1. Thus, we can make these three updates (or fewer, if the scene doesn’t have that many occurrences) and after each of them we propagate the changes up the interval tree.

In this way, we can implement the operation “discard the first scene and recompute the best end” in O(log n) time, making the full solution run in O(n log n).

int[][] sum;
int[][] max_psum;
void update(int level, int index) {
    sum[level][index] = sum[level+1][2*index] + sum[level+1][2*index+1];
    max_psum[level][index] = Math.max(
        max_psum[level+1][2*index],
        sum[level+1][2*index] + max_psum[level+1][2*index+1]
    );
}
void iset(int level, int index, int value) {
    sum[level][index] = value;
    max_psum[level][index] = value;
    while (level > 0) { --level; index /= 2; update(level,index); }
}
public int mostDejaVus(int N, int seed, int R) {
    // omitted: generate the array M as described in the statement
    int depth = 18;
    sum = new int[depth+1][];
    for (int l=0; l<=depth; ++l) sum[l] = new int[1<<l];
    max_psum = new int[depth+1][];
    for (int l=0; l<=depth; ++l) max_psum[l] = new int[1<<l];
    HashMap<Integer, ArrayList<Integer> > occurrences
        = new HashMap<Integer, ArrayList<Integer> >();
    for (int n=0; n<N; ++n) {
        if (!occurrences.containsKey( M[n] )) {
            occurrences.put( M[n], new ArrayList<Integer>() );
        }
        occurrences.get( M[n] ).add(n);
    }
    HashMap<Integer, Integer> offsets = new HashMap<Integer, Integer>();
    for (int scene : occurrences.keySet()) offsets.put( scene, 0 );
    for (int n=0; n<(1<<depth); ++n) iset(depth,n,0);
    for (int scene : occurrences.keySet()) {
        if (occurrences.get(scene).size() >= 2) {
            iset(depth,occurrences.get(scene).get(1),+1);
        }
        if (occurrences.get(scene).size() >= 3) {
            iset(depth,occurrences.get(scene).get(2),-1);
        }
    }
    int answer = 0;
    for (int start=0; start<N; ++start) {
        if (max_psum[0][0] > answer) answer = max_psum[0][0];
        int scene = M[start];
        int off = offsets.get(scene);
        if (occurrences.get(scene).size() >= 2+off) {
            iset(depth,occurrences.get(scene).get(1+off),0);
        }
        if (occurrences.get(scene).size() >= 3+off) {
            iset(depth,occurrences.get(scene).get(2+off),+1);
        }
        if (occurrences.get(scene).size() >= 4+off) {
            iset(depth,occurrences.get(scene).get(3+off),-1);
        }
        offsets.put(scene,off+1);
    }
    return answer;
}