|
Match Editorial |
Tuesday, April 24, 2007
Match summary
Tuesday's night coding was no easy task for coders of either division. They faced problem sets with especially tricky medium problems, causing many solutions
to fail and making the challenge phase particularly active.
Division 1 started with many coders breezing through the easy and medium, although
with several flawed submissions on both that led to a couple of resubmissions and
lots of failures due to challenges or system tests. The hard problem required some
thought and also a lot of work. At the end, it all came down to challenges for the
several coders that could solve all 3 problems with good times.
tstan436 managed to win the match
and regain his target status thanks to his 2 succesful challenges.
Petr, on the other hand, was
pretty steady during challenge phase, with no attempt at all, but his speed in all
problems let him get home with a second place anyway. Last but not least,
Ying came in third, with
+75 in the challenge phase to secure his place by a little over 100 points of the fourth-place finisher.
Division 2 was a different story, with many coders getting trapped for several minutes
in the tricky medium. In the end, solving problems proved to be the way to go, and the
only three coders that were able to solve all problems got the entire podium.
lvxianjie was first,
moharrami followed him in second place
and ACrazyMan got third. All three earned a place in Division 1 for the next match.
The Problems
DiamondHunt
Used as: Division Two - Level One:
Value 250 Submission Rate 413 / 449 (91.98%) Success Rate 341 / 413 (82.57%) High Score tstan436 for 249.65 points (1 mins 4 secs) Average Score 213.83 (for 341 correct submissions)
This problem was rather easy and many coders were able to solve it pretty quickly. There were two approaches to it:
1. Do exactly as it says: Find any diamond, remove it, increment the result and keep doing that until no more
diamonds can be found. A good knowledge of the string functionality of your language was really useful here,
specially to increase the speed (and the score!), but also because less code means less bugs.
You can see an implementation of this idea in
tstan436's
solution.
2. Count the number of properly matched angle brackets. This was a little trickier to think but
much faster to code, because the whole problem could be solved with this simple C++ line:
int i,o=0,r=0;
for(i=0;i<mine.size();++i) if (mine[i]=='<') o++; else if (o>0) { o--; r++; }
return r;
It's a good excercise to try to understand why this code works, so I'll leave that to you.
CommonMultiples
Used as: Division Two - Level Two:
Used as: Division One - Level One:
Value 500 Submission Rate 289 / 449 (64.37%) Success Rate 73 / 289 (25.26%) High Score voidProject for 454.07 points (9 mins 13 secs) Average Score 319.53 (for 73 correct submissions)
Value 250 Submission Rate 421 / 430 (97.91%) Success Rate 312 / 421 (74.11%) High Score Petr for 248.45 points (2 mins 15 secs) Average Score 212.83 (for 312 correct submissions)
This problem needed only some simple math skills to be solved -- but if you weren't careful enough,
an overflow could kill your entire problem at any step of the way.
As many coders noticed, to be a multiple of all members of a is equivalent to being a multiple
of the LCM (least common multiple) of all of them. To find it, you can find the LCM of the first two
members, then the LCM of the result with the third member and so on (this holds simply by the definition,
try to see it!). To calculate the LCM of two numbers, we can make use of the following result:
LCM(a,b)*GCD(a,b)=a*b. Here GCD stands for "greatest common divisor." Now, the LCM(a,b) can be calculated
as a/GCD(a,b)*b. Note that it's better to do the division first to avoid overflowing. GCD can easily be
calculated with Euclid's algorithm (you can find it along with the rest of the solution in
Petr's
implementation).
IMPORTANT: The LCM can be TOO big to fit in any integer type, but this has a simple solution: Whenever
the partial LCM goes over upper, we can simply return 0. You also needed to do your calculations with 64
bit integers, because upper can be too close to the limit of 32 bit, and the overflow may pass unnoticed
even when the check is made at every step.
After all of this, all that's left is to count how many multiples of the LCM lie between lower and
uppper, and that's exactly upper/LCM-(lower-1)/LCM, which is the number up to
upper inclusive substracted with the number of multiples strictly less than lower.
Used as: Division Two - Level Three:
Value 1000 Submission Rate 51 / 449 (11.36%) Success Rate 4 / 51 (7.84%) High Score lvxianjie for 670.15 points (22 mins 23 secs) Average Score 527.73 (for 4 correct submissions)
As with many Division 2 hards, this problem was a classical exercise in dynammic programming, but only 4 coders
were able to solve it correctly.
First, notice that since delivery is instant, it is always best to deliver a letter the first time you pass
through the door of the corresponding house. Thinking in that direction, at every moment the set of houses
that have their deliveries made is an interval with the intitial position inside.
You should also notice that you need to go through the houses one by one -- it's never useful to change direction
at any other point (because you are just losing time). So, we can define the state with 3 integers:
- The beginning of the already delivered interval
- The end of the already delivered interval
- The current position
See lvxianjie's code for an iterative implementation of this idea.
HeightRound
Used as: Division One - Level Two:
Value 500 Submission Rate 317 / 430 (73.72%) Success Rate 96 / 317 (30.28%) High Score Egor for 483.57 points (5 mins 16 secs) Average Score 298.30 (for 96 correct submissions)
Greedy problems seem to be in fashion lately for Division 1 mediums, and this one was no exception. Many
coders looked at it too greedily, however, and lost all their points in challenges or after the system testing.
The crucial observation is that the round is made of two intervals, one in increasing order and one in decreasing
order. See it this way: The shortest person (A) must be the first element of the return array (because the lexicographical
order says so, and there's always a rotation of a solution that makes him first). Suppose now that the tallest person (B)
is at position k. In any solution, you can sort the segment that goes from A to B and that would never increase the
maximum difference while actually having a lexicographically first solution. For the segment that goes from B to
the end, sorting that in decreasing order also never increases the maximum difference, but we might need to "move" some
people to the front (before B) to actually get the lexicographically first solution. I'll stop here because a formal
demonstration would be too long, but try to see that those moves always help you with the lexicographic thing (because
you can always insert those moved guys before a taller one and maintain the order).
The right greedy thing to do was actually not completely greedy. First, you need to fix the best difference (here there
were several options, like iterating over each one and returning the first that has a correct answer or binary
searching, or even doing a dynamic programming code that finds it like
SnapDragon
did).
With a fixed maximum difference (let's call it D), we need to build a lexicographically short round that does not
go over D in any step. As mentioned above, we divide the sequence into 2 parts, first an increasing sequence from A
to B and then a decreasing sequence from B to the end.
To build the last part, we can do it greedily (finally the greedy part!) by inserting each time the greater element
that does not violate D. First we start with A at the bottom. Find the greater element less than or equal to A+D and
make that element the last one (adjacent to A). After that, find the greater element less than or equal to C+D where C
is the new element and so on, until the difference of an added element and B is less than or equal to D. At that point, we
place all the remaining elements in the initial segment, in sorted increasing order. If the obtained order does not
violate D, it's a lexicographically first solution. If it does, no solution can be constructed with that D.
See the
solution
made by Ying for a clear implementation of the idea
of iterating over D.
Used as: Division One - Level Three:
Value 1000 Submission Rate 53 / 430 (12.33%) Success Rate 19 / 53 (35.85%) High Score Ying for 919.97 points (8 mins 31 secs) Average Score 560.58 (for 19 correct submissions)
Geometry problems always require some geometrical subroutines, but in this case, seeing the problem
in the correct angle reduced the actual geometric part to a minimum.
First, divide the perimeter into the perimeter that each circle has and is not "covered" by any
other circle. If you add up those, it will give you the perimeter of the union.
For each circle 2 steps are needed.
- If it's contained in another circle, the uncovered perimeter is 0
- Calculate how much of its perimeter is uncovered and add it to the result
Let's call the current circle C and iterate over every other circle D. For each D, we can see weither there is an intersection or not by comparing the sum of the radius with the distance between the centers. If there is no intersection, we do nothing; if there is one, we want to calculate the angle of the segment that goes from the center of C to each of the intersections (because the length of the covered arc is proportional to that angle). We can easily find those angles by using the cosine theorem and an atan2 function (you can find the actual equation in the code below).
Once we have the right pair of angles for each intersecting circle, we need to find the length of the union of those and then take the complement and add 2PI*radius*ANGLE/2PI=radius*ANGLE to the result, where ANGLE is the size of the complement of the covered interval. To do that, we can sort the initial and ending points of each interval and iterate over both of them simultaneously in increasing order. At each intial point, we add 1 to some variable, and at each ending point, we substract 1. Each interval between 2 of those in which the variable is in 0 is an uncovered interval so we add its length to ANGLE.
Java code for this problem follows:
long sqr(long x) {return x*x; }
double sqr(double x) {return x*x; }
long dist2(long x1, long y1, long x2, long y2) {return sqr(x1-x2)+sqr(y1-y2);}
void add(Map<Double,Integer> m, Double x, int v) {
if (!m.containsKey(x)) m.put(x,0);
m.put(x,m.get(x)+v);
}
void addInt(Map<Double,Integer> m, Double f, Double t) {
add(m,f,1); add(m,t,-1);
}
public double perimeter(int[] x, int[] y, int[] r) {
int n=x.length;
double res=0.0;
for(int i=0;i<n;++i) {
double rc=0.0;
boolean ok=true; //check if current circle its inside another circle
for(int j=0;j<n;++j)if(sqr(r[j]-r[i])>=dist2(x[i],y[i],x[j],y[j])
&& (r[j]>r[i])) ok=false;
if (!ok) continue;
//calculate the intervals and store them into ints
Map<Double,Integer> ints = new TreeMap<Double,Integer>();
ints.put(0.0,0);
ints.put(2.0*Math.PI,0);
for(int j=0;j<n;++j)if (i!=j) {
long d2=dist2(x[i],y[i],x[j],y[j]);
//check intersection with this circle
if (d2>=sqr(r[i]+r[j])||d2<=sqr(r[i]-r[j])) continue;
double alpha,beta,med,offset;
//triangle sides
double a=r[i];
double b=Math.sqrt((double)dist2(x[i],y[i],x[j],y[j]));
double c=r[j];
//difference between the line that goes through
//both centers and the intersections
offset=Math.acos((sqr(a)+sqr(b)-sqr(c))/(2.0*a*b));
//angle from the line that goes through both center with the axis
med=Math.atan2(y[j]-y[i],x[j]-x[i])+2.0*Math.PI;
if (med>=2.0*Math.PI) med-=2.0*Math.PI;
alpha=med-offset; if (alpha<0) alpha+=2.0*Math.PI;
beta=med+offset; if (beta>2.0*Math.PI) beta-=2.0*Math.PI;
if (alpha>beta) //interval passes through 0, so we split it
{ addInt(ints,0.0,beta); addInt(ints,alpha,2.0*Math.PI); }
else addInt(ints,alpha,beta);
}
//calculate the sum of uncovered angle intervals
double tot=0.0,ant=0.0; int h=0;
for(Map.Entry<Double,Integer> e : ints.entrySet()) {
if (h==0 && e.getKey()>0.0) tot+=e.getKey()-ant;
h+=e.getValue();
ant=e.getKey();
}
res+=tot*r[i];
}
return res;
}
