Thursday, June 7, 2007 Match summaryDivision 2 was presented with a balanced problem set with a trivial easy, straightforward medium and standard dynamic programming as a hard. A bunch of coders solved all three problems correctly. Division 2 was won by crazyb0y, followed by ziliang and brahle.Division 1 was another story, with a relatively easy 250 problem and straightforward but still errorprone medium that employed elementary physics. The hard problem was a tough nut for TopCoders that morning, with a total of zero successful submissions. The top three places were determined mostly according to the number of successful challenges among those who had submitted easy and medium problems. So, JongMan took the first place with 6 challenges, while liympanda and ilyaraz took second and third place respectively. Notably third, fourth and fifth places were taken by high school students  ilyaraz, reiten and ahyangyi respectively. The ProblemsEllipseCoverageUsed as: Division Two  Level One: Given that the constraints on the size of ellipse in the input are small, we can easily traverse all integral points in some region containing ellipses and check if they lie inside. The simplest choice was a big rectangle, for example with coordinates (500, 500)  (500, 500). If we choose this rectangle on plane it will be big enough to cover every possible ellipse given as input  we can easily traverse each integral point in rectangle, checking if it lies strictly in given ellipse or not. Checking whether a point with the given coordinates lies in ellipse or not is described in problem description, and it is a trivial procedure. However, it can be performed in two ways: slow and fast. Most participants used slow checking, e.g. calculating distance using doubles and checking against given d. A much faster and accurate solution with integer arithmetic only exists: we can easily avoid doubles, ignoring sqrt operation  we can use sum of squared distances from the integral point to foci to check if the point lie inside. You can see cluster2006's solution as a reference. #define i64 long long i64 len(int x1, int x2, int y1 ,int y2) { i64 res = (x1x2)*(x1x2)+(y1y2)*(y1y2); return res; } int calculateCoverage(int x1,int y1,int x2,int y2,int dd){ int res=0; for(int i=500;i<500;i++) for(int j=500;j<500;j++) { i64 a = len(x1, i, y1, j); i64 b = len(x2, i, y2, j); i64 d = dd; if (4*a*b<(d*dab)*(d*dab)) res++; } return res; }Glossary Used as: Division Two  Level Two: Used as: Division One  Level One: This problem required a clean implementation of the described simple and straightforward logic. However, a significant amount of coders failed to provide a working solution. Most failed submissions were in times larger than the fastest (and prettiest) code by bmerry. So never forget about the KISS principle while competing in TopCoder SRM's. First we need to sort items in a caseinsensitive way, and then fill two columns: the first column with items whose first letter is from 'A' to 'M', and the second column with items from 'N' to 'Z'. We can now fill those two columns separately, and after completion we will merge them into one column of strings  resulting glossary. To fill one column with words we just push them one after another, and if the first letter changes we also push a "letterheader" to column. Don't forget to provide a letterheader for the first word in the column. To easily merge two columns with different number of elements, we simply add empty strings (strings of 19 spaces) to the smaller column. When the heights are equal, merging is a trivial thing. You can see bmerry's solution as a reference. PlatformJumper Used as: Division Two  Level Three: Used as: Division One  Level Two: Obviously, each journey in the problem is directed downward. That implies each journey has finite length, and each platform can be visited at most once. So, we can employ dynamic programming to solve this problem. Let's introduce function F[v]  the maximal number of collected coins, among all journeys ending at v platform. If we can calculate that set of platforms S[v], such that platform v can be reached by one jump from every platform from S[v], then F[v] can be easily computed as a maximum: F[v] = coins[v] + max{y from S[v]} F[y] Where coins[v] is number of coins at platform v.The trickiest part of the problem was to verify if we can jump from one platform to another. This required knowledge of high school physics. Let's consider two platforms with coordinates (x1,y1) and (x2,y2), y1>y2. Jumper need to cover abs(x1x2) distance in Ox direction and (y1y2) in Oy direction. Suppose, that we move with highest possible speed in Ox direction  Vmax. Then we need time Tneed = abs(x1x2)/Vmax to complete jump. However, when flying we are moving downward by force of gravity. We can calculate length of path in Oy direction in time Tneed: Dy = g*Tneed^2/2. If Dy is greater than (y1y2) obviously we can't perform such a jump. Most failed submissions incorrectly checked whether we can jump from one platform to another. zhuzeyuan's solution clearly follows these ideas: int maxCoins(vector <string> ss, int v, int g) { int i,j,k; n = ss.size(); for (i=0; i<n; i++) sscanf(ss[i].c_str(),"%d %d %d",&cc[i].x, &cc[i].y, &cc[i].c); sort(cc, cc+n); // sorting in order of increasing height int opt[60], ans = 0; for (i=n1; i>=0; i) { opt[i] = cc[i].c; for (j=i+1; j<n; j++) if ( opt[j]+cc[i].c>opt[i] && (long long) (cc[i].xcc[j].x)* (cc[i].xcc[j].x)*g <= (long long)(cc[j].ycc[i].y)*2*v*v ) opt[i] = opt[j]+cc[i].c; if (opt[i]>ans) ans = opt[i]; } return ans; }FurnitureRobbery Used as: Division One  Level Three: Fifty solutions were submitted to this problem at coding phase, but no coder survived after system test. It's surely a rare thing at TopCoder. However, a number of coders were just a few lines of code behind the right solution. For example the cool solution by bmerry passes system test successfully, if we add one check at the beginning  whether the famous sofa is already at the first line. Obviously, this notsohard problem required imitation of furniture movement. To avoid visiting the same state a few times we will create a hash function, assigning an integer to some furniture position. Let us first encode some furniture position into an array of integers. Because we have at most 30 field positions, let's assign a 2^{x}, x=0..301 to each of them. Then, each piece of furniture can be encoded as an integer, by applying binary OR operation to integers located in cells occupied by piece of furniture. So, each floor plan state can be encoded as a array of integers, where each integer corresponds to some piece of furniture. The hash code of the whole floor plan can be calculated as a polynomial of array of furniture codes. Important: we will assume that first code is always code of famous sofa, and other codes  at most 14 integers  are sorted. This assumption greatly reduces number of possible states. This small illustration shows its significance: AAA..BB AAA..CC AAA..CC ....CC. ....BB. ....DD. DD..... DD..... BB.....All these positions will be considered as equal, according to the hash code calculation technique described above. Detailed description of good hash function usage and its calculation requires large amount of space and can be found in many books on algorithms. So, hashing details will be avoided (you still can consult selfexplanatory solution of bmerry with excellent implementation of this problem). Now we have an effective memorization structure, and we can safely apply breadthfirst search to find position where part of famous sofa is located at top row. Use of breadthfirst search allows us to return the result when first such state will be found. Its realization is pretty obvious, and most coders should be familiar coding such algorithms. ` 
