JOIN
 Match Editorial
SRM 278
Monday, December 19, 2005

Match summary

The recent Maximum Flow Tutorial was followed by a bipartite matching Division 1 - Level 3 problem. The other two were much easier, so 6 coders were able to hit the 1500+ points mark. In a tough race, 2 challenges helped krijgertje to win the SRM and appear in the top 3 for the 4th SRM in a row. tmyklebu, Petr and happyyellow followed all within 1 challenge, with misof being another 100 points behind.

The race was even closer in Division 2. Newcomer kia was only 4 points ahead of fellow first-timer b285714. LiuYuChen was another candidate for the Division title, but his unsuccessful challenge wasted two successful ones. LiuYuChen landed at the third place, only 6 points from the winner. Another newcomer RoBa and fifka were at distant 4-th and 5-th places respectively.

# The Problems

RectangleGroups
Used as: Division Two - Level One:
 Value 300 Submission Rate 277 / 326 (84.97%) Success Rate 244 / 277 (88.09%) High Score answer-42 for 295.12 points (3 mins 39 secs) Average Score 219.15 (for 244 correct submissions)

Given several rectangles split into groups, find the group with the biggest total area. The most difficult part here is to calculate the value for each of the groups. One must use map structure in a general case, but much simpler approach works. Group name is limited to one letter in the problem, therefore an array of 26 elements can store values for all possible group names. Java code follows:

```String maximalIndexed(String[] rectangles) {
int[] memo = new int[26];
for (int i = 0; i < rectangles.length; i++) {
String[] data = rectangles[i].split(" ");
memo[data[0].charAt(0) - 'A'] += Integer.parseInt(data[1]) * Integer.parseInt(data[2]);
}
int bestValue = 0;
for (int i = 1; i < 26; i++) if (memo[i] > memo[bestValue]) bestValue = i;
return (char)('A' + bestValue) + " " + memo[bestValue];
}

```

BestTriangulation
Used as: Division Two - Level Two:
 Value 500 Submission Rate 152 / 325 (46.77%) Success Rate 134 / 152 (88.16%) High Score Zexee for 479.37 points (5 mins 56 secs) Average Score 336.63 (for 134 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 282 / 296 (95.27%) Success Rate 274 / 282 (97.16%) High Score krijgertje for 247.88 points (2 mins 38 secs) Average Score 210.37 (for 274 correct submissions)

Given a polygon, we reduce it to a triangle cutting vertices one by one in any order. You are to return the maximal possible area of the final triangle.

The first thing to realize here is that the polygon can be reduced to any triangle built on the polygon's vertices. Once we see this, the problem becomes an easy brute force excercise. We iterate over all possible triples of vertices, storing the maximal area for all triangles. The area of a triangle can be calculated using Heron's formula or the cross product of vectors.

IntegerSequence
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 88 / 326 (26.99%) Success Rate 41 / 88 (46.59%) High Score kia for 962.30 points (5 mins 40 secs) Average Score 657.92 (for 41 correct submissions)

Given a sequence of numbers, we are to throw out the minimal number of elements to make the sequence satisfy the condition from the problem statement. Throwing out the minimal number of elements is equivalent to leaving the maximal number of elements, which clearly reminds us of the longest increasing subsequence (LIS) problem. LIS problem can be solved using Dynamic Programming (see Dynamic Programming Tutorial, Books from SRM 175 as an example of a LIS problem).

In the problem we are asked to find the longest subsequence of the form {A0, A1, ..., M, B0, A1, ...}, A0 < A1 < M > B0 > B1. We can easily prove that subsequence {A0, A1, ..., M} is the LIS ending on element M. Similarly, {M, B0, A1, ...} is the longest decrementing subsequence (LDS) starting from element M. Therefore, we can solve the problem in the following 3 steps:

• For each element, find the LIS ending on this element and save it to lis[i].
• For each element, find the LDS starting from this element and save it to lds[i].
• Find the maximum of (lds[i] + lis[i]) for all i.
• The only other thing to mention is that element M will be counted twice (both in increasing and decreasing sequences), therefore we must subtract 1 from the final sequence length.

Java code follows:

```public int maxSubsequence(int[] numbers) {
int[] lis = new int[numbers.length];
int[] lds = new int[numbers.length];
for (int i = 0; i < numbers.length; i++)
for (int j = 0; j < i; j++)
if (numbers[j] < numbers[i])
lis[i] = Math.max(lis[j] + 1, lis[i]);
for (int i = numbers.length - 1; i >= 0; i --)
for (int j = numbers.length - 1; j > i; j--)
if (numbers[j] < numbers[i])
lds[i] = Math.max(lds[j] + 1, lds[i]);
int best = 0;
for (int i = 0; i < numbers.length; i++) best = Math.max(best, lds[i] + lis[i]);
return numbers.length - best - 1;
}

```

OneMorePoint
Used as: Division One - Level Two:
 Value 450 Submission Rate 182 / 297 (61.28%) Success Rate 109 / 182 (59.89%) High Score happyyellow for 446.00 points (2 mins 41 secs) Average Score 262.21 (for 109 correct submissions)

This problem can be split in two parts. First, we need to check mutual location of a point (xp, yp) and a rectangle {x1, y1, x2, x2}. The point is inside the rectangle if and only if (x1 < xp < x2) and (y1 < yp < y2). Similarly, the rectangle is

• above the point if (x1 < xp < x2) and (y1 > yp).
• below the point if (x1 < xp < x2) and (y2 < yp).
• to the left of the point if (x2 < xp) and (y1 < yp < y2).
• to the right of the point if (x1 > xp) and (y1 < yp < y2).
• Having that implemented, we can proceed with the second part.

Lets create two lists of integers - X and Y. To list X we will put all x-coordinates of rectangles (either left or right edges), and to list Y we will put all y-coordinates of rectangles (either top or bottom). After adding all numbers to the lists, sort them in increasing order and remove duplicates. Now choose any indices i and j. All points (xp, yp) such that

• X[i] < xp < X[i + 1]
• Y[j] < yp < Y[j + 1]
• simultaneously either satisfy or do not satisfy the conditions from the problem statement. Therefore, checking any one point from this area is enough to check all points in the area. This property is the key to the problem. Populate lists X and Y, sort them and check all points of the form ((X[i] + X[i + 1]) / 2, (Y[j] + Y[j + 1]) / 2). If one of these points satisfies all conditions, return true. If neither of the points satisfies the conditions, return false.

An implementation detail is that you can use arrays to check whether the point has a rectangle on each side. A fine solution by misof uses bitmasks.

UnitsMoving
Used as: Division One - Level Three:
 Value 1000 Submission Rate 100 / 297 (33.67%) Success Rate 67 / 100 (67.00%) High Score happyyellow for 957.67 points (6 mins 1 secs) Average Score 716.60 (for 67 correct submissions)

This problem, being geometrical at the first glance, is a mixture of classical Binary search and Maximum Bipartite Matching algorithms.

If the optimal answer for all units is T0, this means for every time T >= T0 we can somehow assign destinations to units and all units will reach correspondent destinations earlier than T. On the other hand, such an assignment does not exist for any T < T0. This property should clearly convince us to use binary search. Now we'll see how to use it.

First of all, we set times T0 = 0 and T1 = 1e20 -- left and right boundaries for the binary search. On each following step, we take T2 = (T0 + T1) / 2, and try to assign destinations to units such a way that all units will reach their destinations faster that T2 seconds. During each step, a destination can be assigned to a unit if and only if the unit can reach the destination faster than T2 seconds. In other words, having T2 we can build a bipartite graph with units at the left and destinations at the right. The i-th unit will have edges only to the destinations reachable within T2 seconds. We solve the maximum bipartite matching problem for this graph. Continue with smaller times if all units can be matched, with the bigger otherwise.

See Section 2 of Maximum Flow Tutorial for a detailed description of Maximum Bipartite Matching problem.

By Olexiy
TopCoder Member