### dragoon's blog

By dragoon, history, 9 months ago, ,

Let's discuss the problems.

• +70

 » 9 months ago, # |   +13 How to solve A, E, H?
•  » » 9 months ago, # ^ |   +41 E: I used Java Biginteger since the numbers were too big.We can represent the points on the first segment as parameter of t. If A and B are vector to the two end points, then an arbitrary point on AB is: tA + (1-t)B = t(A-B) — B. Similarly we can express a point on the second segment as parameter of s: s(C-D)-D.Let's compute distance-squared between these points: sum[t(A-B) + s(C-D) + D — B]^2 [sum is over each of the coordinates] = sum[tE + sF + G]^2 (*).To minimize this sum, we can partially differentiate with respect to t and s and hence we will get two equations: t(sum-of-E^2) + s(sum-of-EF) + (sum-of-GE) = 0 and t(sum-of-EF) + s(sum-of-F^2) + (sum-of-GF) = 0. Solving them we will get s and t. And then we can plug value of s and t to (*) we will get the answer.There is a corner case where the lines are parallel with the same direction vector. In such situation, we will have only one equation instead of 2. I plugged in s=0 to get a value for t, and the remaining part was same.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +21 A: Find SALT with precalc. First find all numbers that satisfying second array (~4000 numbers). Then from that 4000 numbers find that number which satisfying first array.
•  » » » 9 months ago, # ^ |   0 How would you do this precalc? My simulation was too slow.
•  » » » » 9 months ago, # ^ |   +15 Notice that you can go from the end (previous seed is determined uniquely)
•  » » » » » 9 months ago, # ^ |   0 Modulo was 2^31, so division is not unique right?
•  » » » » » » 9 months ago, # ^ |   0 You multiply by odd number, so it is. All coprime numbers have unique inverse.
•  » » » » » » » 9 months ago, # ^ |   +10 So, is it like: [reference: 1 3 2 3 0 0 4 2] 1. loop over 0..2^31-1 and see if it's %5 = 2, 2. if so, find the previous seed, and check %5 = 4 ...if all 8 passes, then this is a candidate.So running over 2^31 numbers and doing something like 8 operations. Is this your simulation? And it runs in reasonable time?
•  » » » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +10 Yes, but you continue after that to previous numbers (10k times go back for each number), It leaves only 1/5 of numbers each time so it works faster then is mod*8, it's like mod*5/4 or so, it's not so much especially considering you almost don't use memory
•  » » » » 9 months ago, # ^ |   +20 I used two steps: check only for the last 8 integers, skipping the long generation of 80000 integers: you can perform k steps of generator in O(log(k)) with matrix exponentiation or in O(1) with precalc if k is fixed. If the last 8 integers match, I also check the first 8.
•  » » » » » 9 months ago, # ^ |   +10 Even better: we can bruteforce only "good seeds after 80k iterations skipped", and then only with the succeeding seeds perform 80k roll-backs and checking that power sequence is the same as we want.
•  » » » » 9 months ago, # ^ |   +8 A way to do it without reversing the random number generator is to use a circular buffer for the random values.Start with some seed. Compute the first 80 008 pseudorandom values and put them in an array. Look if the last 8 values, pseudorandom numbers with indices 80 000-80 007 in the array, give the required Gene array if taken mod 5. It happens fairly rarely, like 231 / 58 times. If it did happen, use the previous 80 000 values to slowly check the Power array.Now suppose it didn't work on the first try. Generate the next random value, and check for the numbers with indices 80 001-80 008, all mod 5, that they give the required Gene array. Then generate the next random value and check the numbers with indices 80 002-80 009, and so on.Lastly, note that we should store only the last 80 008 pseudorandom numbers in this approach, so use a circular buffer to store them: for example, an array of size 131 072 which is accessed as Index mod 131072 every time we use it.This approach takes 3-4 minutes to check all 231 possible values of Salt (and probably finds the right one a bit faster, depending on where you started). The Gene array is not necessary at first glance, but actually makes our task easier as shown above. But there is also a fast approach which does not use it. Same as above, start with some seed and generate 80 000 first pseudorandom numbers ri. Calculate the sum of r0 to r9999, the sum of r10 000 to r19 999, and so on until the sum of r70 000 to r79 999. If they are the eight sums we need, great! Otherwise, it's easy to obtain the next eight sums r1 to r10 000, ..., r70 001 to r80 000 from them: for each sum, just subtract the first element and add the next one. And so on: generate the next pseudorandom value, get the next sums in O(1) each, check the eight sums, proceed if they don't match.
 » 9 months ago, # | ← Rev. 2 →   +8 H: Since the maximum area could be 10^30, I coded it in Java (BigInteger) [not sure if there is __int128 in yandex, never used it before]. Barely made it pass in 1.8s after several TLEs. Any better solution?My solution was: binary search on the coordinates one by one. Since coordinate value can be 1000, so at most 10*log(1000) ~ 100 call to a function which says true/false to the question, whether the area of the big box is same as union of other boxes (after cutting those boxes by the query box). The union of other boxes can be computed by Inclusion-Exclusion.
•  » » 9 months ago, # ^ |   0 We used random modulo in C++ to compare volumes. Still had to optimize a bit
•  » » 9 months ago, # ^ | ← Rev. 2 →   +18 There is no need in binary searching over all values for a coordinate. The answer always coincides with some of the b_i, it gives log 10 instead of log 1000 and works fast enough. I used __int128 and didn't have to do any extra optimizations.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +20 After coordinate compression, the area is only 4010 so no need for BigInteger.
•  » » 9 months ago, # ^ |   +10 __in128_t, c++, yandex. AC :)
 » 9 months ago, # |   +6 How to solve I?
•  » » 9 months ago, # ^ |   +20 Give N distinct random odd numbers, so all of them has inverse.Then take a number from the given N / 2 number, and multiply this with inverses of your numbers. So you have N candidates for X.Now try other numbers from those N / 2 numbers and in each step you'll get another N candidates for X, but only keep the intersection of these candidates and previous candidates. Since the N / 2 numbers is random, the number of candidates will soon become 1.
 » 9 months ago, # | ← Rev. 2 →   0 How to solve E? I tried to write a solution using __int128, but it seems to be overflowing (not sure, got WA on test 12 and TLE in Pypy on same test). What are the bounds for the final result?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +59 The limit is about 1045-1046 for numerator and 1030-1031 for denominator. We used BigInteger in Java.
 » 9 months ago, # |   +36 How to solve C?
 » 9 months ago, # |   +18 How to solve J?
 » 9 months ago, # |   +10 How to solve B and L?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +28 B, very briefly. Let's delete all vertices such that one of the sinks is unreachable from them. Notice that for every vertex x of a correct machine the set of edges on any path from the source to x contains the same set of edges. It follows from the fact that any path from the source to the 1-sink have to contain all the edges (can you see why?). Moreover, for every vertex x of a correct machine and for every pair of paths from the source to x and for every vertex of G the parity of the sum of the values of the edges is the same on both paths. The argument is similar to (1). One can verify (1) and (2) using hashing. if (1) and (2) hold then f(x) = 1 implies . The only possibility for an error is x such that f(x) = 0 but . The case (5) happens if and only if there is a vertex of the machine x labeled with an edge e such that e is not a bridge in the graph G - e'0 - e'1 - ... - e'k where e'1, ..., e'k are the edges on a path from the source to x. (6) could be verified using disjoint set union with rollbacks.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 In L, A few questions: How to compute A's or B's? "there is only one tangent plane or no tangent planes." -> How does the one tangent plane case look like? I can think of only two cases, one with two tangent planes, another with very small radius sphere inside a tunnel consisting of convex hull of other two spheres. "It's possible to write down the formula for the volume of such shape. " -> How do you find the formula? Any easy trick or calculus? or may be there is some name of the shape and formula in internet/wikipedia?
•  » » » 9 months ago, # ^ |   +10 First, we note that the vectors OiAi are collinear and normal to the tangent plane. So, all we need is to find this normal. Consider all planes that touch first and second spheres (but not necessarily the third). Consider normals to them. Their locus is a circle on the unit sphere. So we need to intersect this circle with the analogous circle for spheres 1 and 3. Imagine a plane and a line on this plane. Now consider 3 spheres that touch both this plane and this line. Consider, for instance, the case when the middle sphere has radius greater than the radii of two other spheres. I think that in this case there is only one tangent plane. You shouldn't care about that in your solution, anyway. It can be calculated using calculus, if we note that the shape is a solid of revolution.
•  » » » 9 months ago, # ^ |   +10 You can check my solution here.If you would like to look at the solution I used for stress-testing, here it is. This solution does the following: first, we consider a big cube, that contains our spheres. On each step we divide this cube into 8 parts, and remove those parts which lie outside or inside the convex hull. It's hard to check that the cube lies outside the convex hull, so instead of it I check that circumscribed sphere of the cube does not intersect the convex hull. After several steps we are left with some cubes which lie along the boundary. Finally, we can use Monte-Karlo method to calculate the volume of the intersection of these remaining cubes and the convex hull.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Seems that tests for J were weak. Seems that hardest tests against solutions I have seen were s=t=0 and s = neg(t).
•  » » » 9 months ago, # ^ |   0 You are right, many unexpected solutions passed. We had several solutions which calculated some statistics independently for positions and all of them failed in several tests, but some contestants used slightly different approaches/magic constants and got AC :(
•  » » » » 9 months ago, # ^ |   0 You should just make more tests. Seems that 50 tests of both these types were enough
•  » » » » » 9 months ago, # ^ |   0 Yes, more tests is better. Also for some solutions tests with strings different in one position were special, for example.
•  » » » » » » 9 months ago, # ^ |   0 Usually they also fail on all different. Basically you have problem with two equal letters which looks like different or with two different looks like the same.
 » 9 months ago, # | ← Rev. 2 →   +5 Can someone give statements of the problems please?
•  » » 9 months ago, # ^ |   +8 You can download statements at upper-right corner, near "Jury messages" button.
 » 9 months ago, # |   +27 Is it possible to add the Grand Prix contests to Codeforces Gym? I think there are many people here who want to solve problems of GPs, but are unable to solve due to Sector issue and many more.
 » 9 months ago, # |   +10 How to solve D?
•  » » 9 months ago, # ^ |   +15 Consider rotating the plane a bit:The fat squares comprise a grid corresponding to the crosses. There are at least two ways from here: For each square, find the center square of its cross, and then calculate the Manhattan distance between crosses. Note that the centers of the smaller squares are in the corresponding cross if and only if they are in the corresponding fat square. So instead of finding the center of the cross, we can just do some rounding.
•  » » » 9 months ago, # ^ | ← Rev. 3 →   +10 It's probably will get down to the same formulas, but your interpretation seems beautiful but too hard to actually come up with.What we did: Suppose we are going from cross center to cross center: Then we will make several(possibly negative number) (2, 1) moves and several (-1, 2) moves. Then just solve linear system of 2 variables and 2 equations. Now, to get cross center we just need to check initial cell and 4 its neighbours to check if they are in the form mentioned in the statement (again, 2x2 linear system. need to check whether answer is integral)
•  » » » » 9 months ago, # ^ |   +10 Yeah, my solution, in code, is actually translating coordinates (x, y) into ((2x + y) / 5, (x - 2y) / 5), which is the same thing you will get after solving the system of linear equations.And I think one way to achieve it is not actually harder than the other. Just that some people prefer visualization, and some other prefer formulas. From the people I've met, both "groups" (in my subjective classification) had individuals which had been very successful at mathematics and algorithms.
•  » » » » 9 months ago, # ^ |   +10 We solved exactly as Gassa told. I don't think it was hard.
 » 8 months ago, # |   +2 A: Shouldn't all pet powers be 500? Regardless of seed, Random() multiplies it by 1234567893 (multiple of 3) and adds 151515151 (equal 1 mod 3). Hence, Random() return value will always be 1 mod 3, and inside GenerateRandomPower(), Result value in each iteration will be the same (500). Am I missing anything?
•  » » 8 months ago, # ^ |   +1 Note that all calculations are made modulo 231. Before we take the value mod 3, it is taken mod 2^{31}. So the end result may be different after every call.
•  » » » 8 months ago, # ^ |   +9 What a silly mistake! Thank you for pointing out!