KhaustovPavel's blog

By KhaustovPavel, 6 years ago, ,

424A - Squats

The problem is to find the number of standing hamsters. If it is less than half, we should make the required number of hamsters standing. Otherwise we should make some hamsters sitting.

424B - Megacity

We can sort all the cities by their distance to the Tomsk city di. After that we are to find the smallest index t for which the total population p0 + p1 + ... + pt >  = 106. In such case the answer is dt. We can sort all cities in O(NlogN) and find the value of t in O(N). Limits for N allow O(N2) sorting or any other O(N2) solution.

424C - Magic Formulas

Consider the following formulas:

Let . Lets compute the following function for each i (0 ≤ i ≤ n). One can do it in O(n) using .

Lets transform ci:

Also:

Thus:

That means, if n / i is odd, , otherwise — . ci can be computed in O(1), that's why the complexity of the whole solution — O(n).

424D - Biathlon Track

Due to the time limit for Java some of O(N4) solution got Accepted. The authors solution has complexity O(N3·logN). The main idea is to fix the top-border and bottom-border. Then, using some abstract data type, for each right-border we can find the most suitable left-border in O(logN) time. For example we can use set in C++ and its method lower_bound. For better understanding lets have a look at the following figure:

For such rectangle we fix the upper-border as row number 2 and bottom-border as row number 5. Also, we fix right-border as column number 6, and now we are to find some left-border. Now we can split the time value for any rectangle for two summands. One of them depends only on left-border and another one — on the right-border.

With the blue color the summand that depends only on the right-border is highlighted. With the red and yellow color — the other summand is highlighted. The red-colored value should be subtracted and the yellow-colored should be added. For any blue right-border's value we are to find the closest red-yellow left-border. That is the problem to be solved with the help of STL Set or any other similar abstract data type.

424E - Colored Jenga

A classical DP-problem on finding expected number.

Lets define some function F(S) for some state — the expected number of minutes to finish the game from this state. For each color we can compute the probability of showing this color by the simple formula , where c — the number of dice's faces of this color. Now we are to find the probability PL to stay in this state for the next minutes. That is the probabilty of showing black color plus the probabilities of showing colors with no blocks of that color to be removed from the tower. Now we can find the value via the following formula:

The only problem is to find how to encode the state. To reduce the number of states we can assume that there is only 18 different type of levels, but not 27. For better time-performance it is better to use hashing. The solution for this problem requires good understanding of DP and quite good implementing skills.

• +12

 » 6 years ago, # | ← Rev. 3 →   0 i have a different approach for problem B. binary search on (square of) the radius. and for a given radius, check if sum of all "neighbours" the circle encloses satisfies sum + s ≥ 106 or not. my AC solution: 6470353EDIT: my solution is , slightly more complex than author's . ;)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 duplicate post
 » 6 years ago, # |   -6 Problem A: "In one minute, Pasha can make some hamster ether sit down or stand up." I think in place of some you should use one. It cost me wrong answer during contest. Please look into the language ambiguities.Thanks!
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Sometimes it's better to look at samples first, especially for A div2. As I see, you was debugging it for ~30 minutes — don't do it with A div2) Start reading B after first two failed attempts. I did the same today, just because of stupid mistakes. After 20-minutes delay you will defenetly get accepted, even if statement will be written on esperanto.
 » 6 years ago, # |   +6 Can someone explain the logic behind 424C — Magic formulas?
•  » » 6 years ago, # ^ |   0 In my method, you can think about the associative property of xor and the cycle of modulo by some number~ ;)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +4 In my solution, I first xor all pi as P = p1^...^pn, and precompute a xor array X[1...n], where X[i] = 1^...^i. Next, for each k=1,...,n, compute Tk = (1%k)^...^(n%k). Note that if n = k*t + r, where 0 ≤ r ≤ k - 1, then in Tk, each value in {1,..,r} appears t+1 times, and each value in {r+1,...k-1} appears t times. That means we can compute Tk in O(1) time given precomputed Xs above. For odd t, Tk = (r + 1)^...^(k - 1) = X[r]^X[k - 1], and for even t, Tk = X[r]. And finally we can compute the ans in O(n) time. You can see my solution for details: http://codeforces.com/contest/424/submission/6466539
•  » » » 6 years ago, # ^ |   0 Thanks a lot :D BTW you made a typo there X[r]^X[n] should be X[r]^X[k-1]. Really awesome explanation thanks!! :D
•  » » » » 6 years ago, # ^ |   0 Thank for pointing out the typo. Fixed!
•  » » 6 years ago, # ^ |   +4
•  » » 6 years ago, # ^ |   0 here is a good explanation of logic behind 424 Div.2 problem C read this comment you will really like it.. and afterwards try to solve it yourself
 » 6 years ago, # |   0 424D — Biathlon Track Do you mean you can do binary search to find the most suitable left border? Do you assume the perimeter will monotonically grow as you increase any given side?
•  » » 6 years ago, # ^ |   0 He means you can use some data structure (e.g. set in C++) to find left border, which gives closest to given perimeter.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 ...
•  » » » 6 years ago, # ^ |   0 Never mind, I got it. Thanks.
•  » » » » 6 years ago, # ^ |   0 can you tell me what you know ? i have the same problem. :)
•  » » » » » 6 years ago, # ^ |   0 Can you speak Russian?
•  » » » » » » 6 years ago, # ^ |   0 I can, but I don't have Russian keyboard
•  » » » » 5 years ago, # ^ |   0 I have the same problem, please help me out. Or give me a link of a proper soln which uses set for finding the closest left-border.
 » 5 years ago, # | ← Rev. 2 →   0 Your data in 424D is not strong enough. There is some Wrong Code also get an Accept, such as 6472530. There are 2 data I highly recommend to add. 6 3 0 0 10 10 1 1 1 1 1 1 1 3 1 1 3 1 1 3 1 1 1 1 should output:1 1 6 3. 3 6 0 0 10 10 1 1 1 1 1 1 1 1 3 3 3 1 1 1 1 1 1 1 should output:1 1 3 6.
•  » » 5 years ago, # ^ |   0 can not agree more! the algorithm of binary search for this problem is wrong, but it can still get an accept.
 » 5 years ago, # |   0 Can someone please help me with Div2 Problem B.The judge shows WA for the sample test case while it runs fine on my computer. NOTE: printf("%.07Lf") does not works here but cout << fixed << setprecision(7) << R; works Why is this so? Here are my 2 submissions 9374428 and 9374522 Also it shows WA for my implementation using setprecision also.
 » 3 years ago, # | ← Rev. 2 →   0 Shouldn't the time complexity be mentioned in the Editorial? -_- i found the same solution for E but i couldn't calculate the complexity + i couldn't write a hash function for the grid which is TOTALLY missed in the editorial....... you didn't even explain the optimum way of playing which i assumed right without proof and came here looking for answers, some of these editorials need to be re-written by top competitors .....
 » 2 years ago, # |   0 I solved C Magic Formulas with partial sums technique . Any number in the range 1 to n which occurs odd number of times is xor ed with the p array .Submission
 » 21 month(s) ago, # | ← Rev. 3 →   0 For problem C:If n = 8, the remainders of (i = 1 to n) -> i%n: 0 1 1 1 1 1 1 1 -> i = 1 0 0 2 2 2 2 2 2 -> i = 2 0 1 0 3 3 3 3 3 -> i = 3 0 0 1 0 4 4 4 4 -> i = 4 0 1 2 1 0 5 5 5 -> i = 5 0 0 0 2 1 0 6 6 -> i = 6 0 1 1 3 2 1 0 7 -> i = 7 0 0 2 0 3 2 1 0 -> i = 8 You have to XOR all these numbers with ever Pi..Notice that in every column there is a segment of length i repeated (n/i) times..So each column consists of a segment of numbers from 0 to n-1 repeated n/i times and numbers from 1 to n%i .You can XOR all of these in O(1) -->The XOR sum of numbers from 1 to m equals: m if m%4 is 0 1 if m%4 is 1 m+1 if m%4 is 2 0 if m%4 is 3 From the above you can calculate the result: for i = 1 -> n: res ^= p ^ XOR sum of the repeated segments togther ^ XOR sum of the remaining part in the column.