Monday, August 21, 2006 Match summaryThis match proved to be harder then usual. While almost all participants successfully solved the 250 problem, the other two problems appeared to be quite difficult. Nevertheless, YuJieLu, a newcomer from China, won the match with the fastest times on the 550 and 950 problems, and an amazing nine successful challenges. He was followed by his Chinese fellows ahyangyi, hupo001, wintokk, and Weiqi. lexgas from Romania, in third place, was the only European in the top six.The ProblemsIndictDatesUsed as: Division One  Level One: The straightforward approach to solving this problem is to simulate the process described in the problem statement. Let's start at year one and iterate years until we reach one with given indict, circle to the Sun and circle to the Moon. But if you want to win the Shortest250Competition, so popular at the TopCoder forums, you should use another approach, based on the Chinese remainder theorem. Note, that since 15, 19 and 28 are coprime numbers, the Indict system establishes the onetoone correspondence between years in range from 1 to 15*19*28 = 7980 and its indict notation. Let inv(a, b) be such an integer c, that ac mod b = 1. Consider the expression: Y = inv(28*19, 15)*28*19*(indict1) + inv(15*19, 28)*15*19*(circleSun1) + inv(28*15, 19)*28*15*(circleMoon1) Note, that Y mod 7980 = indict1, Y mod 7980 = circleSun  1 and Y mod 7980 = circleMoon  1. In this case (Y mod 7980) + 1 is the answer for the problem. It's easy to see that inv(28*19, 15) = 13, inv(15*19, 28) = 17 and inv(28*15, 19) = 10. Being simplified, it gives us a beautiful solution: struct IndictDates{DistinctDice Used as: Division One  Level Two:
Fisrt of all let's enumerate die's sides in the order they are mentioned in the problem statement: The first task we need to fulfill is to learn how to rotate the die. You need some imagination to see that we can carry out any rotation of the die by combining only two basic rotations, shown on the figure below. Since we have enumerated the die's sides, let's represent each of these rotations as a permutation. The i'th element of the permutation will be the side that will appear at the position i after applying the rotation. In this case, rotateRight = {2, 3, 1, 0, 4, 5} and rotateBack = {4, 5, 2, 3, 1, 0}. Let's implement the ApplyRotation procedure, that takes string die and int[] permutation and applies the rotation of the die according to the permutation. The pseudocode follows: string ApplyRotation(string die, int[] permutation){Now, for each die, let's apply all possible rotations and select one with the lexicographically first notation. Let's call such a notation a normal form of the die. In this case, we can compare any two dice by their normal forms. Now the pseudocode of the solution looks as follows: int getDistinct( string[] givenDice ){Finally, we need to implement the normalForm procedure. Notice that the die's positon is unambiguously determined by it's front side and top side. (In this case, any die can occupy at most 6*4 = 24 different positions.) To generate all the rotations, we need to set each side of the die as it's front side and then apply rotateRight 4 times. Let's see the pseudocode: string normalForm(string die){At last, here is the fourRightRotations function, which applies right rotation four times and returns the lexicographically first among them: string fourRightRotations(string die){Another approach of recursive generation of the rotations was used by YuJieLu. See his solution for the details. Dragon Used as: Division One  Level Three:
In this problem we need to use dynamic programming twice (read this tutorial if you are unfamiliar with it). To compute the probability of the knights' win, we need to predict the dragon's behavior. To do this, we need to know when it is worthwhile for the dragon to attack and when it is better to skip and hide in the cave. At first, for all possible amounts of knights and dragon's heads that may appear after dragon's turn, let's determine the probability of knight's victory. Let K[i][j] be the probability of victory of i knights over jheaded dragon. This is quite simple  see the following pseudocode: for i = 0 to k do K[i][0] = 1.0;Now all we need is for each configuration to decide if it is profitable for the dragon to atack the knights. Let's define D[a][b] as the probability of the knights' win if the aheaded dragon faces b knights (and the dragon still may attack). In this case the dragon has two options. First, he can skip and knights will win with probability K[a][b]. Otherwise, with probability of probDragon he will kill a knight or loose one head otherwise. In the first case knights will win with probability of D[a][b  1], and in the second their win will occur with probability of D[a  1][b]. This means, the cumulative probability of their win is Pab = (probDragon* D[a][b  1] + (1  probDragon) * D[a  1][b]). Therefore, the dragon will attack only if Pab will be smaller than K[a][b], since he wants to minimize the knights' chances to win. The following pseudocode calculates D[i][j]'s (the answer to our problem is D[heads][knights]): for i = 1 to k doYou can also see Burunduk2's solution for a clear implementation of this approach. As an implementation detail, you can solve the problem with only one twodimensional array. To do this you need to store values of D[i][j] in the array K[i][j], overwriting corresponding values of K[i][j] (clearly, the answer to our problem will be K[heads][knights]): for i = 1 to k do 
