|
Match Editorial |
Tuesday, December 30, 2003
Match summary
SRM 177 was a brutal blood bath for division 1, with problems so hard even Yarin scored only 50 points on a challenge. Another notable red coder was not so lucky, and ended up with -50, in what was perhaps the hardest SRM in months. Division 2 had an easier time of things, as most coders breezed through the easy and medium problems, but hit the wall that was their hard and division 1's medium. After the dust settled and system tests were run, only 61 out of 134 division 1 coders had positive points, and only 48 of those had any successful submissions. Out of the chaos, only a single coder, and a yellow at that, Mike Mirzayanov, was able to complete all three problems, and take the day with an impressive rating jump. WishingBone took second, and nicka81 third, while coders with 0 points gained as much as 22 rating points. In division 2, new comer pparys won easily, with datawrangler a distant second, and new comer nicram in third.
The Problems
Stairs
Used as: Division Two - Level One:
Value 250 Submission Rate 154 / 188 (81.91%) Success Rate 125 / 154 (81.17%) High Score hilgart for 237.25 points (6 mins 39 secs) Average Score 181.32 (for 125 correct submissions)
With limits of 1000 on all of the inputs, a brute force approach, trying every possible height and width would easily run in time on this problem. The most straightforward approach is to loop over each conceivable height (1 to maxHeight). Once you have the height, you must first check to see if the totalHeight is divisible by the height. If it is not, then simply go on to the next height. Next, we calculate the width of the treads. The number of risers is totalHeight/height, and there is one less tread than riser. So, with the number of treads in hand, we check that the totalWidth is divisible by that number, and then make sure that the width is large enough. One tricky case to watch out for is when there is only a single riser, and no tread. There are a number of other ways to solve this problem, but the basic idea is always the same: iterate over one of the parameters (or two if you like) and do a bit of arithmetic to find the valid pairs.
int ret = 0;
for(int i = 1; i<=maxHeight; i++){
if(totalHeight%i!=0)continue;
int cnt = totalHeight/i-1;
if(cnt==0 || totalWidth%cnt!=0 || totalWidth/cnt < minWidth)continue;
ret++;
}
return ret;
OldestOne
Used as: Division Two - Level Two:
Value 500 Submission Rate 141 / 188 (75.00%) Success Rate 122 / 141 (86.52%) High Score RandySaint for 466.55 points (7 mins 43 secs) Average Score 334.98 (for 122 correct submissions)
This problem wasn't really much harder than the easy. The only thing that really makes it harder is that it requires some knowledge of string manipulation, whereas the easy requires only numeric manipulation. Anyhow, the simplest way to solve this is first find the index of the first digit in the string. Then, starting at the first digit, find the next space in the string. That gives you the substring relating to the age of the student, and then its just a matter of parsing the string into an int. The name of the student is also easy to attain from this, it is just the characters before the first digit, with leading and trailing space trimmed off.
Removal
Used as: Division Two - Level Three:
Used as: Division One - Level Two:
Value 900 Submission Rate 61 / 188 (32.45%) Success Rate 3 / 61 (4.92%) High Score pparys for 823.34 points (8 mins 50 secs) Average Score 588.40 (for 3 correct submissions)
Value 450 Submission Rate 80 / 135 (59.26%) Success Rate 20 / 80 (25.00%) High Score Kavan for 392.23 points (11 mins 14 secs) Average Score 260.40 (for 20 correct submissions)
The simplest way to solve this problem is to consider events in reverse. First, consider where the kth element of the sequence would have been before the final removal. Then the removal before that, and so on. We handle each removal the same way, and after we have undone all of the removals, we end up with the initial position. So, then all that remains is to figure out exactly how to undo a removal. Let the index of the number after the removal be k and the removal be given be lo and hi. If lo is greater than k, then the removal of the elements may not effect the sequence, as each element removed comes later than the kth and does not effect its position. If, on the other hand, lo is less than or equal to k, then each element removed came before k, and so we set k = k + hi - lo + 1. Then, before we return the final k we need only check that it is at most n (the total number of element in the sequence). The only other detail to this method is that we must use 64 bit integers, or else we will overflow:
public int finalPos(int n, int kk, String[] remove){
long k = kk;
for(int i = remove.length-1; i>=0; i--){
int lo = Integer.parseInt(remove[i].split("-")[0]);
int hi = Integer.parseInt(remove[i].split("-")[1]);
if(k>=lo)
k+=hi-lo+1;
}
return (int)(k>n?-1:k);
}
TickTick
Used as: Division One - Level One:
Value 300 Submission Rate 78 / 135 (57.78%) Success Rate 35 / 78 (44.87%) High Score nicka81 for 234.43 points (15 mins 59 secs) Average Score 177.98 (for 35 correct submissions)
This problem stumped many a fine coder, causing trouble even for most of the reds. The trick to solving it was to figure out which times to consider for the first tick. To start off, lets first note that the beginning of the program is essentially the same as an event, since it can either be in the same or in a different tick as the next event. Now, lets us consider some time for the first tick (before the start of the program) which is not an integral distance from any event. Now, that time causes some sequence of 'S's and 'D's. Imagine that we now slide the time of the first tick so it happens a little earlier, but not so much earlier that the sequence changes at all. In fact, as long as the tick remains the same number of full ticks away from each of the events, we can continue sliding. To find out exactly where we have to stop, we need only find how far we can slide it and remain the same number of whole ticks away from each event. Now, all this sliding around and you're likely to slip and introduce some bug in your code. Instead, note that we can always slide the tick down to the point where it is just a hair greater than an integral distance from some event. So, instead of doing any sliding, we need only consider ticks that occur just after some event. In fact, we need not even worry about when the first tick is before the program starts, since one tick tells us when all the others are. So, in pseudocode:
set ret
add time = 0 to events
for i = 0 to lengthOf(events)
double tick = events[i]+5e-8
double prev = NaN
String seq = ""
for j = 0 to lengthOf(events)
double tickIndex = floor(events[j]-tick)
if(tickIndex==prev)
seq = seq + "S"
else
seq = seq + "D"
add s to ret
return sizeOf(ret)
And then in Java, using bitmasks:
TreeSet ts = new TreeSet();
double[] e = new double[events.length+1];
for(int i = 0; i<events.length; i++)e[i+1] = Double.parseDouble(events[i]);
for(int i = 0; i<e.length; i++){
double d = e[i]+5e-8;
double prev = Double.NaN;
long s = 0;
for(int j = 0; j<e.length; j++){
double n = Math.floor(e[j]-d);
if(n==prev)s|=1<<j;
prev = n;
}
ts.add(new Long(s));
}
return ts.size();
Warehouse
Used as: Division One - Level Three:
Value 1000 Submission Rate 15 / 135 (11.11%) Success Rate 3 / 15 (20.00%) High Score WishingBone for 737.77 points (18 mins 21 secs) Average Score 599.09 (for 3 correct submissions)
The first step to solving this problem is realizing which paths to consider. Obviously, there are way to many possible paths to try them all (an infinite number, in fact), but only a few that could potentially be optimal. Each potentially optimal path is defined by either 2 or 3 posts (where the corners are considered posts). The paths defined by 2 posts have the truck traveling perpendicular to the line between the 2 posts. A simple example of this is when the truck travels due east between two posts with equal x coordinate. In the 3 post case, the truck comes close to two of the posts on one side, and to the third on its other side. We can show that these all optimal paths will fall into one of these cases by imagining some other path, and showing that it must be suboptimal.
Let us first start with a little bit of essential computation geometry before we delve into the whole solution. First, the distance from a line defined by two points, p1 and p2, to a point, p3, can be found be taking the cross product of p3-p1 and p2-p1 where subtraction means the subtraction of the x and y coordinates independently. The cross product yields the area of a parallelogram those base is given by p1 and p2 with a third point at p3. Since the area of a parallelogram is simply base times height, we can get the height by taking the area divided by the length of the base. In other words, the cross product divided by the distance between p1 and p2.
double distToLine(point p1, point p2, point p3){
vector v1 = p2-p1;
vector v2 = p3-p1;
double cross = v1.x * v2.y - v2.x * v1.y;
double base = sqrt(v1.x * v1.x + v1.y * v2.y);
return cross/base;
}
One important thing is that the distance will be negative if the point is one side of the base, and positive if it is on the other. The actually distance is simply the absolute value, but in many cases, knowing which side the point is on is also important.
That is almost all of the geometry that you need for this problem. Some line intersection code is necessary for some implementations, but we won't need it for this implementation. To avoid it, we will add posts at regular intervals along the upper and lower walls. This means that we don't have to worry about paths that go through the wall as special cases, since the will be smaller than paths that don't. With only 50 posts, we know that the gap must be at least 4 units wide, so if we add posts every 4 units along the walls, that will be sufficient. Next, we will consider paths defined by only two posts, p1 and p2. To make our code simpler, we will convert this case into the 3 post case by imagining that there is a third post at p3 such that the line between p1 and p2 is perpendicular to that between p1 and p3. That way, a truck traveling perpendicular to the line between p1 and p2 will almost touch p3, and we have the 3 post case. To find p3, we do the following:
p3.x = p1.x + p1.y - p2.y
p3.y = p1.y + p2.x - p1.x
Now, both cases can be handled the same way: for some pair of points, find the width of the widest truck that can drive through such that one of its sides almost touches both of those points. In the case outlined above, the points are p1 and p3. In the three points case, we simply consider all pairs of points given by two posts.
Finally, for the given two points, we find the two points nearest the line on either side. As mentioned above, we can tell which side the point is on based on the sign of the cross product. Since the line itself is defined by at least one post, we get two widths: the width going down one side, and the width going down the other side. We can safely ignore points on the line (distance = 0) and needn't worry about using an epsilon since the cross product will be exactly 0 for points on the line. The only other thing to note is that if there are no points on one side of the line, then that side of the line is outside of the warehouse, and shouldn't be considered. The return value is just the width of the widest path found when considering all pairs of posts, minus a small epsilon.
double ep = 1e-13;
public int feetWide(int[] xx, int[] yy){
int[] x = new int[xx.length+102];
int[] y = new int[xx.length+102];
for(int i = 0; i<xx.length; i++){
x[i] = xx[i];
y[i] = yy[i];
}
for(int i = 0; i<=50; i++){
x[xx.length+2*i] = 4*i;
y[yy.length+2*i] = 0;
x[xx.length+2*i+1] = 4*i;
y[yy.length+2*i+1] = 200;
}
double ret = 0;
for(int i = 0; i<x.length; i++){
for(int j = 0; j<i; j++){
double[] d = doit(x,y,x[i],y[i],x[j],y[j]);
ret = Math.max(ret,d[0]);
ret = Math.max(ret,d[1]);
d = doit(x,y,x[i],y[i],x[i]+y[i]-y[j],y[i]+x[j]-x[i]);
ret = Math.max(ret,d[0]);
ret = Math.max(ret,d[1]);
}
}
return (int)(ret-ep);
}
double[] doit(int[] x, int[] y, int x1, int y1, int x2, int y2){
double c1 = 10000, c2 = 10000;
for(int k = 0; k<x.length; k++){
double dx1 = x[k]-x1;
double dy1 = y[k]-y1;
double dx2 = x2-x1;
double dy2 = y2-y1;
double dist = (dx1*dy2-dx2*dy1)/Math.sqrt(dx2*dx2+dy2*dy2);
if(dist<0){
c1 = Math.min(c1,-dist);
}else if(dist > 0){
c2 = Math.min(c2,dist);
}
}
return new double[]{c1==10000?0:c1,c2==10000?0:c2};
}
