### rng_58's blog

By rng_58, history, 8 years ago,

Let's discuss problems.

How to solve 8? I have no idea at all and finally decided to believe that we don't need nested addition/subtraction blocks, but it got WA. It seems there are harder cases.

How to solve 12? Essentially it reduces to the following: you are given a circle C and a point P. Find the movement of a point on C whose angular velocity is proportional to the distance from P. Is numerical integration accurate enough?

• +53

 » 8 years ago, # |   +34 8 is solved with precalc. Basically store all possible sets which you can reach in k moves and do all possible moves from each of them. With n up to 1000 answer doesn't exceed 8, and the whole backtrack works in a few minutes.P.S. I didn't get Accepted and don't know if my solution is basically correct (forgot to add input.txt/output.txt while submitting the output in the very last minute), but the same solution by Endagorion was accepted.
 » 8 years ago, # |   +21 How to solve 1? I have and get TL 31.
•  » » 8 years ago, # ^ |   +56 dp[type][n][k1][k2] — type is either 0 (segment hasn't started), 1 (segment is open now) or 2 (segment has already closed). k1 — number of elements that we swapped in the segment, k2 — number of elements that we swapped out of the segment. answer is in dp[1][n][i][i] or dp[2][n][i][i]
•  » » » 8 years ago, # ^ |   0 Can you show your code, please?
•  » » 8 years ago, # ^ |   +11 The same complexity we have accepted in upsolving. We got TL31 when doing k4 instead of k3.
•  » » 8 years ago, # ^ | ← Rev. 3 →   +3 Our solution on 1:Let us have an arbitrary segment [l, r] and two sets (multisets, but then we add to every number an index of it in order to recover necessary swaps for answer) of numbers on [l, r] segment: one set is for numbers inside the segment, one is for the outside numbers. Then we can easily get a sum with swaps on [l, r]: using prefix-sums (or whatever to get an actual sum) on a [l, r], then simultaneously iterate over k biggest numbers (from biggest to lowest) in outside and smallest in inside (from smallest to biggest) sets, and change our computed sum according to these values (will the sum get bigger, if we swap those values?).The solution is just to move two pointers over an array, while sustaining two sets accordingly and update answer if necessary.Does anyone know what is wrong with this approach? We've got WA8 or something with that.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +3 Function ans(l, r) with fixed l isn't monotonic on [l, roptimal].As far as I understand, your solution will fail this test:5 01 1 -1 1 1Here ans(1, 3) < ans(1, 2) < ans(1, 5)
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 We move r pointer until ans(l, r) becomes negative (I think it is obvious why should we look after negative sum, but I could be wrong) — than we set l = r and go on.My solution produces 3 0 1 5 on your test-case.
•  » » » » » 8 years ago, # ^ |   +3 6 11 -1 -1 2 2 -5Optimal answer is segment [3, 5] or [2, 4] with negative number swapped out. On the other hand, ans(1, r) isn't negative for r < 6. So your solution will skip segments with l = 3 and l = 4.
•  » » » » » » 8 years ago, # ^ |   0 Oh, right, many thanks for an explanation!
 » 8 years ago, # | ← Rev. 2 →   +28 8 can be solved with bruteforce with pruning from fixed starting set of powers of 2 in less than 100ms.
 » 8 years ago, # |   +3 I am also interested in solution for Problem 12. I tried to solve it and I think I did everythin right, but the output numbers were a bit different from the example output. I have no idea on what went wrong, looks like some kind of computational error. Here is my code. If you want I can explain it, but actually it is not the right solution. If someone can explain how to solve this problem, I would appreciate that.
•  » » 8 years ago, # ^ |   +8 It's not true, that angle speed is equal all time. You losses part of speed v to go along line.
•  » » » 8 years ago, # ^ |   +8 Oh, I got your point, thanks! And thank you for explanation below.
 » 8 years ago, # | ← Rev. 8 →   +18 In 12 i got ok with following.Let φ(t) be the angle you are talking about (counted from vector u as zero).Then .Now, we can get time ti when . It's can be calculated as Now, if we get time t, φ(t) is close enough to , where k is smallest where tk > t (we should shift t to range [0, tM] before this).With M = 3·107 it gets OK in YandexContest.
•  » » 8 years ago, # ^ |   0 Can you please explain a little bit more?
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +8 Which part? When we know, how to get derivative from angle, it's just numerical solving of differential equation.To get equestion, we considering x(t) = x0 + ux * t + r * cos(φ(t)), y(t) = y0 + ux * t + r * sin(φ(t)) (this is because distance is constant), and just simplify x'(t)2 + y'(t)2 = v2 (which is condition given in statment). This is square equation on φ'(t), which gives forumla above. I don't really ready print all counting here.
•  » » » » 8 years ago, # ^ |   0 Thanks, it is much clear now. Quite interesting to see stepping on perimeter instead of time. Although from mathematical point of view, it is more sensible to step on perimeter (otherwise, big step != circle).
•  » » » » » 8 years ago, # ^ |   0 Well, i got TL2, tring to step on perimeter. We have derivatives which are not to small, and not to big, so probably both have same order of error. And i didn't make more precise analisis.
 » 8 years ago, # |   0 Can you give me a hint for 5 and 10? Thanks!
•  » » 8 years ago, # ^ | ← Rev. 2 →   +6 10) Let's try to make a horizontal line (vertical one can be done similarly). Suppose, we will make a line at y = Y. Then we know the total amount of movements to bring all the points to y = Y (which is sum of |Y — yi|). Movement of x is independent of y movement. So we can minimize x/y independently. To minimize sum of |Y — yi| we should choose median(yi).Now, let's calculate movement of x. Sort all x. It is okay to say that, x0 will be leftmost, then x1, then x2 ... Say xi moves to x = i. Then signed movement is: set(xi — i). Let, xm = median(set(xi — i)). Then, you have to move: xi to i — xm. Why? Can be proved, can't find are simpler argument now.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 5) I got tle by suffix array. Later got ac using hashing+bitset. For each word, I converted the word to lower case and computed hash value (some simple polynomial hash). Also I kept a bitset consisting of 0 for lower case, 1 for upper case (AbaC = 1001) Then for each (word, query) I checked if they satisfy all the conditions (length equal, hash same, count of ON bits in xor of bitset <= K).
•  » » » 8 years ago, # ^ |   0 There's no need in hashing — u can jsut sort input and find words which are same in lowerace with query via binsearch
•  » » » » 8 years ago, # ^ |   0 map
•  » » » » » 8 years ago, # ^ |   0 gr8 m8
 » 8 years ago, # |   0 Could somebody send screenshot of top-10 results of the teams that are not currently in opencup table?
•  » » 8 years ago, # ^ |   +13
 » 8 years ago, # |   +11 For multiplier problem, the minimal case when nested blocks are necessary is N = 22 (test #5): Picture
 » 8 years ago, # |   0 Does anyone have tests for problem 4 that can help with WA2?
•  » » 8 years ago, # ^ |   0 When I had WA2 these tests were useful: 2 0 0 0 0 2 0 1 1 3 1 answer 1 1 2 1 0 1 1 and 5 0 0 0 0 0 1 0 1 0 2 0 2 2 2 0 1 10 1 5 3 5 5 answer 1 2 2 5 1 5 3 
•  » » 8 years ago, # ^ |   +10 This input should help you: 16 3 2 3 1 3 -1 3 -1 5 -1 5 -1 5 1 5 1 8 1 8 1 8 4 8 4 7 4 7 4 7 3 7 3 6 3 6 3 6 7 6 7 3 7 3 7 3 5 3 5 5 5 5 5 5 6 5 6 4 6 1 -1 -1 -1 -1 -1 -1 3 
•  » » » 8 years ago, # ^ |   0 Can you describe the solution please?
•  » » 8 years ago, # ^ |   +19 First, print 0 200 times. Then denote the sum of last n - 1 elements (denote them by a1, a2, ..., an - 1) by S. We print 0 and get . Then we print a1 + a2 and get . Then we print a3 + a4 and get . When the new answer tk + 1 is less than the previous one tk we know that M = 2tk - tk + 1.The only problem is when . In this case we print a1 + a2 ± 1 (plus or minus depends on if a1 + a2 equals 1e9 or doesn't) and continue in the same manner.First 200 zeroes are needed in order to have a2k - 1 + a2k no more than 1e9.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +28 First print 10^9. We will get r. (SumOfLast(n) - r) % m == 0, (SumOfLast(n) - r) > 0.Assume that we know that m1: m1 % m == 0, m1 > 0.Let's x = min(m1 - 1 - SumOfLast(n - 1) % m1, 10^9); r1 = SumOfLast(n - 1) % m1 + x.Let's print x and get answer r. If r == r1, then m == m1.Else if m1New = gcd(m1, r1 - r), then m1New % m == 0, m1New <= m1 / 2 and m1New > 0.Let's m1 = m1New. Continue this, while m1 is decreasing.At most 40 questions (first m1 < 10^11).