|
Match Editorial |
Online Round 3
Wednesday, August 31, 2005
Match summary
The competition heated up in round 3 of the TCO. Coders had little trouble with the easy problem, and many of them submitted the medium shortly thereafter. However, a rash of resubmissions should have clued everyone in that there was something a bit tricky about the medium, and many of the submissions ended up failing on a few tricky cases. At the end of the round, it was snewman who had the most points. tomek was not too far behind, followed by overwise. Good luck to everyone who advanced.
The Problems
PlayingCubes
Used as: Division One - Level One:
Value 250 Submission Rate 187 / 191 (97.91%) Success Rate 164 / 187 (87.70%) High Score RalphFurmaniak for 247.44 points (2 mins 53 secs) Average Score 215.50 (for 164 correct submissions)
Naturally, we'll process the words one at a time, independently. For
a given word, create a vertex in a graph for each letter in the word.
Then, for each cube, we create another vertex in the graph. Finally,
we draw edges from each vertex corresponding to a cube to each vertex
corresponding to a letter where that letter is on the cube. This
gives us a bipartite graph where one part is the vertices
corresponding to the letters in the word, and the other half is the
vertices corresponding to the cubes. Then just run bipartite
matching, and if the size of the matching is equal to the length of
the word, the word can be formed. That's one way to solve the problem
anyway...
Most coders, however, opted for the simpler solution made possible by
the fact that there were at most 8 cubes (always read the
constraints!). In this solution, a brute force recursive function is
written. It takes a word, a position in the word, and an array of
booleans stating which cubes have already been used. We need to find
a cube that contains the letter at the given position in the word, so
we just check every cube:
boolean recurse(word, position, used)
if(position == word.length) return true
for(i = 0; i<numcubes; i++)
if(!used[i] && cube[i].containsLetter(word[position])
used[i] = true
if(recurse(word,position+1,used)return true
used[i] = false
return false
In the worst case, there are 8 cubes that match the first letter, 7
that match the second and so on down to 1 cube for the last letter.
So there are 8! different execution paths our program could take
before getting to the last letter of the word. The containsLetter
method adds another factor of 6, since you might have to look at all 6
letters on each cube. Finally, there are 50 words, which gives us a
rough approximation of 12,096,000 operations: a big enough number that
you wouldn't want to have to count that many marbles, but not so big
that a computer can't do it in under 2 seconds pretty easily.
OptimalTax
Used as: Division One - Level Two:
Value 500 Submission Rate 182 / 191 (95.29%) Success Rate 60 / 182 (32.97%) High Score snewman for 473.23 points (6 mins 50 secs) Average Score 314.16 (for 60 correct submissions)
There are a few different ways to solve this problem. The most
obvious one (to me anyway) is to consider some range for which the
tax specified by index is optimal, which starts out very large: from 0 to
infinity. As we consider other taxes the
range for which the specified tax is optimal shrinks.
One good way to visualize this is to consider each tax as a line in the Cartesian
plane where the x axis represents income, and the y axis represents
tax. In this view, elements of fixedBase form the y-intercepts of the lines
and elements of percent form the slopes. A tax is optimal at a
particular income (x value) if the line representing it is below all
the other lines at that point. With this view, it should be clear
that the ends of the range for which tax index is optimal are
two points where the lines for that tax cross the lines for some
other taxes. To the right of the optimal region is a tax with a
lower percentage, while to the left of the optimal region is a tax
with a higher percentage.
Hence, we can iterate through all of the other taxes and find the
intercepts between those taxes and tax index. Using these
intercepts and the percentages of the other taxes, we can adjust
either the left or right end of the range as is appropriate. Finally,
we have to be sure to handle the special cases where two percentages of
two taxes are equal, as well as the cases where the optimal range
shrinks.
lo = 0;
hi = infinity;
for(int i = 0; i<percent.length; i++){
if(i == index)continue;
if (percent[i] == percent[index] && base[i] <= base[index])
return -1;
else if(percent[i] == percent[index])continue;
double x = 100.0*(base[i]-base[index])/(percent[index]-percent[i]);
x is the point where tax i and tax index
//result in the same payment
if(percent[i] <= percent[index]){
hi = Math.min(hi,x);
}else{
lo = Math.max(lo,x);
}
}
if(lo < hi)return lo;
else return -1;
Since you are dealing with simple fractions (no addition or
subtraction after the division), you don't have to worry about doubles
not being precise enough. If hi and lo should really be equal, then
they will be, and if they should really be different, then they will
be also. Finally, the problem can also be solved with a binary
search, which may be a bit easier for those who don't like
manipulating equations.
Springs
Used as: Division One - Level Three:
Value 1000 Submission Rate 22 / 191 (11.52%) Success Rate 7 / 22 (31.82%) High Score Eryx for 600.34 points (27 mins 22 secs) Average Score 465.11 (for 7 correct submissions)
Most coders are familiar with the idea of a binary search. In this problem, you had to take binary search to the next level, and nest it within itself. In the outer binary search, you are looking for the compression at the left end of the rod. At the inner binary search, you try to find the value for the right end of the rod, assuming that you've already got the value for the left end fixed from the outer search. Once you have the compressions for the left and right ends, the rest of them follow. So, the basic algorithm looks something like this:
initialize lo1, hi1
while(!done1){
mid1 = (lo1+hi1)/2
initialize lo2, hi2
while(!done2){
mid2 = (lo2+hi2)/2
if(toohigh2(mid1,mid2))
hi2 = mid2
else
lo2 = mid2
}
if(toohigh1(mid1,mid2))
hi1 = mid1
else
lo1 = mid1
}
Obviously, a lot of details were left out. In particular, the
toohigh1() and toohigh2() functions. But the idea is that toohigh1()
returns true if mid1 should be lower, and toohigh2() return true if
mid2 should be lower. But, how exactly do we calculate them? Lets
start with toohigh2(), we are going to have this function return true
if the total upwards force is greater than the weight of the rod, and
false otherwise.
Therefore, when our inner binary search terminates, we will have found
a value for mid2 such that the total upwards force generated by using
mid1 and mid2 is equal to the weight of the rod. However, this only
fulfills one of our conditions. The other one is that the torque must
be 0 at all the attachments to the springs. Before we tackle this
part of the problem, I want to show that we don't actually have to
calculate the torque everywhere, just at one point. If its 0 there,
its 0 everywhere.Lets say that the length of the rod is N, and the torque is 0 at some point K from the left. Furthermore, there is a force of M being exerted by the springs to the left of K, and hence N-M by the springs to the right of K. Now, let's say that we increase K by 1 and let's look at what happens to the four components of the torque:
Change In
Force Due to | Torque (Clockwise)
-------------+-------------+
Weight to R | (N-K-1)2/2 - (N-K)2/2 = (K-N)+1/2
Weight to L | K2/2 - (K+1)2/2 = -K-1/2
Springs to R | N-M
Springs to L | M
Note that we don't actually know or care how much torque the springs
to the left and right cause. But, we do know that the torque will go
up by M if all the distances from the point of rotation goes up by 1,
and the total force is M. So, if we add all the changes in torques up
we get:
((K-N)+1/2) + (-K-1/2) + (N-M) + M = 0
You may worry about the possibility of a springs switching from the
left to right when we move K by 1, but this case works out just as
well. So, with that out of the way, let's just worry about the torque
around the left most spring. Given a particular mid1 and mid2 we can
calculate this easily and then compare it to the torque from the
weight of the rod: len*len/2. If the torque from the springs is too
great, it means that there is too much force in the springs to the
right. The only way to reduce the torque is to shift some of the
force to the left (the sum of all the force must remain the same).
So, if there is too much torque, then it turns out that mid1 is too
low. Similarly, if there is too little torque then mid1 is too high.
Either way, we keep refining our bounds, lo1 and hi1 until the torque
is just right. Once both the torque and the total force are correct
(or as close to it as we can get with doubles), we are all done, and
we just compute the compressions of all the springs.
