Match Editorial

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.

In division 2 only da_brain_damage solved all three problems, winning easily. bcloud, the only other coder to solve the hard problem took second, while a newcomer, szywrz got third.

The Problems

Value	250
Submission Rate	265 / 285 (92.98%)
Success Rate	242 / 265 (91.32%)
High Score	mhykol for 249.34 points (1 mins 28 secs)
Average Score	195.45 (for 242 correct submissions)

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.

Value	500
Submission Rate	183 / 285 (64.21%)
Success Rate	25 / 183 (13.66%)
High Score	szywrz for 420.54 points (12 mins 51 secs)
Average Score	303.32 (for 25 correct submissions)

Value	250
Submission Rate	215 / 221 (97.29%)
Success Rate	76 / 215 (35.35%)
High Score	rem for 241.18 points (5 mins 28 secs)
Average Score	197.27 (for 76 correct submissions)

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.

There are a number of ways to work around this. The most reliable is to avoid doubles altogether. Instead, consider representing fractions using two 64 bit integers -- one for the numerator and one for the denominator. Then you can check the equality of two fractions by cross multiplying: a/b == c/d if and only if a*d == c*b. Unfortunately, this makes the problem more complex, and makes solutions longer. In many problems, including this one, it suffices to use a small epsilon when checking for equality. If two floating point values are less than that epsilon apart, then consider them equal. Of course, this can cause other problems: if your epsilon is too big, you will consider things equal that you oughtn't, while if it is too small, the opposite is true. In this problem, it turns out that the closest two numbers ever get without being equal is about 7E-9, so an epsilon less than that and greater than about 1E-14 worked well. If you work through a bit of the math required for computing the result as a fraction, you can come up with the lower bound given above.

Value	1000
Submission Rate	4 / 285 (1.40%)
Success Rate	2 / 4 (50.00%)
High Score	da_brain_damage for 453.41 points (44 mins 46 secs)
Average Score	452.02 (for 2 correct submissions)

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 non-letter 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.

The hard part, of course, is in the details of how you do this. If you use something like an ArrayList for each sentence, it makes it easier to remove a sequence of words, and insert a single acronym in their stead. You will probably also find it easier if you write a function to extract all capital letters from a word, and also to extract trailing punctuation.

Value	500
Submission Rate	129 / 221 (58.37%)
Success Rate	50 / 129 (38.76%)
High Score	John Dethridge for 418.88 points (13 mins 2 secs)
Average Score	290.87 (for 50 correct submissions)

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.

To make this work properly, you need to make sure you calculate the values for all valid J before you can calculate it for K. This can be done by sorting the shows by start time.

Value	1000
Submission Rate	25 / 221 (11.31%)
Success Rate	18 / 25 (72.00%)
High Score	AdrianKuegel for 948.32 points (6 mins 42 secs)
Average Score	695.95 (for 18 correct submissions)

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.