15295 Spring 2022 #11 No Theme -- Problem Discussion

April 6, 2022

This is where we collectively describe algorithms for these problems.  To see the problem statements and scoreboard, go to this page and select this contest.

A. An Easy Graph Problem?

Notice that 2N > 21 + 22 … 2N-1. So whoever gets 2N will have the larger set, regardless of how the other items are assigned. This must be person A.

To maximise person B, notice that 2N-1 > 21 + 22 … 2N-2 (using the same idea as before). So it is best to give person B the value 2N-1 since you must maximise person B now. Now start a DFS from N-1 to find all items you can reach from N-1 without passing through N. Assign all these items B, and the remainder must be A.

• Soum

B. Invested Money

C. Joining Pairs

Consider only the pairs of points such that both points are on the border around the grid. Out of these points, imagine tracing the points along the border. One of two cases must be true: either the order in which you encounter the points has no pairs (A1, B1) and (A2, B2) such that you first encounter A1 then B1 then A2 then B2, or that there must be such pairs. If there are such pairs, there is no way to draw these pairs without intersections, so answer no. Otherwise, the construction is always possible, so answer yes.

• Soum

This can be computed in O(n) time, using sorting and a stack.  

—DS

D. Hamilton - The Musical

Let there be M positions you still need to fill (M = ceil(N/2)). Then construct a flow diagram with 2M+2 nodes. There will be one node for each of the odds from 1..N and one node for each of the places these odds can go in (each odd index). Then add the following edges:

• One edge from the source to each node, with cost 0 and capacity 1
• One edge from each index to the sink, with cost 0 and capacity 1
• One edge from every node to every index that the node can go in, with cost equal to the distance between the two adjacent nodes to the index and the specified node (or one, if there is only one adjacent node).

Then the maximum flow in this graph is M since it is possible to pair every index and every node. Calculate the minimum cost of this maximum flow to find the answer.

• Soum

E. Most Ordered Way

We first find any order that works, and then see how we can improve it to the lexicographically smallest order. To find any order that works, sort the assignments with their deadlines and do them in that order (that’s the most natural strategy to do homeworks huh?). If this is not possible then return *. Otherwise it is always possible, so we find the best order. Suppose the current order is p[0], …, p[n-1], and the inverse of this order is p-1.

To improve this, for each index, we see if it is possible to move some assignments with small index to the front, while preserving the validity of the order. The idea is, we determine the n positions of the final result in order. We see what is the smallest index that we can assign to res[i], then we remove that index from the current list, and add it to the result. Then, we do the same for the remaining positions of the result and list. The problem is, if we add something to the final result, the starting time for some assignments in the remaining list changes, and even making them violations. The standard way to do this is to maintain the time from the end of each assignment to the deadline using a segtree that supports adding to a range and querying for the range minimum. The order of elements in the segtree is in the sorted order p[0], …, p[n-1]. The elements in this segtree must always be nonnegative, otherwise there is a violation.

For res[i], we should iterate over all the remaining possible assignments j in increasing order. We see if we can assign j to the res[i], that is to move j to the front of the current order, with the previous selected assignments removed. To check this, it suffices to check the minimum value in the range [0, p-1[j]) of the segtree. If the minimum time is at least t[j], then we can move j to the front, which results in decreasing the values in the range [0, p-1[j]) by t[j]. This preserves the validity of the order, since the values will remain nonnegative. We also need to “delete” this element from the segtree. We can do this by setting its value to infinity. It is guaranteed that we can find a solution (since p is already a solution).

Since we iterate through i and j, and the query time for segtree is O(log n), the total time complexity is O(n2 log n). My solution takes 1.5s, and it passed after Danny changed the time limit to 2s.

– Yan

F. Because, Art!

I’m going to illustrate the algorithm by way of an example.  Let’s first solve the case where the goal is the compute the k-matching of maximum value. (To solve the reverse problem where we want the k matching of minimum value, you can simply negate F, solve the maximization problem, then negate it.)

So let’s take F and C and sort them so that they go from largest to smallest (left to right).  The result could look like this.

In this example F reaches its first negative value first, then three positions later C reaches its first negative value.  So going from left to right, first they’re both positive, then F goes negative, then C goes negative, then they’re both negative.  The middle region (shown highlighted in green) is where F is negative and C is positive.  We’ll treat that region differently (later on).  The two outer regions are the ones which have matching values that are positive.  And the optimal solution is always going to begin with those.

If you have a pair if F values (a,b) with a>b and a pair of C values (c,d) with c>d, then the maximum pairing for k=1 is obtained with a*c.  Then for k=2 the best value is a*c + b*d.  So to obtain the beginning of our matching we just pair the items up in left to right order. and output them (as k increases) in decreasing order of their product.  This is shown in the first four parts of the figure below.  We can obtain this simply by sorting.

Before we begin to discuss the green region, we reverse the positive part (in C) as shown in the first frame of the diagram.  Then when we continue into the green region, the values are going to be negative, so our goal is to output them from smallest (in absolute value) first.  The optimal way to do this is shown in the final three panels of the diagram.  Note that the pattern in which these are paired has is fixed, given that the values are sorted as shown.

If we think of the green region of F and C to be coefficients of two polynomials, then the successive values, as k increases, are just the coefficient in the product polynomial of successive powers of x.  Therefore these can be efficiently computed using the FFT.

For more on the FFT see these lecture notes, and this video.

—Danny

G. Ancient Towers