SRM 579 - Disaster averted?

Yep I helped write the problem set this time.

I gave up trying to write div1 500s and div1 1000s. It has gotten a bit difficult to get things that are interesting and difficult enough for these slots. So I sent the admins some ideas for problems for the easier slots. Hoping that maybe there is a coder out there with the exact opposite issue - all his problems are too difficult for the easier slots.

UnlicensedPrimalCreatures

I thought of this one some time after playing a game. (Pro-tip: Spell Grez backwards). Seemed appropriate for div2 easy.

There are some creatures of different power levels. Your creature wants to defeat as many opponents as possible. A creature can only defeat creatures with a strictly smaller power level. When you defeat a creature, its power level divided by 2 is added to your own power level.

Just sort the creatures. If you make sure to always attack the weakest available creature until you cannot defeat anyone your power level will be maximum possible at the time you face any given creature. (If you face creature #i, you can assume you have already defeated all the creatures before).

UndoHistory

I dunno, I thought of this during a rush.

Initially UndoHistory = { "" }, Buffer = "", and contents = {}.

If you type a lowercase letter, then Buffer = Buffer + (the letter). And the new buffer is added to UndoHistory

If you press enter then Buffer is appended to contents[].

If you double click, you can do Buffer = (any element of UndoHistory)

You are given lines an array of strings. What is the minimum number of (key presses + mouse clicks) needed to make contents= lines ?

Let us say you are interested in typing the contents of the i-th element of lines, you can assume that all of the previous elements were also typed and added to contents. This means that all of the prefixes of each of the previous elements are in UndoHistory.

So we have two choices: a) Restore an element of UndoHistory (Always restore the one with the largest common prefix as lines[i]). And b) If the buffer is currently a prefix of lines[i], you can also continue typing. Note that there are times where even if b) is possible, it is still better to do a).

MarblePositioning

I proposed this problem for a previous SRM as a div2 hard. IT was rejected because it was too easy. So we tweaked that match's div1 250 into a problem that ended up being too hard. So now we prefer to try this "too easy" problem.

Given a list of up to 8 circles each with a given radius, line them up over a straight line so that the distance between the tangent point of the line and the left-most circle and the tangent point between the line and the right-most circle are as small as possible. You can place the circles in any order and they should not overlap.

A classical problem, since 8 is very low, we can try any permutation, what is left is to find the minimum distance given the chosen order.

Place the first circle, there is no condition to follow, so just place it at position 0.

Then whenever you place circle i, find the minimum position larger than 0 at which you can place the circle without overlap. This means that it should not overlap with any of the previous circles. For each of the previous circles, you can find the minimum positions at which circle i can be placed without overlap. The maximum of all these values is the new position for i.

Given two circles of radius r1 and r2, the minimum distance between the tangent points should be one such that the distance between the centers is exactly r1 + r2. The centers are located at (0, r1) and ( min_dist, r2). So you only need to solve an equation. The result is 2*sqrt(r1* r2).

TravellingPurchasingMan

I wrote this problem aeons ago. We even developed it and test cases. But we decided that it was too easy/not interesting enough for division 1 500 and put another problem instead.

This week, when I was offered the chance to write most of the problems of SRM 579, because someone else (Turns out it was ir5) had a div1 hard but no easier problems. We didn't have a div1 500. On Wednesday, I thought of a problem that seemed *WONDERFUL*. It was a lovely little problem with a interesting solution. However, just last night we found out that the interesting solution was wrong. There was still another interesting solution, but it would have been too hard for div1 medium. So with less than 16 hours before the contest, we had no viable div1 medium.

I remembered about TravellingPurchasingMan. It is very easy, but at least it exists - However, we had to spend the last 4 hours tweaking this problem so that it is not awful. It initially had 14 interesting stores. But since the problem was looking too easy we increased it to 16. It also had a much more complicated input format that required far more parsing. It was too annoying so we had to work into removing all that mess.

The solution is a strange dynamic programming one.

Edit: I regret nothing. And no, this is not a "standard TSP by dp", you still need to figure out that edges depend on the minimum time of your current vertex. And just because this extra step is trivial for you, it does not necessarily mean it was trivial for everyone (And the submission rate suggests it wasn't). Let me be frank: Not all div1 500s have to be made with the high level yellows and reds in mind. Quite honestly, we are sick of you guys being the only ones that solve more than one problems. If you could solve this problem easily, then great news! At least this time you had time to try and solve div1 1000; And since you are so good, I bet you solved it, right?. Meanwhile, at least more coders in the blue and mid to low yellow were able to enjoy more than *ONE* problem in a TopCoder match.

Also, it was either this problem or an alternate version of the marbles div2 hard with n<=10 we didn't have many choices, you know.