Match Editorial

Match summary

This match was SRM number 314, which is the truncated decimal expansion of pi to two decimal places, putting it quite exclusive company -- only SRM 3 (May 2001) and SRM 31 (September 2001) also start the decimal expansion of pi , and these three will be the only ones until SRM 3141, projected to occur in the year 2062 (assuming the current rate of about fifty SRMs per year). For this momentous occasion, 744 competitors showed up, 349 in Division I and 395 in Division II.

In Division I, Petr opened up the match by solving all three problems in about thirty minutes, but he quickly resubmitted his 1000 point problem twice. Taking the lead from him was Burunduk2 , with 1431.91 points. After challenge phase, Petr rose back up to second place with four successful challenges. All their solutions passed, giving Burunduk2 his first SRM win. Rounding out the top five were HiltonLange, overwise, and andrewzta.

In Division II, jfguo won the division handily with 1496.09 points, beating newcomers m_artur and Jonick by over 100 points, despite Jonick having the fastest submissions for both the easy and medium. Rounding out the top five were hoanglb and glee.

The Problems

Value	250
Submission Rate	321 / 395 (81.27%)
Success Rate	242 / 321 (75.39%)
High Score	Jonick for 248.00 points (2 mins 33 secs)
Average Score	191.67 (for 242 correct submissions)

Here we have a farm with some very loud cows, who are happiest when they hear each other. However, only one of the cows is allowed to moo here, and you have to determine which one, and what the total amount of dissatisfaction is when that cow moos.

If you look at the formula for the total dissatisfaction (the number you needed to find), the total dissatisfaction when one given cow moos is the sum of the dissatisfactions between it and all other cows. This suggests a simple solution: loop through all cows and simulate what would happen if that cow mooed, and take the minimum of all of those. At most the farmland can be 50 x 50 squares large, which means that there can be at most 2500 cows on the land. This means that 2500 x 2499 distance calculations need to be done, which will run in plenty of time.

For a clean implementation, have a look at Jonick's implementation here. Note that in his solution, the dissatisfaction between a cow and itself is also added to the sum, but this does not change the answer, because that dissatisfaction is always zero!

The majority of submissions that failed unfortunately set their "infinity" value to be smaller than the maximum possible return value, and thus failed on the largest possible test case: a 50 x 50 grid, each square containing a cow.

Value	500
Submission Rate	213 / 395 (53.92%)
Success Rate	187 / 213 (87.79%)
High Score	Jonick for 486.14 points (4 mins 49 secs)
Average Score	334.99 (for 187 correct submissions)

Value	250
Submission Rate	341 / 349 (97.71%)
Success Rate	333 / 341 (97.65%)
High Score	Petr for 248.19 points (2 mins 26 secs)
Average Score	207.56 (for 333 correct submissions)

At least a few coders (myself included) read the problem, then looked at the input constraints, which specified that there would be at most ten soldiers, and immediately thought, "next_permutation!" In fact, that was probably the quickest way to code up a solution: try all possible orderings for the soldiers and check each to see if it is consistent with the input. Since you were guaranteed by the problem statement that there would be exactly one solution, this procedure would find it. This solution runs in O(N! * N^2). This is admittedly borderline for N = 10, but should run in time if you make sure to break out of the check early if it has already failed.

The much more elegant solution is to actually construct the soldiers' ordering using some logic. We will loop from the tallest soldier to the shortest and insert each in the correct spot (to the right of the correct number of taller soldiers) as we go. Note that this means two things. First, when we reach a certain soldier, all of the soldiers he possibly could have noticed to his left have already been placed. Second, the soldiers placed afterwards can be placed anywhere without affecting the correctness of the previous soldiers' placements. A very concise implementation of this approach can be found in konqueror's solution here.

Value	1000
Submission Rate	57 / 395 (14.43%)
Success Rate	18 / 57 (31.58%)
High Score	jfguo for 792.10 points (15 mins 25 secs)
Average Score	536.73 (for 18 correct submissions)

Value	500
Submission Rate	248 / 349 (71.06%)
Success Rate	170 / 248 (68.55%)
High Score	Burunduk2 for 477.63 points (6 mins 12 secs)
Average Score	359.31 (for 170 correct submissions)

TC veterans read this problem, looked at the input constraints, and decided that it had to be a DP problem with 2¹⁶ states. And, indeed, it was. In this problem, let a state be a bitmask with 16 bits. Bit i of the number will be 1 if fence i has been used, and 0 otherwise. Our DP storage consists of keeping the greatest area that has been built with a given subset of fences. Note that for a given subset of fences, there are multiple ways that they can be broken into valid triangles: consider, for example, {2, 2, 2, 3, 3, 3}. This can be broken down into two equilateral triangles, or as a {2, 2, 3} triangle and a {2, 3, 3} triangle. However, the former arrangement is much better.

Now that we have our state representation, we need to come up with a relation between different states. Well, if you have used some subset of the fences, then to get to another valid state, pick three unused fences and make a triangle out of them, if you can. This was made much easier because the Notes section of the problem statement (you do read those, don't you?) gave the conditions under which a triangle was valid, as well as Heron's formula for the area of a triangle given its three side lengths.

So, the recurrence relation expressed in pseudocode:

  N = number of fences

  biggest_area(used_fences) {

    double best = 0;

    for i = 0 to (N - 1) {

      for j = (i + 1) to (N - 1) {

        for k = (j + 1) to (N - 1) {

          if used_fences contains {i, j, k} AND the three form a valid triangle {

            best = max(best, area(i,j,k) + recurrence[used_fences minus {i, j, k}])

          }

        }

      }

    }

    return best

  }

Note that this will automatically handle the base case, which is zero area for no fences used.

The last step of this puzzle is to save previously calculated results, or the solution will time out. It's probably easiest in this case to use memoization on the above recurrence simply by adding two lines: one to save the value of best at the end of the function, and one at the beginning of the function to check if the best value for the given used_fences set has already been calculated.

Value	1000
Submission Rate	76 / 349 (21.78%)
Success Rate	20 / 76 (26.32%)
High Score	Burunduk2 for 754.99 points (17 mins 24 secs)
Average Score	474.40 (for 20 correct submissions)

Boy, someone really sends a lot of SMS messages -- up to 10¹² of them per month! Picking the right set of plans could really save some money. But how?

Let's consider a simplification of the problem first. What if only one SMS package deal were available? If the deal costs at least ten cents per SMS, then it's not worth it to use the deal at all, so the optimal cost is then ten cents times the number of messages. Otherwise, the package deal is cheaper, so there are two possibilities. Let M be the number of messages you want to send, P the number of messages in the package, and C be the cost of the package. Then you either want to buy floor(M / P) packages, or floor(M / P) + 1. In the first case, you need to make up the difference, if any, by buying individual messages, and in the second case, you buy more messages than necessary. (Exercise for the reader: Why don't we have to consider any other cases?) These two cases can be checked in constant time to see which one costs less. So now we're done with our simplified problem, and can apply that to solving the harder version.

Now say we've selected a quantity N1 of package 1 to buy. This means that there are M - (N1 * P1) messages left to assign between package 2 and the default pricing. But this is exactly the problem we just solved! So all we have to do is loop through all possible quantities N1, from 0 to floor(N1 / P1) + 1, and for each, solve the easier version of the problem. Okay, great, we've got a solution! Code it up and it'll pass all the examples, and submit!

Wait a second. What were those input constraints again?

In the worst case here, there are 10¹² messages to send, and both packages can contain one message apiece. This won't run in time. Okay, back to the drawing board.

The thing to notice is that all but "a few" of the packages you buy will be of one type, and the rest will be divided between the other package and the standard per-message deal. So, try both packages as the one you buy "a few" of, and loop through all possible quantities of that package, up to a certain limit. Then, for each quantity of the package you buy, find the optimal solution using our previous procedure.

Combing through solutions that used this approach and that passed system testing, it seems that the smallest limit that worked was one million. For a clear implementation of this approach, see tgrbin's solution.

Other coders picked interesting ways to cut down on the search space: Petr (solution) simply bought a large number of the cheaper package before doing the exhaustive search, and HiltonLange (solution) used ternary search to reduce the search space to a more manageable level before iterating through all possible values. (Note that ternary search does not work by itself. Since the number of packages bought must be integers, the function that you are trying to minimize is not actually unimodal.)

In fact, this problem is an example of an integer programming problem, which is to optimize a cost function given some constraints, with all variable values required to be integers. In general, integer programming problems are undecidable, although in most situations they are "merely" NP-hard. This means that unless the problem has some special structure (which this does not) there is no way to avoid some amount of exhaustive search, although there are ways to remove sections of the search space that could not possibly contain the optimal result. This is a programming technique known as pruning, and is extremely useful when attempting to optimize brute force solutions -- it may even allow you to create a brute force solution to a problem which was not intended to have one!