SRM 278

Match Summary

Round Overview
Discuss this match

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.

RectangleGroups

Used as: Division Two - Level One:

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:

1
2
3
4
5
6
7
8
9
10
11
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:

Used as: Division One - Level One:

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:

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:

• 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 ld[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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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:

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

above the point if (x₁ < x_p < x₂) and (y₁ > y_p).
below the point if (x₁ < x_p < x₂) and (y₂ < y_p).
to the left of the point if (x₂ < x_p) and (y₁ < y_p < y₂).
to the right of the point if (x₁ > x_p) and (y₁ < y_p < y₂).
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 (x_p, y_p) such that

X[i] < x_p < X[i + 1]
Y[j] < y_p < 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:

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.