goryinyich's blog

By goryinyich, 8 years ago, In English,
This is initial version only. TeX-style and Russian version will appear soon.

Problem A (div. 2) - Help Vasilisa the Wise 2

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.


Problem B (div. 2) - Help Kingdom of Far Far Away 2

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.


Problem A (div. 1) / C (div. 2) - Help Farmer

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.


Problem B (div. 1) / D (div. 2) - Help General

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.


Problem C (div. 1) / E (div. 2) - Help Caretaker

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.


Problem D (div. 1) - Help Donkey and Shrek 2

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.


Problem E (div. 1) - Help Greg the Dwarf 2

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.
 
 
 
 
  • Vote: I like it
  • +36
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it
In problem B (div. 1) / D (div. 2) for the case N > 2 && M > 2 we have formula (N*M + 1)/2.
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Ja~
    Color the matrix with black&white contiguously, then the answer=max(number of black,number of white)=(n*m+1) div 2.
»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please give me some resource (problem/discussion) on dynamic programming on "broken profile" ? I tried to google for it, couldn't find anything.

BTW, is it bitmasking?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think it is dp[n][mask1][mask2], where n is number of last filled row, and mask1, mask2 - bitmasks of two last filled rows

    See next comment

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 4   Vote: I like it +14 Vote: I do not like it

      Not exactly. This is usual DP by profile (not broken), so it probably'll get TLE if you don't use precalc. "By broken profile" is when you store the state of the last 2*m+1 cells, e.g. picture like (where # denotes cells for which you save their state):

      ------
      --####
      ######
      ###---

      This allows to consider only few transitions from previous states to the given state, and works much faster.
      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        In this problem we can use DP with usual (not broken) profile, without any precalc. Look for example at my solution. Time 440 ms. Memory 64 Mb.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    There is a little information for DP with broken profile in internet. This is my solution that i have wrote on contest http://codeforces.ru/contest/142/submission/1038015. Unfortunately in my code a lot of copypaste, so it's very large, but you can understand it.
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I am facing confusion about this 142D - Help Shrek and Donkey 2 From the editorial I understood that the answer will be "First" for the following input. But I could not make the First person win manually. Could anyone please tell the steps to win for the "First" person or I have wrong understanding. Here is the input:

2 6 1
G--R--
G----R
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the problem C Div 2 . i got this equation for getting the maximum value max = 3LL * 3LL * (n + 1) — n; and it is worked correctly as i don't know why ? also for the getting three values of a, b, c why did we start with this particular assumption that all values of a * a * a <= N; for example 27 = 9 * 3 * 1 as 9 (a) 9 * 9 * 9 > n. is it fact or something like that ? although the problem was accepted i would fully know why :) thanks

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

upd: sorry.. I understand now..

[del]Should this answer be Draw?[/del]

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this pdf link given for problem D (div-1) cannot be accessed. what to do?