Match Editorial

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

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];
}

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)

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.

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 {A₀, A₁, ..., M, B₀, A₁, ...}, A₀ < A₁ < M > B₀ > B₁. We can easily prove that subsequence {A₀, A₁, ..., M} is the LIS ending on element M. Similarly, {M, B₀, A₁, ...} is the longest decrementing subsequence (LDS) starting from element M. Therefore, we can solve the problem in the following 3 steps:

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;
}

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 (x_p, y_p) and a rectangle {x₁, y₁, x₂, x₂}. The point is inside the rectangle if and only if (x₁ < x_p < x₂) and (y₁ < y_p < y₂). Similarly, the rectangle is

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 (x_p, y_p) such that

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.

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 T₀, this means for every time T >= T₀ 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 < T₀. This property should clearly convince us to use binary search. Now we'll see how to use it.

First of all, we set times T₀ = 0 and T₁ = 1e20 -- left and right boundaries for the binary search. On each following step, we take T₂ = (T₀ + T₁) / 2, and try to assign destinations to units such a way that all units will reach their destinations faster that T₂ seconds. During each step, a destination can be assigned to a unit if and only if the unit can reach the destination faster than T₂ seconds. In other words, having T₂ 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 T₂ 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.