goryinyich's blog

By goryinyich, 12 years ago,
Hi there!

Here is editorial for the round #78.
Russian editorial will be published a bit later - I supposed that there are more people who can understand English (or who can do English -> Russian web page translation) than vice versa.

Again, I'm very sorry for the situation with problem B (div. 1) / D (div. 2). Also, I'm sorry that I underestimated difficulty of the problems. At least, I hope the problems appeared interesting for many contestants.

Problem A (div. 2) - Help Far Away Kingdom
Here the problem was to round a number up according to the usual mathematical rules with the exception that if the last digit of integer part is equal to 9, you should output "GOTO Vasilisa.". One may notice that to check whether number's fractional part is not less than 0.5 only one digit just after the decimal point should be analysed. If it is '5' or greater - add one to the last digit of the integer part, and the problem is solved. Probably, the simplest way to deal with the input data was using of the string variables.

Problem B (div. 2) - Help Chef Gerasim
The problem was to accurately check what is required in the problem statement. First of all, check whether all volumes in the input are equal. In this case output "Exemplary pages.". Otherwise find two cups with largest and smallest volumes. Suppose their numbers are a and b, and their volumes are v[a] and v[b]. Now suppose that before pouring their volumes were equal to V. Then they contained 2V units of juice before (and after) pouring. So, you need to check whether (v[a] + v[b]) is divisible by 2. If this is not so - output "Unrecoverable confihuration.". Otherwise assign to the cups presumable old volume v[a] = v[b] = (v[a] + v[b])/2. Now if only one pouring have been made, volumes of juice in all cups should be equal, and you print corresponding message "... ml. from ... to ...". If volumes are not equal, print "Unrecoverable configuration" instead.

Problem A (div. 1) / C (div. 2) - Help Victoria the Wise
In this problem you were required to find the number of sufficiently different colorings of a cube faces with predefined six colors. The most trivial solution is to introduce some ordering of the cube faces (say, 0 - front, 1 - back, 2 - up, 3 - down, 4 - left, 5 - right), then consider 720 = 6! arrangements of colors over these 6 faces. Each arrangement is some permutation of characters from the input. For each arrangement we find all its 24 rotations - and get 24 strings. Lexicographically smallest string will be representative of this coloring. The answer is the number of different representatives.

Problem B (div. 1) / D (div. 2) - Help King
Unfortunately, initial author's solution for this problem appeared wrong. However, the optimality of the below algo was proved by Knuth and Yao in 1976. Limitation for n in the problem now changed to 10000.
The process of tossing a coin and making decisions regarding which alternative to choose may be naturally described as drawing some (possibly infinite) binary tree. Each toss "draws" two new branches from every free node of the tree (initially the tree consists of one free node). Whenever the number of free nodes becomes >= n, you turn n free nodes into leaves (onle leaf for each alternative), and proceed with the other free nodes in a similar way. For example, for n == 3 we get the following infitite tree:
o
/      \
o          o
/     \      /     \
1        2  3        o
/      \
...      ...
Now we should evaluate expected length of a random path in this infinite tree now. One may notice that the tree is recursive: since the number of free nodes at every level is strictly less than n, the situation will repeat after maximum of n steps. Once one notices this, it is not so hard to derive formulas for the answer. Since numbers in the answer could be of the order 2^n, one needs to write "long arithmetics", or use Java.BigInteger.

Problem C (div. 1) / E (div. 2) - Help Greg the Dwarf
For this problem I assumed numerical solution. But there are several cases to consider. Below without loss of generality we assume a <= b.
1. l <= a <= b. In this case the answer is restricted by the length of the coffin, so the answer is l and it is clear that the coffin l x l can be brought through the corridor (a, b) - let's denote corridor's sizes in this way.
2. a < l <= b. In this case the answer is a, and it is clear that no larger number can be an answer. Indeed, otherwise the coffin (w > a) x (l > a) is impossible to drag through the corridor (a, b).
3. a <= b < l. This is the most general case, where we should rotate the coffin inside the corridor where it has a kink. To maximise the width of the coffin, we want to move it in such a way that one corner of the coffin touches one outer wall of the corridor (suppose bottommost on the picture), and another corner adjacent to the same long side of the coffin touches another outer wall of the corridor (leftmost on the picture). Let's introduce coordinate system in such a way that bottommost wall be OX axis, and leftmost wall - OY axis. Suppose that during the "rotation" process one corner of the coffin is at the point (x,0) (0 <= x <= l), then another corner should be at the point (0,sqrt(l*l-x*x)). And the answer we search for is min {distance from the segment (x,0) - (0,sqrt(l*l-x*x)) to the point (a,b) }, where you take min{} over all 0 <= x <= l. Let this distance at point x be f(x). Since f(x*) is minimal in some point x* and increases everywere to the left and to the right from x*, one may use ternary search to find its minimum.
Exact solution for this problem is also possible: you can reduce the problem to minimizing the dot product of the vectors (a-x,b) and (-x,sqrt(l*l-x*x)) over x. But this leads to the neccessity to find the roots of the fourth-degree polynomial, which is not the best idea during the contest.

Problem D (div. 1) - Help Monks
This problem was about famous puzzle "Hanoi towers", but diameters of some discs might be equal. How to solve that? A good thing to do is to write BFS solution to check optimality of your ideas for small inputs (by the way, BSF works quickly for almost all towers that have up to 10 discs) and then try to create an algo which solves the puzzle in an optimal way.
Let C (x1, x2, ..., xn) be a solution (under "solution" here we mean optimal number of moves - the moves itself is easy to get with one recursive procedure; also "solution" is the number of moves to move group of discs from one peg to any other (and not some particular) ) to the puzzle when we have a puzzle with x1 equal largest discs, x2 equal second largest discs and so on. And let U (x1, x2, ..., xn) be a solution to the puzzle when you are allowed not to save the order of the discs (you should still follow the restriction of the initial puzzle not to put larger discs onto the smaller ones, but at the end discs of the same diameter may be in any order).
Then one of the optimal solutions to the problem is the following:
C (x1, x2, ..., xn) = U (x1, x2, ..., xn) if x1 = 1 (*)
C (x1, x2, ..., xn) = 2*x1 - 1 if n = 1 (**)
C (x1, x2, ..., xn) = U (x2, ..., xn) + x1 + U (x2, ..., xn) + x1 + C (x2, ..., xn). (***)
U (x1, x2, ..., xn) = U (x2, ..., xn) + x1 + U (x2, ..., xn) (****)
Why so? One can notice that U() is "almost" solution for our problem: it "flips" order of the bottommost group of equal discs, the order of the rest of the discs remains the same! (try to understand why)
That's why (*) is correct.
The (**) is quite obvious.
The (***) does the following: move (x2, ..., xn) from peg 1 to peg 2 without saving the order. Then move x1 equal discs from peg 1 to peg 3, then move (x2, ..., xn) from peg 2 to peg 1 without saving the order (but it occurs that after we apply U() to the same group of discs twice, the order restored!), then move x1 equal discs from peg 3 to peg 2, and then use C() to move (x2, ..., xn) from peg 1 to peg 2 (here we use C() since we should preserve the order). So, (***) is correct.
And (****) is quite straightforward expression for U(): move all discs but the largest group with the same algo, then move largest discs (that's why if x1 > 1, the group of discs "flips"), and then move all discs but the largest group onto the same peg with x1.

Problem E (div. 1) - Help Shrek and Donkey
This problem was about optimally playing this simple-at-first-glance game. The key thing to recognize in the statement was that it is not always optimal to name card which you don't have. Sometimes it is optimal to confuse the opponent by naming card which you have on hand. In this case... yes, he may think that the card you named is card on the table and lose during the next turn. Now the problem is to understand when to use the strategy of reduction of opponent's cards, when to bluff in the abovementioned sense and when to try to determine which card is on the table. But instead of "when" the right question is "how frequently" since we have nothing else but usual constant-sum matrix game, and optimal strategy is the mixture of these three. Let's construct a matrix first. Player 1 has three pure strategies: "playing" (when he plays the game and really tries to determine opponent's cards and card on the table), "guessing" (when he guesses which card is lying on the table) and "bluffing" (when he tries to confuse his opponent to force him to lose by naming card in his own hand). In turn, if the first player used "bluffing" strategy, or during the "playing" strategy named card on the table, his opponent has two strategies: "check" (i.e. to believe the first player that he doesn't own the card he named and guess it as the card on the table) and "move on" (i.e. to decide that it was a "bluffing" strategy and the game should be continued, but with notice that the first player has named card on hands). Let's denote P(m,n) probability to win the game when the first player has m cards and the second player has n cards. Then P(m,n) is the value of the matrix game with the following matrix (rows - strategies of the first player, two numbers in the rows - probabilities to win when the second player uses strategies "check" and "move on" correspondingly:

"check"                                    "move on"
"playing"        n/(n+1)*(1-P(n-1,m))        1/(n+1) + n/(n+1)*(1-P(n-1,m))
"guessing"                 1/(n+1)                                     1/(n+1)
"bluffing"                       1                                       1-P(n,m-1)

How to get these numbers in the matrix? Consider the first row: "playing" strategy of the first player, "check" strategy of the second. First just names one of the n+1 cards. With probability 1/(n+1) he names card on the table, seconds checks it and wins (so, probability to with for the first is 0), with probability n/(n+1) the first names one of the cards on hands of the second player, so the game continues, second wins with prob. P(n-1,m) in this case. Then the overall probability for the first to win with such combination of pure strategies is n/(n+1)*(1-P(n-1,m)). In the same manner we fill other cells of the matrix. Finally we solve the game (this can be done straightforwardly, or with one formula if one notices that the "guessing" strategy is suboptimal everywhere when m>=1 and n>=1 and that the game doesn't have saddle points) and get answer to the problem - P(m,n).
And the last thing to note: when m==0 it is clear that during his move the second wins, so the first should guess, and P(0,n) = 1/(n+1). When n==0 P(m,0)==1 sinse we just do one rightguessing.
• +47

| Write comment?
 12 years ago, # | ← Rev. 2 →   0 For problem B (div2) you can simplify things by sortingthen the condition: "volume[1] == volume[N]" means: "volume[1]==volume[2]==volume[3]== ... volume[N]"If that's true then all volumes are equal.If it isn't true, try to normalize volume[1] with volume[N] and check volume[2] == volume[N-1]Just pay attention at tests with small N
 12 years ago, # |   +6 I think my solution for Div-2 B problem is slightly simplier and more understandable than author's one. I just calculated mean of all volumes and check if exactly two cups contain different volume. Here's my code: http://pastebin.com/YNxpK7DV.
 12 years ago, # |   0 in problem C
,after 6! factorial arrangement how i can figure out the 24 rotations for each lexicographical arrangement.I am very weak at visualizing cubes symmetry.can anyone help?thanks in advance.
•  12 years ago, # ^ |   +3 Suppose the faces on the cube are fixed.For each rotation, we can choose which face to be the "top" face. (6 choices)Once you choose the top face, the "bottom" face is fixed.Then, for the "side" faces, there are 4 possible arrangements - namely, rotating the cube along the axis passing through the center of the top face and that of the bottom face, by 0, 90, 180, or 270 degrees. (4 choices)So, these are the    6 x 4 = 24rotations.(Each possible rotation is determined by identifying the top face, and how you perform the 2nd rotation.)
•  12 years ago, # ^ |   -11 (Each possible rotation is determined by identifying the top face, and how you perform the 2nd rotation.)what do you mean by that?can you please explain?
•  12 years ago, # ^ |   0 Imagine a standard dice with faces numbered from 1 to 6, then take the dice  and rotate it in such a way until you have brought the number "1" to the top...Look at this: http://www.freeclipartnow.com/d/36259-1/dice.jpgYou want to put "1" where (in the link above) there is a "6", ok?Well, now you have 4 rotations of the dice having "1" on the top, right?Each of these 4 rotations is a candidate.Now the algorithm: try to put 1,2,3,4,5,6 on the top, and for each choice make a copy of the dice and rotate this copy in the 4 ways described above.You have made 6*4 = 24 rotations
•  12 years ago, # ^ |   -8 when I choose one face how can I determine the bottom face?
•  12 years ago, # ^ |   0 Well, I think you're a bit confused about what are fixed and what are not fixed.The statement actually writes: two dices, A and B, are defined to be equivalent, if you can (3D-) rotate A in some way, such that A and B looks the same from any viewing angle. And it turns out that, there are 24 ways to rotate A. (see my previous comment)(*) Imagine now you have a particular dice, A, and now that its six faces are already printed with some fixed colors. You wish to know this dice A is equivalent to which of the remaining 6! - 1 dices. Actually, what you need to do is to rotate dice A using the aforementioned 24 ways, and check against the remaining 6! - 1 dices, to see if A and B matches.And you do this checking (*) for each of the 6! dice A.
•  12 years ago, # ^ |   0 Thanks.
 12 years ago, # | ← Rev. 2 →   +5 Hi!i know why the algorithm for D(div1) which you are explain in editorial is correct , but i don't know why it's minimum?please give me some idea to prove it!thanks for your nice contest!
 » 3 years ago, # |   0 The answer for the DIV2 C question is the same as number of stereoisomers , of different types
 » 2 years ago, # | ← Rev. 2 →   +8 deleted