|
Match Editorial |
Thursday, June 7, 2007
Match summary
Division 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 error-prone 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 Problems
EllipseCoverage
Used 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.
Value 250 Submission Rate 483 / 774 (62.40%) Success Rate 393 / 483 (81.37%) High Score CBETO3AP for 245.81 points (3 mins 43 secs) Average Score 186.58 (for 393 correct submissions)
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 = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
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*d-a-b)*(d*d-a-b))
res++;
}
return res;
}
Glossary
Used as: Division Two - Level Two:
Used as: Division One - Level One:
Value 500 Submission Rate 253 / 774 (32.69%) Success Rate 156 / 253 (61.66%) High Score Msching for 479.51 points (5 mins 55 secs) Average Score 257.39 (for 156 correct submissions)
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.
Value 250 Submission Rate 573 / 616 (93.02%) Success Rate 486 / 573 (84.82%) High Score bmerry for 236.09 points (6 mins 58 secs) Average Score 160.45 (for 486 correct submissions)
First we need to sort items in a case-insensitive 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 "letter-header" to column. Don't forget to provide a letter-header 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:
Value 1000 Submission Rate 100 / 774 (12.92%) Success Rate 27 / 100 (27.00%) High Score flaresky for 871.23 points (11 mins 16 secs) Average Score 664.35 (for 27 correct submissions)
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.
Value 500 Submission Rate 483 / 616 (78.41%) Success Rate 292 / 483 (60.46%) High Score ACRush for 485.04 points (5 mins 1 secs) Average Score 357.77 (for 292 correct submissions)
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(x1-x2) distance in Ox direction and (y1-y2) in Oy direction. Suppose, that we move with highest possible speed in Ox direction - Vmax. Then we need time Tneed = abs(x1-x2)/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 (y1-y2) 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=n-1; 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].x-cc[j].x)* (cc[i].x-cc[j].x)*g <=
(long long)(cc[j].y-cc[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.
Value 1000 Submission Rate 50 / 616 (8.12%) Success Rate 0 / 50 (0.00%) High Score null for null points (NONE) Average Score No correct submissions
Obviously, this not-so-hard 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 2x, x=0..30-1 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 self-explanatory solution of bmerry with excellent implementation of this problem).
Now we have an effective memorization structure, and we can safely apply breadth-first search to find position where part of famous sofa is located at top row. Use of breadth-first 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.
`
