Problem 189A — Cut Ribbon

The problem is to maximize x+y+z subject to ax+by+cz=n. Constraints are low, so simply iterate over two variables (say x and y) and find the third variable (if any) from the second equation. Find the maximum over all feasible solutions.

Other approaches: Use dynamic programming with each state being the remainder of ribbon. Select the next piece to be a, b or c.

Problem 189B — Counting Rhombi

Observe that lots of rhombi have the same shape, but are in different locations.

What uniquely determines the shape of a rhombus? Its width and its height.

Is it possible to build a rhombus with every width and every height such that the vertices of the rhombus are in integer points? No, it is possible only if the width and the height are both even.

How many places we can put a rhombus of width w0 and height h0 in a rectangle of width w and height h? (w * w0 + 1)(h * h0 + 1)

So, iterator over all even widths and heights and for each of them add the number of possible locations to the final result.

Problem 187A — Permutations

It is easy to see that if we replace each number in the first permutation with position of that number in the second permutation, the problem reduces to sorting the first permutation.

Each time we take a number from the end of array, we can postpone its insertion until we know the most suitable position for insertion. Note that it is not good to insert a number and take it again, as we could make a better decision first time we took the number.

So, as long as the remainder of the array is not in increasing order, we should take more numbers from the end. But as soon as you have an increasing subsequence, you can insert the numbers you have taken to make the array sorted.

Therefore to solve the problem, we find the largest i such the numbers from 1 to i are in increasing order. The answer would be n-i.

Problem 187B — AlgoRace

First we solve the problem when the number of allowed car changes is zero (_k=0_). Let W(i,j,l) be the length of shortest path from i to j with car l. We use Floyd-Warshal on graph of each car to find this value. Then answer for the case that we can use only one car for each pair of cities i and j is:

ans(0,i,j) = min W(i,j,l) for (_1≤l≤m_)

This part has time complexity O(m*n^3).

For larger values of maximum number of changes (_k_), we use the following equation:

ans(k,i,j) = min (ans(k-1,i,l)+ans(0,l,j)) for (_1≤l≤k_)

which can be computed in O(k*n^3) using dynamic programming.

But how large can be k in worst case? We know that shortest paths are simple paths (i.e. they have no repeated vertices). Because otherwise we could eliminate the path we go between two appearances of one vertex and have a smaller result. This and the fact that we change the car at most once in each vertex, guarantees in any optimal solution we will not need more that n car changes. Thus the order of the solution would be O(m*n^3+n^4).

Problem 187C — Weak Memory

There were many different correct approaches to this problem during the contest. But I will explain author’s solution.

First we can use binary search over the value of q. Now for a fixed q we want to check s-t connectivity.

Let K be the set of all intersections with volunteers union s and t. One can use BFS from each k∈K, one by one. Then build a graph G’ with vertices K. For each two vertices k1,k2∈K add an edge between them, if their shortest distance is less than or equal to q. Finally use any path finding algorithm to check the connectivity. Unfortunately this solution has time (and space) complexity of O(|K|*m) which is not good enough.

We can optimize the above solution by initiating BFS from all k∈K at once. In other words during the initialization step in BFS algorithm, we push all these vertices in the queue with distance 0. Each element in the queue also maintains its source (i.e. the source it is originating from). In BFS each time we have have a vertex u with source su and we want to set the minimum distance to a vertex v that is already set from a different path with source sv, we connect su and sv in G’ if d(u)+d(v)+1<= q, where d(x) denotes length of the shortest path from a vertex in K to x. As we are only dealing with connectivity, this approach is correct. (Proof of correctness is left as an exercise)

BFS takes O(m) time and we add at most O(m) edges to G’, so the overall complexity is O(m) for a fixed q. As we used binary search to find the smallest q, we can solve the problem in O(m*logn).

Problem 187D — BRT Contract

We define ti as follows: assume a bus starts moving from i-th intersection exactly at the time when the light changes to green. The time it takes for the bus to get the final station is ti. We call the times when a green interval begins t0 (so every g+r seconds t0 occurs once)

If a bus gets to i-th intersection during the red phase, it should wait and then start moving at t0. So considering the fact that all lights are synchronized (and length of segments are fixed) if we have ti for i-th intersection, we can compute the time for the bus to get final station.

Clearly tn is the length of the last segments. For computing ti we should find the smallest j such that if a bus starts at t0 from i-th intersection, it gets to j-th intersection during the red phase. So we have:

ti=tj+d(i,j)+w

where d(i,j) is the distance between i-th and j-th intersections and w is the time that the bus should wait behind the red light at j-th intersection. The later value can be computed easily.

The only problem that remains is to find j for i-th intersection. So we start iterating over i for (n-1)-th intersection backwards and we compute ti for all intersections. Assume p=g+r and ta=d(i,j)%p. Now if the bus starts from i-th intersection at time t0 and we have ta>=g, in this case we are in red phase at j-th intersection. Actually ta should be in interval [_g, g+r_).

Here we can use segment trees. That is for all intersections from i+1 to n, we store some values in the tree that helps us find the smallest j. But we should note the value of ta depends on d(i,j) which changes as i changes. Thus we cannot use ta in the tree. Instead, we define si the be the distance of i-th intersection to the destination. So we have d(i,j)=si-sj and we use the value of sj with storing –sj%p in the segment tree as the key and the value would be j itself. In other words for each intersection we store the key-value pair (-sj%p, j) in the tree. According to what we said so far, to be in the red phase at j-th intersection we should have:

ta=(d(i,j)%p)=((si-sj)%p)∈[g,g+r) => -sj%p ∈ [(g-si)%p, (g+r-si)%p)

As we stored –sj%p in the tree, we can retrieve the smallest j in the above interval with a query in the segment tree.

This way we can compute ti for all intersections. Answering to each query in the problem can be solve in exactly the same way. So the overall complexity would be O((n+q)logn).

Problem 187E — Heaven Tour

Step 1. Solve the problem if the starting man is the leftmost man and the finishing man is the rightmost man.

Obviously every segment (the distance between two consecutive men) should be covered at least once. We also argue that at least l (the number of left tickets) segments should be covered at least three times.

Proof: Each time you use a left ticket to go to man i with 1<i<n-1, the segment between i-th and (_i+1_)-th men is covered at least three times:

1. Once for you should go after i be in a position to come back.
2. Once for you use a left ticked to come back to i
3. And once again you should go after i, because you want to finish at man number n

Note that in the first and the last segments are always covered once, no matter what we do. But except for these two segments, every other segment can be chosen to be among the segments that are covered three times, and every combination that we choose l segments is feasible. (Proof it as practice) So we choose the smallest l segments and the problem can be solved with a simple sort in O(n*logn).

Step 2. Solve the problem if the starting man is the leftmost man, but the finishing man can be anywhere.

To solve this problem we first fix the finishing man. With reasoning similar to that of step 1, we conclude that at least l segments should be covered with at least two times if they are after the finishing man or three times if they are before him. But obviously every segment after the finishing man is covered at least two times. So it is always good to waste as many left tickets as possible after the finishing man to prevent them from breaching the left side of finishing man and becoming multiple three.

So the algorithm would be: iterate over i, the number of finishing man, and maintain the l-(n-i) smallest segments to the right of finishing man as you progress. This can be implemented in O(n*logn).

Step 3. Solve the problem if the starting man is fixed, but the finishing man can be anywhere.

Assume that the starting man is not the first man or the last man, otherwise we could use algorithm of step 2 to solve the problem. Without loss of generality assume that you finish your tour to the right side of finishing man. Therefore every segment to the left of starting man is covered at least two times and actually it is always possible to arrange visits such that every segment to right is covered exactly two times. So just like what we said in step 2, it is good to waste as many left tickets as possible in this area.

So the algorithm would be, choose to finish left or right first, then greedily waste as many bad moves (by bad moves I mean the moves that if breach to the other side will be more costly) as possible there and follow the algorithm in step 2 to solve the whole problem.

There are some special cases such as when the tour cannot be finished at all, that we left to readers find a way how to handle them.