|
Match Editorial |
Tuesday, March 10, 2003
The Problems
Div 1 had a rather rough set tonight, as only 1 person (SnapDragon) was able to solve all three problems successfully. However, SnapDragon was rather slow on the hard problem, and despite being the only one to solve all three problems, he came in third. It was lars, with the highest score on the hard, who took first place, pushing him up 184 rating points. WishingBone was a close second, and moved up 93 points. Div 2 had a rather easy set, and first timer TekGoNos won by a large margain.
NewPhone
Used as: Division 2 - Level 1:
Value 250 Submission Rate 163 / 196 (83.16%) Success Rate 112 / 163 (68.71%) High Score maximuscranius for 245.17 points
The most obvious way to do this is with a stable sort. A stable sort is one that preserves the order of elements with equal value. In this problem, you want to stable sort phone numbers so that those which are called more often come first. Then, you can just pick the first spaces numbers in your sorted array. Another way to do this, which is perhaps simpler, is to loop backwards through all possible frequencies (the max is 1000), and add the numbers to an array as they are found.
String ret[] = new String[spaces];
int ptr = 0;
for(int i = 1000; i>=0; i--) for(int j = 0; j<freq.length && ptr!=spaces; j++)
if(freq[j]==i)ret[ptr++] = n[j];
return ret;
RunLengthEncode
Used as: Division 2 - Level 2:
Used as: Division 1 - Level 1:
Value 500 Submission Rate 135 / 196 (68.88%) Success Rate 89 / 135 (65.71%) High Score Spike for 478.75 points
Value 200 Submission Rate 137 / 138 (99.28%) Success Rate 127 / 137 (92.70%) High Score Oblok for 198.08 points
Most people had little trouble with this, and getting it correct was not algorithmically difficult. Basically just check each character, and see if it is the start of a run of length greater than 4. If it is, delete the run, and replace it with a slash and the number of characters in the run. You could also do it by building a wholly new string out of the old one.
StringBuffer r = new StringBuffer(50);
for(int i = 0; i<input.length(); i++){
int j = i;
while(++j<input.length() && input.charAt(j)==input.charAt(i));
if(j-i>4){
r.append('/');
r.append(new DecimalFormat("00").format(j-i));
r.append(input.charAt(i));
i = j-1;
}else r.append(input.charAt(i));
}
return r.toString();
GiftWrap
Used as: Division 2 - Level 3:
Value 1000 Submission Rate 58 / 196 (29.59%) Success Rate 25 / 58 (43.10%) High Score TekGoNos for 774.59 points
Probably one of the easier div 2 hard problems. There are three different ways that the package can be wrapped, corresponding to the three different dimensions of the box. We can use each of the three dimensions as the dimension along which the seam runs after the paper is first wrapped around (the seam in step 3 of the diagram). Thus, if the seam runs down
dimension 1, then one of the dimensions of the paper must be
1 + 2 * (dimension 2 + dimension 3) - enough to wrap around, and overlap by 1. Note that we add one for the overlap, not two, because if the paper were just touching, we would only have to add 1 to one side of the paper to make it overlap by 1. So, then we must see how long the paper must be to fold down on the ends. Looking at the diagram provided, it should be clear that the overlap should occur along the longer dimension of the end that is folded over, across the shorter dimension. So, then if the first seam was along
dimension 1, the other two seams would cause the other dimension of the paper to be:
dimension 1 + 2 * (1/2 + min(dimension 2, dimension 3)/2) = 1 + min(dimension 2, dimension 3).
So, if the first seam runs along
dimension 1, then the paper's dimensions are:
1 + 2 * (dimension 2 + dimension 3) by
1 + dimension 1 + min(dimension 2, dimension 3).
Once you have this, you simply need to check that it is smaller than the paper given, and then follow the tiebreaker rules.
Used as: Division 1 - Level 2:
Value 450 Submission Rate 54 / 138 (39.13%) Success Rate 3 / 54 (5.56%) High Score Jumping John for 250.63 points
This was probably the hardest "450" ever. Only three people were able to solve it successfully, perhaps due in part to a slightly misleading problem statement, but much more probably due to the algorithmic difficulty of the problem. In response to the requests made in the round tables, here is a hint: try to think about which points the line hits, both of whose coordinates are integers.
Now, for the spoiler. The key to this problem is GCD. The first thing that we should do is divide dx and dy by gcd( dx, dy). This guarantees that if we successively increment x and y by dx and dy, we will hit every point that the line segments hit. As we increment, we have to wrap around, and count how many times we wrap around. Each time we wrap around, we will form a new line segment. When we get back to the point where we started (this is guaranteed to happen eventually), we are done.
The two things to watch for are cases when we hit the corners, and the case when dx or dy is negative. The easiest way to handle the negative case, in my opinion, is to simply flip things around so that nothing is negative. The corner case can be handled by decrementing the return value by one when we get to a corner, which will never happen more than once. But, this causes trouble for the case where dx or dy is 0, so we just handle that separately.
In the end, the solution seems surprisingly simple, which is what led to the misleading points assignment. The most common mistake seems to be the mishandling of the case where one or both of the directions is negative. People also had trouble when the line ran along an edge. There were also some solutions which timed out because they did not use division and modulus, but used addition and subtraction to accomplish the same thing. Here is something similar to the way most people did it:
int w = in[0], h = in[1], sx = in[2], sy = in[3], dx = in[4], dy = in[5];
if(dx==0||dy==0)return 1;
if(dx<0){
sx = (w-sx)%w;
dx = -dx;
}
if(dy<0){
sy = (h-sy)%h;
dy = -dy;
}
int g = gcd(dx,dy);
dx/=g;dy/=g;
int ret = 0;
int nx = sx, ny = sy;
while(true){
ret+=(nx+dx)/w + (ny+dy)/h;
nx = (nx+dx)%w;
ny = (ny+dy)%h;
if(nx==0 && ny==0)ret--;
if((nx-sx)*dy == (ny-sy) * dx && ret !=0)break;
}
return ret;
The above code is quite similar to all 3 successful submission, and was the easiest way to do it. However, for those who are interested, there is also a constant time solution (well, actually it's logrithmic in the size of the numbers because of gcd, but constant with respect to the answer) to this problem. The first thing to note in order to come up with this solution is that, unless the line hits a corner, the start location does not matter. To see this, imagine that you start at some point in the square, and draw all of the line segments. Then, if you shift the point one square to the right, all of the segments will shift one square to the right. It should not be too hard to verify that if shifting causes a segment to hit a corner, the total number of segments decreases by 1, while if shifting causes no segment to hit a corner, when it did before, then the number of segments increases by 1. So, this suggests that we should first start by calculating the number of segments in the case where none of the segments hits a corner. To do this, consider how far the segment goes up, each time it goes across the paper. A little algebra gives you
w*dy/dx, or
width*slope. Now, lets consider this as a fraction of the total height, so divide by h to get
(w*dy)/(h*dx). We represent this as a reduced fraction, which tells us how far up the paper we get, each time we go across it. So, now observe that we will end up back where we started when we have gone across the paper an integer number of times, in both the
x and
y directions. Thus, we want to find the smallest integer,
n, such that
n*(w*dy)/(h*dx) is an integer. In other words, the smallest number of times we have to go across the paper in the
x direction so that we have also gone across the paper an integer number of times in the
y direction. It is not hard to see that
n is the denominator in the reduced fraction
(w*dy)/(h*dx). Thus, the total number of segments is:
n+n*(w*dy)/(h*dx)=number of times across in the x direction + number of times across in the y direction
This brings us very close, but now we have to figure out if any of our segments hits a corner, in which case the answer is actually 1 less that calculated above. To figure out if it crosses a corner, first figure out where it crosses x=0 as a fraction of the total height. If the denominator in this fraction is a factor of the denominator of the fraction we previously calculated, then some segment will hit a corner. This is because of the property that, when n and d are relatively prime, there will be some x such that n*x % d = y for all integers y less than d.
That was probably a bit confusing, but if you try to work it out yourself with a paper and pencil, it should become clearer. Anyhow, here is the code:
int w = params[0], h = params[1], sx = params[2], sy = params[3], dx = params[4], dy = params[5];
if(dx==0||dy==0)return 1;
if(dx<0){dx=-dx;sx=(w-sx)%w;}
if(dy<0){dy=-dy;sy=(h-sy)%h;}
int g = gcd(dx,dy);
dx/=g;dy/=g;
int n = w*dy;
int d = dx*h;
g = gcd(n,d);
d/=g; n/=g;
int ret = d+n;
int nsy = sy*dx+dy*(w-sx);
int dsy = dx*h;
g = gcd(nsy,dsy);
dsy/=g;nsy/=g;
if(d%dsy==0){
ret--;
}
return ret;
Layoff
Used as: Division 1 - Level 3:
Value 1000 Submission Rate 13 / 138 (9.42%) Success Rate 11 / 13 (84.62%) High Score lars for 680.33 points
If you know max flow, this problem should be pretty easy, although it may take a while to code. If you don't know max flow, you were pretty much out of luck. I'm not going to provide an in depth explanation of how max flow works, because it is a rather long explanation, and there are better resources for it. The simplest algorithm to solve it is probably the Ford-Fulkerson Algorithm.
First a brief explanation of what max flow is. The problem is to find the largest possible flow from a designated source node, s, to a designated sink node, t, in a directed graph. Each edge in the graph has some capacity, and any number of units of flow up to that capacity may be pushed along that edge. Furthermore, for all nodes other than s and t, the incoming flow must be equal to the outgoing flow.
So, how is this problem max flow? Well, each position has some capacity, so add a node for each position, and draw a directed edge from that node to the sink, with a capacity equal to the number of positions of that type. Thus, for each type of position, we have one node. Similarly, for each type of person, we add a node, and draw an edge from the source to that node, with capacity equal to the number of that type of person. This ensures that the flow out of each person node will be at most the number of people that the node represents, and the flow out of each position node will be at most the number of positions that node represents. The crucial step is then to connect people to positions. For each type of person, we check each type of position and see if that type of person can do that type of job. If they can, then we add an edge of infinite capacity from the person's node to the position's node. It doesn't have to be infinite capacity, anything greater than 1000 will work in this case. Now, we run max flow, and return the number of people minus the flow. Since the incoming flow at each node other than the source and sink is equal to the outgoing flow, no person is assigned to more than one position, and no position is assigned to more than one person. And, if we draw all of our edge correctly, the max flow gives us a maximal assignment of people to positions.
So, assuming that you get the max flow part correctly, you then only have to determine how to draw edges from people to positions. This can be done be examining the strings related to each person and position in a pair wise fashion. If the person has a superset of the skills that the position requires, and his security clearance is greater than or equal to that required, then he can do the job.
