Let's discuss the problems.

Before contest

Codeforces Round #518 (Div. 1) [Thanks, Mail.Ru!]

12:33:32

Register now »

Codeforces Round #518 (Div. 1) [Thanks, Mail.Ru!]

12:33:32

Register now »

*has extra registration

Before contest

Codeforces Round #518 (Div. 2) [Thanks, Mail.Ru!]

12:33:32

Register now »

Codeforces Round #518 (Div. 2) [Thanks, Mail.Ru!]

12:33:32

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3581 |

2 | OO0OOO00O0OOO0O0…O | 3264 |

3 | mnbvmar | 3246 |

4 | LHiC | 3183 |

5 | Um_nik | 3176 |

6 | Petr | 3161 |

7 | Radewoosh | 3128 |

8 | CongLingDanPaiSh…5 | 3116 |

9 | ainta | 3115 |

9 | ko_osaga | 3115 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 191 |

2 | Errichto | 166 |

3 | rng_58 | 160 |

4 | tourist | 158 |

5 | Vovuh | 150 |

5 | Um_nik | 150 |

7 | Petr | 149 |

7 | Swistakk | 149 |

9 | 300iq | 148 |

10 | neal | 147 |

10 | PikMike | 147 |

Let's discuss the problems.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/24/2018 07:01:29 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How to solve A, E, H?

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.

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.

How would you do this precalc? My simulation was too slow.

Notice that you can go from the end (previous seed is determined uniquely)

Modulo was 2^31, so division is not unique right?

You multiply by odd number, so it is. All coprime numbers have unique inverse.

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?

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

I used two steps:

ksteps of generator inO(log(k)) with matrix exponentiation or inO(1) with precalc ifkis fixed.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.

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 2^{31}/ 5^{8}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 2

^{31}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 numbersr_{i}. Calculate the sum ofr_{0}tor_{9999}, the sum ofr_{10 000}tor_{19 999}, and so on until the sum ofr_{70 000}tor_{79 999}. If they are the eight sums we need, great! Otherwise, it's easy to obtain the next eight sumsr_{1}tor_{10 000}, ...,r_{70 001}tor_{80 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 inO(1) each, check the eight sums, proceed if they don't match.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.

We used random modulo in C++ to compare volumes. Still had to optimize a bit

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.

After coordinate compression, the area is only 40

^{10}so no need for BigInteger.__in128_t, c++, yandex. AC :)

How to solve I?

Give

Ndistinct 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 haveNcandidates forX.Now try other numbers from those

N/ 2 numbers and in each step you'll get anotherNcandidates forX, but only keep the intersection of these candidates and previous candidates. Since theN/ 2 numbers is random, the number of candidates will soon become 1.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?

The limit is about 10

^{45}-10^{46}for numerator and 10^{30}-10^{31}for denominator. We used BigInteger in Java.How to solve C?

Let's consider some pair of vertices (

u,v). Optimal path could be written as a sequence of verticesu=a_{0},a_{1}, ...,a_{p}=v. Obviously the edgea_{0}→a_{1}belongs to some cliqueAand edgea_{1}→a_{p}belongs to some cliqueB. The crucial observation is that if we fix the cliquesAandBwe are able to find the path betweenuandvwithout looking at the individual vertices but only at the cliques. Every edge in the path betweenuandvbelongs to one or several cliques. Let's call a pair of cliquesC_{1}andC_{2}connected if there exists vertexxbelongs to bothC_{1}andC_{2}. The path betweenuandvcould be decribed as a sequence of cliquesA=A_{1},A_{2}, ...,A_{p - 1}=BwhereA_{i}connected withA_{i + 1}. It's obvious that with given vertices of the path we can easily find the indices of the cliques. On the other hand given the indices of the cliques we can by definition choose a common vertex for every consecutive pair of cliques and add the starting and the ending vertices.Let's consider a graph

Gwhere each vertex corresponds to a clique and there is a directed edgei→jwith the weighta_{j}(weight of clique numberj) ifiandjare connected. Then for every pair (u,v) such that (S(k) is the set of vertices of cliquek).dist(u,v) ≤dist_{G}(i,j) +a_{i}wheredist_{G}is the distance between the cliquesiandjinG.dist_{G}could be found inO(k^{3}) with Floyd-Warshall algorithm.Gitself could be constructed by definition inO(n·k^{2}).Then all what we have to do is for every pair of cliques (

i,j) find the number of vertices such that the optimal path for these pairs corresponds to the path betweeniandjinG. Let's process pairs of cliques in the increasing order ofa_{i}+dist_{G}(i,j) and at each step find the number of pairs (u,v) such that ; and (u,v) was not considered at previous steps. Then if this number is denoted axwe should increase the answer byx·(a_{i}+dist_{G}(i,j)) because for these pairs there is no better path. Let's enumerate . For every cliqueiwe will maintain set of cliquesD(i) such that . Denote cliques whereubelongs asi_{1},i_{2}, ...,i_{p}. Pair (u,v) should be counted at this step iff and . Assuming that for every possible set of cliques {c_{1}, ...,c_{p}} we calculated α({c_{1}, ...,c_{p}}) the number of verticeswsuch that the intended number of verticesucould be found as .So, only thing we should do is to calculate α for each of 2

^{k}sets of cliques. First of all we can find β(I) the number of vertices belongs to cliques from setIand doesn't belong to any other cliques. Then . Even if we calculate alpha in straightforward way enumerating all the subsets of one can proof that we will have time complexityO(3^{k}) and it was enough to get accepted.But there is a way to calculate α in

O(2^{k}·k). It's easier to calculate α'(I), the number of vertices . Let's use dynamic programming:dp[mask][j] (wheremaskis the string ofkzeroes and ones) is the number of verticeswsuch that fori<jand fori≥j.dp[mask][k] = β(mask). Forj<kdp[mask][j] =dp[mask][j+ 1] +xwherex= 0 ifmask[j] = 0 andx=dp[mask'][j] (where andmask'[j] = 0) otherwise.For every vertex denote

M(v) as a string of zeroes and ones such that . Then first summand in dp corresponds to vertices withM(v)[j] =mask[j] and the second summand corresponds to vertices withM(v)[j] ≠mask[j] (ifmask[j] = 0 we should not calculate it). Finally it's pretty clear that α'(S) =dp[S][k].This is it, now we have a solution with time complexity

O(2^{kk}^{2}+n).How to solve J?

How to solve B and L?

B, very briefly. Let's delete all vertices such that one of the sinks is unreachable from them.

Notice that for every vertex

xof a correct machine the set of edges on any path from the source toxcontains the same set of edges. It follows from the fact that any path from the source to the 1-sink have to containallthe edges (can you see why?).Moreover, for every vertex

xof a correct machine and for every pair of paths from the source toxand for every vertex ofGthe 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

xsuch thatf(x) = 0 but .The case (5) happens if and only if there is a vertex of the machine

xlabeled with an edgeesuch thateis not a bridge in the graphG-e'_{0}-e'_{1}- ... -e'_{k}wheree'_{1}, ...,e'_{k}are the edges on a path from the source tox.(6) could be verified using disjoint set union with rollbacks.

Solution sketches for some problems:

B:

While traversing through the machine we can watch for a state of the graph -- mask of size

kthere 1 is corresponding to not satisfied nodes. Initially this mask is equal to the arrayc. After going along an edge fromvtouin the machine state may change -- if this edge was labeled with 1 then values of endpoints of the edge in the graph must be flipped. Our goal is to check if each path tot_{1}corresponds to an empty mask and if each path tot_{0}corresponds to a nonempty mask.Let's note some facts about the case then answer is YES:

stot_{1}allmlabels must be present, because otherwise we can freely change value of not presented edge and one of the corresponding states will be nonempty, but still leads tot_{1}stot_{i}all labels are distinct mean that if one can reacht_{1}from some nodevthen paths fromstovuse the same set of edges in the grapht_{1}from some nodevthen path fromstovmust correspond to the same state of the graph, otherwise one can reacht_{1}with 2 different masksIt is easy to check 1. and find corresponding counterexample if it exists. 2. and 3. can be checked with hashing the state of the graph: generate random

z_{v}for each 1 ≤v≤k, hash of the state will be of all not satisfied nodes. It is easy to update this hash then values of 2 nodes in mask changes -- just it with .Now we can assume that if some configuration of edges in the graph leads to

t_{1}then it is really 1. The last thing to check is existence of configuration of edges leads tot_{0}but have . Consider edge in the machine fromvtousuch that it is possible to get tot_{1}fromv, but not possible fromu. Each path tovuses the same set of edges in the graph and corresponds to the same state of the vertices of the graph. Fromuwe could only get tot_{0}, so the task here is to check whether we can assign some values to not used edges of the graph so that final state will be empty (allkzeros). We can do that iff in each connected component of not used edges xor sum of values of nodes in mask is zero. We can check that using dsu (disjoint set union) data structure with rollbacks: run dfs over back edges of the machine starting witht_{1}. Because in each path tot_{1}allmedges were used then dfs reaches the nodevit will contain exactly connected components of not used edges. To check if state is still ok after going along the edge fromvtouit is enough to check if endpoints of are in the same connected component (in case of edge fromvtoulabeled with 1 of course).F:

If

n=kthen answer is YES.Note the following facts:

If the answer if not prefix and not suffix than it is

kconsecutive maximums of the array. If the answer is suffix of lengthkthan it is nondecreasing anda_{n - k + 1}must be not less than alla_{i}with 1 ≤i<n-k+ 1. The same for prefix. All these cases are easy to check inO(n).J:

Ask "?" Q times. Select 2 strings from the input, denote them by

s' andt'. Let's think that they were generated from different base stringssandt. Cluster all the remaining string in 2 clusters based on distance tos' andt'. ConstructSandTby selecting the most frequent digit in each position in corresponding cluster. Check ifSandTcould generate givenQinput strings (each input string has distance exactlyKtoSor toT). If everything is OK, outputSandT.Let's provide some intuition about correctness of this solution.

What is the probability that some incorrect

SandTpass the final check? It means that some 25 strings were generated froms, but someS≠shas distanceKto each of them. But we can reconstructsfrom these 25 strings: with probability ≈ 0.999983 some position was flipped <13 times, and with probability ≈ 0.998312 each position was flipped <13 times. This is a lower bound for the correct probability. In reality situation is even better since we constructSandTin a special way.So we will win if for some pair of strings

s' andt' from the inputSandTappears to be equal tosandtrespectively. If distance betweensandtare big then each string almost certainly will be in correct cluster, if distance betweensandtare small then actually small number of positions are unknown and correct configuration of these positions will be found fast.To solve this problem one don't have to write down some probabilities, because it is very easy to verify correctness of solution locally.

Authors tried to find at least one test run there model solution fails, but didn't succeed.

K:

4 variables fully define the entire table:

* number in the left upper corner;

* difference of adjacent elements in the first row;

* difference of adjacent elements in the second row;

* difference of adjacent elements in the first column;

So one can solve system of linear equations over these variables. Be careful with small tables and thin table.

L:

We have to consider two separate cases: 1) there are two tangent planes, 2) there is only one tangent plane or no tangent planes.

The second case is easier, so we are going to describe only the first case. First of all, we need to understand the structure of the surface of the convex hull. It comprises the following parts: two equal triangles, which lie on two tangent planes; for each pair of spheres there is a part of the cone, tangent to these two spheres; for each sphere there is a part of the surface of this sphere.

It's convenient to start the solution by finding the normals to the tangent planes. If we can't find two distinct normals, then it's the second case and we do not discuss it here. Let

O_{1},O_{2},O_{3}be the centers of the spheres. Now, for convenience, we will suppose, that the plane that contains these three points is horizontal, and that the cross product (O_{2}-O_{1}) × (O_{3}-O_{1}) is in upwards direction.Let

A_{1},A_{2},A_{3}be the touching points of the upper tangent plane and spheres and letB_{1},B_{2},B_{3}be the touching points of the lower tangent plane. First, we calculate the volume of the polyhedron with the verticesO_{1},O_{2},O_{3},A_{1},A_{2},A_{3}. The volume of the polyhedron with the verticesO_{1},O_{2},O_{3},B_{1},B_{2},B_{3}is the same. Next, we should calculate the volume of the parts of the cones. Consider, for instance, the cone between first and second spheres. Consider the three-dimensional shape with verticesO_{1},A_{1},A_{2},O_{2},B_{2},B_{1}, with surface that consists of the part of the cone between first and second spheres, rectanglesO_{1},O_{2},A_{2},A_{1}andO_{1},O_{2},B_{2},B_{1}and also two parts of cones with verticesO_{1}andO_{2}. It's possible to write down the formula for the volume of such shape. We add to the answer this volume and analogous volumes of shapes between two other pairs of spheres.Finally, it remains to calculate the volume of the parts of the balls. It's just times the area of the part of the sphere. How does the part of the sphere looks like? It's bounded by two arcs of two circles, which are not geodesics. This problem is analogous to the following well-known problem: find the area of the union of two circles on plane. But in our case we should find the area of the union of two circles on sphere. This can be solved in a standard way.

For instance, consider the part of the first sphere. It's a union of two circles on the first sphere. These circles intersect in points

A_{1},B_{1}. Consider the geodesic between this two points. It separates our part of the first sphere in two parts. We calculate their areas separately. Each part is bounded by one geodesic betweenA_{1}andB_{1}and one arc of some circle between these two points. So, we need to calculate the volume of the segment of the circle on the sphere. To do this, we need to calculate the area of the sector of the circle and subtract the area of triangle.In L, A few questions:

O_{i}A_{i}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.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.

Seems that tests for J were weak. Seems that hardest tests against solutions I have seen were s=t=0 and s = neg(t).

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 :(

You should just make more tests. Seems that 50 tests of both these types were enough

Yes, more tests is better. Also for some solutions tests with strings different in one position were special, for example.

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.

Can someone give statements of the problems please?

You can download statements at upper-right corner, near "Jury messages" button.

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.

How to solve D?

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.

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)

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.

We solved exactly as Gassa told. I don't think it was hard.

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?

Note that all calculations are made modulo 2

^{31}. Before we take the value`mod 3`

, it is taken`mod 2^{31}`

. So the end result may be different after every call.What a silly mistake! Thank you for pointing out!