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 firsttimer 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 4th and 5th places respectively. The ProblemsRectangleGroupsUsed 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: 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. IntegerSequenceUsed 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_{0}, A_{1}, ..., M, B_{0}, A_{1}, ...}, A_{0} < A_{1} < M > B_{0} > B_{1}. We can easily prove that subsequence {A_{0}, A_{1}, ..., M} is the LIS ending on element M. Similarly, {M, B_{0}, A_{1}, ...} 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; }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_{1}, y_{1}, x_{2}, x_{2}}. The point is inside the rectangle if and only if (x_{1} < x_{p} < x_{2}) and (y_{1} < y_{p} < y_{2}). Similarly, the rectangle is Lets create two lists of integers  X and Y. To list X we will put all xcoordinates of rectangles (either left or right edges), and to list Y we will put all ycoordinates 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. UnitsMovingUsed 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_{0}, this means for every time T >= T_{0} 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_{0}. 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} = 0 and T_{1} = 1e20  left and right boundaries for the binary search. On each following step, we take T_{2} = (T_{0} + T_{1}) / 2, and try to assign destinations to units such a way that all units will reach their destinations faster that T_{2} 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_{2} seconds. In other words, having T_{2} we can build a bipartite graph with units at the left and destinations at the right. The ith unit will have edges only to the destinations reachable within T_{2} 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. 
