Optimal Constructives
10/20
Warm-Up
You are given an array of integers. You want to put them into pairs such that each integer is in exactly one pair. Your score is defined as the sum of over all pairs. Whatβs the maximum score you can achieve?
Example:
Optimal Constructives
Construct ___ such that ___ is maximized/minimized.
Adjacent Delete
Solution
(for now, assume is even) Ideally, we always pair the largest elements with the smallest elements. The cool thing is it turns out that this is always possible!
We can use a simple inductive proof. When , it is obviously always possible. Then, when , note that there must always be a βlargeβ element adjacent to a βsmallβ element. Therefore, we can simply delete this pair, and recurse to .
odd case is left as an exercise to the reader/viewer.
Manhattan Pairs
Solution
The idea is similar to that of Adjacent Delete. Letβs shift our coordinate axes such that exactly half the points are above the -axis, and exactly half the points are to the right of the -axis. Then, our goal is to pair points in the first quadrant with points in the third quadrant, and points in the second quadrant with points in the fourth quadrant.
Again, it turns out that this is always possible!
Bounds
The next two problems involve finding good upper/lower bounds on the answer that will decrease our search space significantly.
Mr Kitayutaβs Technology
 |  |
Solution
First observe that we can solve each weakly connected component separately.
Now, notice that in a component of nodes, we can always satisfy all relations by using only edges, simply by connecting the entire component in a cycle. We also definitely canβt use less than edges, otherwise the component wonβt be connected anymore. Therefore, the question becomes: can we satisfy all required relations in this component using only edges (sound familiar?)
Maple and Tree Beauty
Solution
Let be the minimum depth of any node. Then, it turns out the answer is always at least (how?) Therefore, we just need to know whether we can achieve an answer of exactly or not, which can be done via a subset sum DP.