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 ProblemsPlayingCubesUsed as: Division One  Level One:
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...
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 falseIn 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:
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. 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:
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 NM 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  (NK1)^{2}/2  (NK)^{2}/2 = (KN)+1/2 Weight to L  K^{2}/2  (K+1)^{2}/2 = K1/2 Springs to R  NM Springs to L  MNote 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: ((KN)+1/2) + (K1/2) + (NM) + M = 0You 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. 
