Wednesday, January 21st, 2009 Match summarySRM 433 had an unbelievable challenge phase  pmnox outchallenged Petr and won the match by a mere 5 points. TopCoder titans ACRush and misof were a hundred points behind. In Division 2, fatrat1695 dominated the field winning by more than 100 points, with veteran Uranium235 and NewForce coming second and third, respectively. The Division 2  1000 problem appeared to be quite hard, with only 12 correct submissions. The ProblemsRoyalTreasurerUsed as: Division Two  Level One:
This was a pretty classical problem. If you want to minimize the sum of A_{i} * B_{i}, you should multiply the smallest A_{i} by the largest B_{i}, the secondsmallest A_{i} by the secondlargest B_{i}, and so on. In other words, if B_{i} > B_{j}, then A_{i} must not be greater than A_{j} (you can prove this by contradiction). The java code follows: public int minimalArrangement(int[] A, int[] B) { Arrays.sort(A); Arrays.sort(B); int res = 0; for (int i=0; i < A.length; i++) res += A[i] * B[B.length  i  1]; return res; }MagicWords Used as: Division Two  Level Two: Used as: Division One  Level One:
This problem was harder than a usual problem of this slot. Nevertheless, there are at least 3 solutions which are guaranteed to pass any test under the given constraints.
Used as: Division Two  Level Three:
This problem splits into 2 independent parts: parsing the input into some data structure (should be easy for most coders trying to solve the problems of this level) and computing the price of LOVE. We'll concentrate on the latter. Computing the price of any potion should be simple  either the potion could be bought on the market, or there is a recipe which results in that potion. Unfortunately, you need to compute the prices of recipes in a specific order  for example, if you need WATER to get COFFEE, then you can not compute the price of COFFEE until you know the price of WATER. To make things worse, the dependencies may be cyclic, so you can not topologically sort the potions to get the order of computations. Fortunately, the constraints on this problem are quite low, so we can try using the following algorithm:
In general, the algorithm is not that hard. The only problem is "if needed" part. How do we know whether we've achieved the optimal price? The answer to this question is very simple: if (in point 2) we tried all recipes and didn't update the price for any of the resulting components, then we've reached the optimum. See the fastest solution for an example of implementation (note that osan didn't bother with checking for update on each loop). SettingTentsUsed as: Division One  Level Two:
This problem is quite similar to IsoscelesTriangle, and the approaches are quite similar. The solution splits into 2 parts: a) checking all possible shapes of rhombs and b) computing the number of ways such a rhomb can be placed inside the designated area (if your implementation is not careful enough, then you have also part c)  make sure you dodn't count any rhomb more than once). Subproblem b) is quite simple  you compute the dimensions Bx*By of the bounding box of the rhomb, and the number of ways the rhomb can be placed inside the N*M area is either (N  Bx + 1)*(M  By + 1), or zero (if Bx > N or By > M). Lets find a way to check all possible rhomb shapes. To do that, lets start from the bottom vertex A of the rhomb (if a rhomb has 2 bottom vertices at the same level, choose the leftmost of them). Now you need to check all possible directions and lenghts of the 2 edges coming out of the vertex A. Checking all of them in a bruteforce way will be too slow, since there are 100*100 = 10000 possibilities for each edge. To optimize the search, we do the following trick: check all possibilities for the left of two edges (10000 possibilities), and then start 'rotating' it clockwise to check all possibilities for the second edge (they must be of the same length). 'Rotation' can be implemented in the following way. Let the first edge be (x, y). We start incrementing x, checking the length of the new edge and adjusting it when needed (increasing y if the edge is too short and decreasing if the edge is too long). If the length of the edge is equal to the length of the first edge, then these edges correspond to a rhomb. We check the number of ways this rhomb can be placed inside the area (see subproblem b) above), and return the total for all possible directions of the first edge. The time complexity of this solution is O(N^3)  checking all possible directions on the first edge takes O(N^2) and checking all rotations of the edge can be done in linear time. BarbarianInvasionUsed as: Division One  Level Three:
This problem is solved by maximum flow algotithm, so unexperienced coders may want to read the tutorial before going further. Lets start by solving easier versions of the problem. For example, what if all detachments would be of the same size? This is a classical minimal cut problem. Indeed  think of all barbarian lands outside the country as of source, the capital will be the sink, and all cells become the intermediate vertices of the graph. Two vertices in that graph will be connected only if the enemy can move directly between the corresponding cells on the map. Since the flow can be limited in the cells only(the barbarians can be stopped in the cells only, not between cells), we need to eliminate vertex capacities as it shown in the tutorial (see Figure 7). Lets call the edges added on this step (edges between vertices of the same color on Figure 7 in the tutorial) auxiliary edges. The capacities should be set to 1 for all auxiliary edges, and to infinity (replaced by a very big integer number) for all other edges. Now the answer of this simplified problem will be the size of the minimal cut in the graph. Lets now try another simplification. Forget about "the minimal number of detachments" requirement, and try to find the minimal total size of all detachments needed to protect the capital (now detachments may be of different sizes). This version differs only slightly from the previous one  the capacity of each auxiliary edge will be changed to the size of the detachment needed to block the corresponding cell, and the capacities of all nonauxiliary edges remain infinite. And the last step  we are to change the problem solved in the previous paragraph and minimize the total number of detachments used prior to minimizing the total size of all detachments. So, using X detachments of total size S1 should be more expensive than using (X  1) detachment of total size S2, even if S2 > S1. In other words, using an extra detachment should be very expensive, and we can simulate this by adding a very big number T to the sizes of ALL detachments. If the mincut in the corresponding graph will be equal to M, this will mean we needed [T / M] detachments of total size (T % M). 
