Match Editorial

In division 1 liympanda took his first SRM victory, closely followed by Im2Good (one failed challenge from first place) and tomek. For a long time though it looked like ACRush would go home with the victory, but after failing one of the last system cases on the hard problem, he fell back. The problem set contained two fairly standard problems which caused little trouble for most reds and yellows, while the third problem stumped a lot of coders. There were also a lot of challenges, mainly time-outs on the medium problem.

Division 2 also saw a hard last problem that had many submissions but where few passed. First place was taken by Aesop thanks to a successful challenge, closely followed by first timers taral and dan19. A notable first timer was also the TCO "Pick Me" challenge winner davidyang, solving the first two problems and almost making it to division 1.

The Problems

Value	250
Submission Rate	378 / 449 (84.19%)
Success Rate	342 / 378 (90.48%)
High Score	chenll for 249.43 points (1 mins 21 secs)
Average Score	200.86 (for 342 correct submissions)

This is, obviously, a pure math problem. One way to solve the problem is to first convert the desired temperature t to a neutral scale where the freezing point is 0 and the boiling point is 1. That is, we scale down the range between boiling and freezing from b1-f1 to 1. Then we scale it up again, but this time from 1 to b2-f2. We end up with a one-liner:

return ((double) (t-f1) / (b1-f1)) * (b2-f2) + f2;

Value	500
Submission Rate	346 / 449 (77.06%)
Success Rate	253 / 346 (73.12%)
High Score	niebieski for 490.77 points (3 mins 54 secs)
Average Score	369.38 (for 253 correct submissions)

Value	250
Submission Rate	388 / 397 (97.73%)
Success Rate	361 / 388 (93.04%)
High Score	Petr for 249.50 points (1 mins 16 secs)
Average Score	223.16 (for 361 correct submissions)

Let fcnt and rcnt be the number of occupied columns and rows in the frontal and right projection, respectively (i.e. the number of 'x' in front and right).

It should be clear that the only cells that can be occupied are those lying on the intersections of the columns marked as occupied in the frontal projection and the rows marked as occupied in right projection. Basic combinatorics tells us that the total number of such intersections are fcnt * rcnt. Obviously all these cells can be occupied, so the maximum possible number of occupied cells is this product.

To find the minimum value, one should first realize that it must be at least the maximum of fcnt and rcnt, since we can actually see that many cells being occupied just by looking at the frontal and right projection. It turns out this value is the answer also. To see this, assume that the frontal projection tells us column 1, 3 and 6 are occupied, while the right projection tells us row 2 and 4 are occupied. If we let a cell on column 1 lie on row 2, and the cell on column 3 lie on row 4, the right projection picture is fulfilled, and we can place the cell in column 6 on either row 2 or 4.

Value	1000
Submission Rate	187 / 449 (41.65%)
Success Rate	8 / 187 (4.28%)
High Score	Ihsahn for 608.74 points (26 mins 42 secs)
Average Score	455.25 (for 8 correct submissions)

The reason this problem has such a low success rate was most likely because the examples in the problem statement were trivial and could be solved by any greedy algorithm. Greedy doesn't work however, since the order in which the particles collide does matter. Also, we can try all possible orderings of collisions since there are way too many permutations.

We can build a graph of the input, where each node corresponds to a particle. Let there be a directed edge from node x to node y if x can make y disappear. The key to solve the problem is to realize that all cycles in this graph can be merged. That is, if particle A can make B disappear, B can make C disappear and C can make A disappear, then we can treat particles A, B and C as just one particle. It's obvious that we can, at any time, let all particles except one in a cycle disappear. We can also make the entire merged particle disappear if some particle outside this merged particle can eliminate one of the particles inside the cycle.

There are many ways to merge all cycles in a directed graph. The fastest algorithm is to use two DFS searches to find all strongly connected components (see DmitryKorolev's solution for an implementation of this), even though using the Floyd-Warshall algorithm is faster to code.

When all cycles have been merged, we end up with a DAG (directed acyclic graph) where each node correspond to a particle or merged particles. The solution is then simply the number of root nodes in this DAG. The particles in these root nodes obviously can't disappear, but all other particles can. For instance, if a root node in the DAG contains merged particles, we can eliminate all of them except one. If an intermediate node in the DAG contains merged particles, we first eliminate all of them except the one particle that can be eliminated by a parent node in the DAG. See the writer's solution in the practice room for a clean implementation of this solution, using Floyd-Warshall.

Value	550
Submission Rate	311 / 397 (78.34%)
Success Rate	202 / 311 (64.95%)
High Score	Petr for 538.18 points (4 mins 13 secs)
Average Score	404.93 (for 202 correct submissions)

Let s be the input string concatenated. We will solve the problem by induction over the length of s; that is, we will first find the least number of partitions required to partition the first character of s, then the two first characters, then the three first characters etc.

Obviously, the number of partitions required to partition only the first character of s is 1, since a single character is always a palindrome. Now consider the general case: we want to find the least number of partitions required to partition the first k characters of s. By induction, we can assume we have already solved the problems for all lengths less than k. The idea is to find all palindromes in s ending at position k, and for each such partition check what the least number of partitions required for k would be if that palindrome was the last one.

Example: Let k be 8 and the first 8 characters of s be BACABABA. There are three palindromes ending at character 8, namely ABABA, ABA and A. Now consider each such palindrome as the last palindrome in a palindrome partition of the first 8 characters of s. The remainder of the string would then be BAC, BACAB and BACABAB, respectively. Since we, by induction, already know the optimal solutions for these strings (which happens to be 3, 1 and 3, respectively), we can deduce that the best final palindrome for k = 8 was ABA and that 2 partitions are required to partition the first 8 characters.

The approach above requires two nested for-loops: an outer loop looping k from 1 to the length of s, and an inner loop looping over all substrings in s ending at position k. This inner loop must also verify that the substring is indeed a palindrome, and this must be done very fast, since an O(n^3) algorithm ought to time out. We can solve this by precalculating all substrings in s that are palindromes. Then this check will be done in O(1), and the whole solution will run in O(n^2).

To precalculate the palindromes, let isPalin(x,y) be a function returning true if the substring in s starting at position x of length y is a palindrome. Obviously, if y is 1 the function always returns true, and if y is 2 the function returns true only if the x'th and x+1'th character of s are the same. For the general case, the function should return true if the x'th and x+y-1'th character are the same and isPalin(x+1,y-2) is true (a string is a palindrome if the first and the last character are identical and the characters in between form a palindrome).

See my solution for a fairly clean implementation of this

Value	1000
Submission Rate	37 / 397 (9.32%)
Success Rate	15 / 37 (40.54%)
High Score	Im2Good for 662.50 points (22 mins 53 secs)
Average Score	472.99 (for 15 correct submissions)

Logic puzzles similar to this problem often appear in magazines and elsewhere. There are many versions involving hats and people (usually prisoners) not seeing their own hat. The exact condition differs, but the solution ideas are often similar. Of course, since this is a programming problem, the whole procedure must be "mechanized", which can be quite a lot harder. The solution presented below is the approach taken by most coders. It's the perhaps most natural one, in that it tries to simulate the wizards' pondering.

Common knowledge among the wizards is the total number of hats of each color available. Let a hat configuration be a valid distribution of the hats among the wizards (where the input parameter hatsOnWizard is the configuration we're actually trying to find the answer for). The general solution idea is as follows:

As illustrated by the first example, for some hat configurations one wizard knows immediately the color of his hat. Since the wizards are perfect logicians, those hat configurations are known to everyone. If one of these configurations includes hatsOnWizard, we're done - (at least) one wizard will shout out the color of his hat. Otherwise all wizards know that the actual configuration is not one of these. From this a new set of hat configurations can be calculated for which some wizard will know the color of his hat. If hatsOnWizard include one of these configurations, we're done. Otherwise we keep on until we gather no new information. If the hatsOnWizard configuration has never appeared, no wizard will ever know the color of his hat.

An example of this idea will illustrate this: Let the total number of hats be (7 8 9) and the number of wizards 18 (this is the last example in the problem statement). If hatsOnWizard was (1 8 9), (7 2 9) or (7 8 3), some wizard would immediately know the color his hat. If this it not the case, then some other configurations will cause a wizard to know the color of his hat. Consider the configuration (2 7 9) for instance. A wizard with the first hat would think something like this: "Hmm, I see (1 7 9). I obviously can't have hat 3, since there are no more of those available. Can I have hat 2? Then the actual configuration would be (1 8 9). But that configuration has been ruled out, since someone would have known his hat already on the first question! Hence I must have hat 1." From this reasoning we can deduce that the configuration (2 7 9) is a configuration that would be solved in two questions. Other configurations that would be solved in two questions (with similar reasoning) are (2 8 8), (6 3 9), (7 3 8), (6 8 4) and (7 7 4). On the third question, the configuration (5 4 9) would be found, because here a wizard with the second hat would know he can't have hat 1 because that would yield the configuration (6 3 9), which was ruled out above.

In pseudo-code, this would look like this. For a somewhat clean implementation, see my solution in the practice room.

      // Let q[hatConfig] be the number of question required
      // for hatConfig to be found. Initialize to infinity
      currentQuestion = 1
      while true
         newInformationFound = false
         foreach hatConfig X in allHatConfigurations
            foreach hatColor Y
               // Let wizard with hat of color Y ponder
               possibilities = 0
               foreach potentialColor Z
                  let X' = configuration X minus color Y plus color Z
                  if X' is valid and q[X'] < currentQuestion
                     possibilities++
               if possibilities = 1 begin
                  q[X] = currentQuestion
                  newInformationFound = true
               end
            end foreach
         end foreach
         if q[hatsOnWizard] < infinity
            return q[hatsOnWizard]
         if newInformationFound == false
            return -1         
         currentQuestion++         
      end while
   

I choose to represent a hat configuration as an integer, allocating 4 bits for each hat color (since there would be no more than 15 hats of each color). This allows me to declare q as a simple array. It would probably also work to use an int[] and let q be a hash table.

Some performance considerations: In the code above, I loop over all valid hat configuration for each question. The total number of configuration could be roughly 16⁴, so if the number of question requires were a lot, this might take a time. It turns out that the system test never had a case requiring more than 13 question, so this is no problem. During the contest, I had no idea what the upper limit was, so instead of looping through all hat configurations each time, I only looped through those that were added in the last question (since those were the only ones providing new information).

However, there exist a much shorter solution to this problem though, which doesn't take hat configurations into account at all. During the limited time I had for this writeup I failed to understand why it works. See Mojito1's solution for a clean implementation of this approach.