Match Editorial

Round two seemed very tricky for most coders, dispite the low point values for the easy and hard problems. In fact, 9 red coders were eliminated, 6 of them scoring 0 points or less. Most people believed that the low scored easy and hard were undervalued. It's often difficult to determine the value for greedy problems because you don't know how fast a coder can prove to his- or herself that the greedy algorithm works. A tough but mostly standard level 2 problem was the only salvation for a few coders who were fooled by the greedy problems.

haha was the star of this round, scoring slightly less than SnapDragon in points, but taking the lead with two challenges. Heavyweights radeye, snewman and tomek rounded out the top 5. Incidently, Rustyoldman was the only coder ranked below yellow who made the cut, but he changed colors in the process.

The Problems

Value	200
Submission Rate	154 / 184 (83.70%)
Success Rate	88 / 154 (57.14%)
High Score	indigo9 for 198.52 points (2 mins 27 secs)
Average Score	165.25 (for 88 correct submissions)

Usually easy problems don't make you think much, but this one was an exception. Here we are looking for the maximum number of bags we have to buy. Clearly we can't use brute force to find the worst case, as there are way too many combinations. In one bag alone, there are 10,626 possible combinations of colors. Figuring this out for thousands of bags would be undoable in the allotted time.

However, for this problem, we are only interested in the very worst possibility. To solve it, imagine we have 5 buckets, each representing a color. We'll add beans to buckets one bean at a time. When the bucket has quantity beans in it, it is emptied, and the number of sets is incremented by one. Each bucket represents beans of a certain color that aren't part of a set. To maximize the beans placed into buckets, we want to fill each bucket with quantity-1 beans. At that point, no matter what color bean is next, a set is formed. After the set is formed, the bucket is emptied. To ensure the worst case, the next quantity-1 beans should go into the empty bucket. Any other color, and another set is formed early.

This greedy algorithm should be enough to code a solution which runs fast enough. However, there is a constant time solution which uses the fact that the last state of the buckets is that 4 of them are full of quantity-1 beans. Therefore, the final number of beans required is:

quantity * children + (quantity-1) * 4

In all cases, we need to round up this to a multiple of 20, since even if we need only one bean, we need to buy a whole bag. Therefore, the final formula is:

(quantity * children + (quantity - 1) * 4 + 19) / 20

Value	600
Submission Rate	74 / 184 (40.22%)
Success Rate	64 / 74 (86.49%)
High Score	Yarin for 543.99 points (9 mins 18 secs)
Average Score	365.74 (for 64 correct submissions)

Many knowlegable coders will recognize this as the infamous traveling salesman problem. Many people know that this problem is NP-complete, but with the number of locations limited to 15, a O(2ⁿ) solution will run in time.

The first thing to note is that the time to move the pen is not the cartesian distance, but rather the maximum of the x and y distances. This is because both motors can run simultaneously.

To solve the graph problem, We'll use recursion with memoization of 2ⁿ * n states. Part of the state will be a bitmask representing which lines have been drawn, and the other part will be which line endpoint the pen is located at. The recursive function will return the minimum time needed to draw the rest of the lines.

For each run of the recursive problem, we try drawing each undrawn line starting from either endpoint. The new state is that the pen is on the other side of the line just drawn, and the bitmask has a bit added for the line just drawn. We add on the time it takes to move the pen to the endpoint, and then to move the pen (while drawing) to the other endpoint. By memoizing on the state, we can reduce the runtime to O(2ⁿ * n).

Value	900
Submission Rate	46 / 184 (25.00%)
Success Rate	16 / 46 (34.78%)
High Score	haha for 637.39 points (20 mins 3 secs)
Average Score	465.11 (for 16 correct submissions)

It's that time of the year again! Baseball is one of America's greatest games, and the race for the playoffs is generally very tense. In this problem, we are trying to see if we can stop the worrying, and see if our team is out or in.

This problem seems at first like it could be solved with maximum flow, but in the end, it turns out to have a very easy greedy solution. You perform two checks on the team. If it wins all its remaining games, is it still forced out of the playoffs, and if it loses all its remaining games, is it still in the playoffs.

One of the other issues is to make sure the wins acheived in the rest of the season are consistent with the number of games played. We know that each team will play gamesLeft games. Each game is played by two teams, so the number of games left to be played by all the teams are gamesLeft * numTeams / 2. The constraints guarantee that this is a whole number. As it turns out, because of the way the constraints are, we don't have to keep track of which team plays who. We just assign wins to whichever team we want. All we have to do is to make sure no team gets more than gamesLeft wins added to their record, and that the total number of wins added equals gamesLeft * numTeams / 2.

So keeping this in mind, to answer the first question, we assign gamesLeft wins to the team in question. Then we want to assign wins to the other teams, trying to keep our team from being eliminated. If there is no possible way to do this, the team is eliminated. To keep the team at the same rank, we first can assign gamesLeft wins to all the teams that rank higher than it. If there are any games left, we should first assign wins to teams lower than it, but only enough to make those teams tie the target team. If we still have wins left to assign, we must assign those wins to the tied teams, but here, it is important to assign wins to teams which have more games left to play, as we can use up more wins on those teams without changing the rank. If all this is done correctly, and the team still isn't in the top N ranking teams, it has been eliminated.

A similar procedure is followed for the question of clinching. However, this procedure is a little simpler. We want to see if it is possible for a team to not make it into the playoffs. We still have the same constraints on the total wins assigned. Assigning wins to higher ranking teams doesn't help, since those teams cannot push our team out, so we assign wins to teams who are lower ranking until they have enough wins to just tie our team. We choose the team to assign the wins to based on how close it is to our team's record. The closer ones are chosen first because they use up fewer wins to tie our team. At the end, if the set of tied teams is not all in the playoffs, then the team cannot clinch. If our team and all the teams tied with it are in the playoffs, then the team has clinched.