There are many ways of solving this easiest problem of the contest. I list them in the order of increasing realization difficulty:

1. If you use C++. Take permutation (1, 2, ..., 9). Suppose elements 1-4 are numbers we're looking for. Use next_permutation() to generate all possible combinations of numbers and just check that all conditions are met.

2. Pure brute-force - just 4 nested for() cycles for each unknown number. Here one should not forget to check that all numbers are pairwise different. This takes additional 6 comparisons.

3. One may note that, given the first number in the left upper cell, one may restore rest of the numbers in O(1). So, just check 9 numbers in the first cell (let it be x), restore other numbers from the given conditions:

(x, a)

(b, c)

a = r1-x, b = c1-x, c = r2-b = r2-c1+x

and check that they all lie in [0..9] and rest of the conditions are met.

4. O(1) solution - one may derive it from the previous approach: since x+c = d1 => 2*x + r1 - c1 = d1 => x = (d1+c1-r1)/2

So, you find x, check that it is in [0..9], restore all other numbers as in the previous approach and check that all conditions are met.

This was purely technical problem. String type is the best way to store the number. The main steps to get this problem is just to follow problem statement on how a number in the financial format is stored:

1. Divide the number in the input into integer and fractional parts looking for position of the decimal point in the input number (if input number doesn't have decimal point - assume fractional part is empty string)

2. Insert commas into integer part. This is done with one for() / while() cycle

3. Truncate/add zeroes to length 2 in the fractional part

4. Form the answer [integer part].[fractional part]. If initial number had minus in the beginning - add brackets to both sides of the answer.

Due to quite low constraint this problem is easily solvable by brute-force. Without loss of generality assume that A <= B <= C. Then it is clear that A cannot exceed , and, given A, B cannot exceed . Then all solution is just two cycles:

for (long long a = 1; a*a*a <= n; ++a) if (n%a == 0){

for (long long b = a; b*b <= n/a; ++b) if ((n/a)%b == 0){

long long c = n/a/b;

...

}

}

Since we assumed A <= B <= C, now it is not clear which parameter (A, B or C) is the height of haystack, so inside the cycle one should consider all three possibilities. For any N <= 10^9 the code inside the second loop runs no more than 25000 times, so this solution fits timelimit even for N <= 10^11 and maybe larger. Why it's so quick? It's because of the fact that number of divisors of arbitrary number N does not exceed about . That's why all similar solutions and maybe some other streetmagic that has anything common with divisors of N, should get AC.

This problem was not on derivation of the general formula m*n - (m*n)/2 (only this would be too simple for the second/fourth problem, isn't it?) but rather on accurate investigation of several cases. Unfortunately, many participants were very eager to submit the formula above, that's why there were so many hacks. I would say: this is not jury fault - pretests were made very weak intentionally, partially - to give you some space for hacks; but jury didn't presume there would be so many hacks. This is your fault of submitting unproven solutions. This is large risk given Codeforces rules, and this time risk-lovers were not lucky =)

Ok, let's come to the solution. Without loss of generality let's assume m <= n. Then we have the following cases:

1. m = 1 x n fields. It is obvious that here the answer is n.

2. m = 2 x n >= 2 fields. Here the correct formula is 2*[2*(n/4) + min(n%4, 2)]. Why so? To see this draw the board for arbitrary n and draw all possible knight moves on it. In general, you'll see four not overlapping chains. Since you cannot place soldiers in the neighboring cells of any chain, then for a chain of length L the answer doesn't exceed (L - L/2). On the other hand, it is clear that the answer (L - L/2) is always possible since soldiers on different chains never hurt each other. If you consider fields with different remainders n%4, the formula above becomes clear.

3. m >= 3 x n >= 3 fields, except the cases 3 x 3, 3 x 5, 3 x 6 and 4 x 4. Here one may use general formula m*n - (m*n)/2. Why so? It is known (or becomes known with google) that for all such fields knight tours exists. Any knight tour is just a chain of lenght m*n, so by the logic above one cannot place more than m*n - (m*n)/2 soldiers on it. On the other hand, if one makes chessboard coloring of the field, it is clear that the answer above is always achievable if one chooses cells of one color as places for soldiers. So, formula above is proved.

4. Cases 3 x 3, 3 x 5, 3 x 6 and 4 x 4. Here we can't use the logic above to prove that the above formula is also right here. The easiest way is to verify it using brute-force or pen and paper. This concludes the solution.

This is technical problem, one may use several approaches to solve it. Additional complexity is to restore the answer after you got it.

1. Dynamic programming "on the broken profile" - I'll not explain the approach here in detail, you can find explanation of it on the Internet or even on Codeforces. Worth to point out, care should be taken of your code memory usage.

2. Search with memorization - one jury solution uses logic like DP with usual (not broken) profile: move by rows (or by columns), try all possible T placements such that upper cell of T's is in the given row and run the same search procedure for the next raw, passing the state of the two last filled rows of the board to it. For the given board state save the answer recursive function returned (max number of T's one may place on the not-yet-filled part of the board) and use it in the future as the answer for the given state. This requires only O(n*2^(2^m)) of memory and works about 2 sec. on maxtest 9 x 9.

3. Branch and bound. Another jury solution recursively tries all possible tilings of the board with T's. If on some step it occured that number of T's on the board plus number of T's one can theoretically place on the remaining part of the board doesn't exceed existing best answer - trim this node. Such solution is the easiest to code and it works only 0.5 sec. on maxtest, however it is not obvious from the very beginning.

4. Precalc - not to write a lot of code (applying DP or search with memorization) and not to deal with possible time/memory limits, some participants did the right thing: using the third approach, just precalculated answers for large (or for all possible) inputs.

Solving this problem involves two basic steps: firstly, to recognize that we have nothing else than generalised version of Nim and secondly, to solve it.

The first part is not difficult: assuming we don't have rows with soldiers of only one color (in which case the game usually becomes trivial, since one or both players may play infinitely long), let the number of cells between two soldiers in every non-empty line be the size of the corresponding piles in nim. Then attack according to the rules of the given game is the move in the corresponding nim that allows you to take as much as you like stones from at most k piles (but at least 1 stone should be taken). Such generalized nim is called Moore's nim-k, and we should solve it to find the winner in the initial game. As any source you may google (except Russian Wikipedia) shows, solution to the Moore's nim-k is the following:

Let's write binary expansions of pile sizes, and for any position check that sum of digits on the given position in all expansions is divisible by k+1. If this holds for all positions - then the winner is the second player, otherwise - the first player. Proof of the fact may be found here: http://www.stat.berkeley.edu/~peres/yuvalweb/gath9.pdf

Let's consider the following case for k = 2:

R-G--

R--G-

R---G

R---G

Corresponding 4-piles nim-2 for this test is (1, 2, 3, 3). After writing binary expansions of piles sizes we get

01

10

11

11

Sums of digits in both positions (3) are divisible by k+1=3, so here Second wins.

But this is still not full solution to the initial game, because we forget about retreat possibility. But it is simple here: only player losing the game in which only attacks allowed may want to retreat (winner just plays corresponding nim by attacking). But if loser retreats, winner just restores initial position attacking in the corresponding rows. And since loser cannot retreat infinitely, he cannot improve his win chances with retreat moves. That's it.

And finally, don't forget about tests like:

2 2 2

GG

RR

Answer: Second

All such tricky cases were in pretests.

This problem was "just" about finding the shortest path on a cone. Unfortunately, even though jury lowered precision requirements to 10^-6 and included all possible general cases in pretests, nobody tried it =(

For solution, let's consider all possible cases of two points on the cone surface (including its basement):

1. Both points on the basement. Here it is clear that Euclidean distance between points is the answer to our problem.

2. Both points on the lateral surface. One may think that optimal path is also always lies on the lateral surface. In this case it is easy to find length of an optimal path from geometric considerations (by considering loft of the lateral surface). But 10-th pretest disproves that it is always optimal:

100 100

99 0 1

-99 0 1

Answer: 202.828427124746210

So, optimal path may go through the basement. In this case it has two points that lie at the same time on the basement and on the lateral surface (let's call them A' and B'), so length of the path through this points is easy to find by adding length of the three different segments - AA', A'B' and B'B. So the problem is reduced to finding optimal positions of A' and B'? Let's assume that polar angle of the first point in XOY plane is a1 (0 <= a1 < 2*PI) and polar angle of the second point is a2 (0 <= a2 < 2*PI). Length of the shortest path between A and B passing through the points A' and B' (AA' + A'B' + B'B) is some function of two arguments that we want to minimize - f (a1, a2). One may minimize it using, for example, grid or any other suitable numerical approach.

3. One point on the basement and another point on the lateral surface. This case is similar to the previous one - optimal path passes some point C' on the "brink" whose optimal polar angle we are to find. In this case we optimize function of one argument g(polar angle(C')) = AC' + C'B.

1. tourist

2. PavelKunyavskiy

3. Egor

4. Fefer_Ivan

5. fhlasek

6. Coder

7. RAVEman

8. neal

9. WXYZ

10. whhone

1. vyvtjp643

2. songlj

3. t.gogniashvili

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.

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.

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.

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.

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.

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.

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.

Div. 1: 1000-1500-1500-1000-???

Div. 2: 500-500-1500-2000-2000

That's why I don't very like this contest. But, once again, problems were interesting, thanks to the author!

Now short editorial.

Problem A - Cableway (div. 2)

The only thing in this problem is to write expression for time of the arrival for final group of students of each color. This could be done with the following code:

Problem B - African crossword (div. 2)

Due to the small restrictions, the problem could be solved with the straightforward O(n*m*(n+m)) algo of finding for each symbol whether there is other such symbol in the corresponding row or column. More fast approach is to count for each symbol how many times it appears in any row/column, and do corresponding checks in O(1) instead.

Problem A (div. 1) / C (div. 2) - Robbery

Good problem, and I don't agree with scoring of 500 for div. 1, I think the optimal score for this problem is 1000. The idea is the following: if n is even, then the answer is 0. If n is odd, then the answer is min (mn, (m/(n/2+1))*k), where mn is the minimum number of diamonds in some odd cell i. Now let's explain this formula.

If n is even, then all cells may be divided into pairs, and sum in each pair should remain constant => sum in all cells should remain constant => Joe cannot steal anything!

If n is odd, suppose Joe managed to steal D diamonds before some check. Let's prove that he should rearrange diamonds in cells so that any odd cell now contains D diamonds less, and any even cell - D diamonds more. Why so? Consider any odd cell. Again, remaining cells could be divided into neighboring pairs (n/2 of them) such that sum in every pair should remain constant => if Joe has stolen D diamonds, cell that we consider (any odd cell) should contain D diamonds less after robbery! But this entails (since pairsums should remain constant) that even cells should contain D diamonds more now. So, thus we proved first part of the formula under min() - Joe cannot steal more diamond than there is at any odd cell. But this is not the only restriction. In each of the k turns he may perform not more than m operations. How to economize operations to steal more diamonds? Well, the minimum number of operations to steal 1 diamond is n/2+1 (try to think why), so in every turn Joe may steal not more than m/(n/2+1) diamonds, and since there are only k turns, we get second part of the formula under min() function at the beginning.

Problem B (div. 1) / D (div. 2) - Widget Library

Pretty straightforward realization. Things to remember are:

 - sizes of widgets can be as large as 100*2^30+

 - when evaluate sizes of widgets recursively, memorize answers that are already evaluated. Otherwise you will need up to 2^30+ operations to get answers

"Bad" tests are of the following type:

76

Widget a(100,100)

HBox b

b.pack(a)

b.pack(a)

HBox c

c.pack(b)

c.pack(b)

...

HBox z

z.pack(y)

z.pack(y)

Problem C (div. 1) / E (div. 2) - Chip Play

From test 1 it becomes clear that the game process is dependent on history, so any DP schemes will not work. So, we perform straightforward simulation: take every chip and go. But the following test shows that straightforward simulation can take O(n^3) time to finish:

1 5000

R(2500 times)L(2500 times)

Answer: 5000 2

To speed the process up, one can use linked lists to get next cell with chip in O(1). The more tricky and easy-to-write approach is in my solution. It fits in timelimit, unfortunately, I can't prove complexity easily: http://pastebin.com/3KB7s0Le

Problem D - Space mines (div. 1)

I can't understand why it's D. It's pretty straightforward, it's easy to write. The only thing to understand is that it cannot be the case when Death Star intersects some spike and doesn't intersect its endpoint. Why? Remember: radius the the Star is not less than radius of any mine, and length of each spike is at most 3/2 of radius of mine. Then show by yourself that the situation described above is improssible.

That's all! Now just find all times where Death Star touches mine surface or touches spike end and take minimum of those. Pretty easy (one quadratic equation), I think - on the level of problem A: http://pastebin.com/YCSAbju1

Problem E - Fire and Ice (div. 1)

Who can explain this to me?