Thursday, July 7, 2005 Match summary
Coders in both divisions stumbled over floating point difficulties today, as most
div 1 easy and div 2 medium submissions failed. This left lots of opportunities
for challenges, and misof took advantage with a whopping 250 points in the
challenges phase. This, combined with good times on the medium and hard
problems allowed him to overcome a failed easy problem and take first place,
beating out a number of coders with three correct submissions. warmingup took
second place without the help of any challenges, while rem was a distant
third. The ProblemsColorCodeUsed as: Division Two  Level One:
Whenever you see a problem like this, your first step should be to place all the string constants in an array. This will make it easy to convert from a string to an integer with a simple for loop. Once you have done this, just convert each of the three input strings to integers, and perform the appropriate math. LanguageRecognitionUsed as: Division Two  Level Two: Used as: Division One  Level One:
You need to be a little bit careful dealing with floating point arithmetic.
Since fractions can often not be represented exactly, small errors may creep
into your calculations. In many settings, this is unimportant, but it becomes a
big deal when you are trying to figure out if two things are equal using
doubles. As an example, consider adding three thirds. Clearly, the sum should
be one, but if each third is represented as 0.333333333, then the sum will be
0.999999999, which is slightly off from 1. This is the sort of problem that
caused so many solutions to fail this problem. Used as: Division Two  Level Three:
New lines count as spaces, so the first thing to do is concatenate all the input
elements into one string, inserting spaces. Once this is done, you can break
the document into sentences by splitting the string up at double spaces (Java's
String.split(s," ") works well for this). Then, you need to find the sequences
meeting the criteria in each of the sentences. You can do this by scanning the
words in the sentence one at a time. If you hit an uppercase word that doesn't
start a sentence, it may be the start of an acronym, so start checking ahead to
see how many words you can go before you hit the end of the sentence, or two
consecutive uncapitalized words. If you find that there is a valid sequence,
then acronize that sequence. When you do this, be careful to only include words
that start with an uppercase letter. Also, you must include the nonletter
characters from the end of the last word. Once you've acronized a sequence,
simply move on to the next word and repeat. If you find that a word is not part
of any acronym, simply leave it alone. Once you are done acronizing, put the
sentences back together in one String, with two spaces between sentences and
return the result. Used as: Division One  Level Two:
Because the schedule wraps around, the best way to solve this problem is to
independently consider each 24 hour period that starts at the beginning of each
show. With the starting time of the period, you want to find how many minutes
of TV you can watch starting with the show beginning at that time. To do this,
you can use dynamic programming. You can compute the maximum number of minutes
watched ending with a particular show, K, provided K doesn't overlap with the
show that starts at the beginning of the period. You must watch that show K
after some other show, J, that ends before the show K starts. If you find the
maximum number of minutes that you could watch TV ending at show J for any J
where J ends before K starts, this will give you the maximum number of minutes
of TV you can watch up until the start of K. Then, you just add the length of K
to get the maximum number of minutes you could watch up to the end of K.
Used as: Division One  Level Three:
Coders who took the time to solve last week's problem correctly benefited today. An easy way to solve this problem uses four common methods: line intersection, point in polygon, convex hull, and polygon area. First, find the intersection points between all the segments in polygons 1 and 2. These points will be on the edge of the polygon defined by the intersection. Next, find all of the vertices that make up polygon 1 and also inside polygon 2, as well as those that make up polygon 2 and are also inside polygon 1. At this point, you have found all of the vertices of the polygon formed by the intersection. However, unless you did something fancy, you don't know what order they form the polygon, so you can't find the area. To get them ordered, run your convex hull code, and then just return the area of the resulting polygon. This, combined with some prewritten code, was how AdrianKuegel was able to solve the problem in under 7 minutes. If you aren't familiar with some of these methods, check out the education content section of TopCoder. 
