Width of free space is decreasing by *v*_{1} + *v*_{2} per second. It means that it'll decrease from *L* to *d* in seconds. The moment when width gets a value of *d* is the last when Luke is alive so *t* is the answer.

Sort array in descending order.

Iterate over all letters, First letter is added *c*_{1} = *a*_{1} times, each other letter is added *c*_{i} = *min*(*a*_{i}, *c*_{i - 1}). Don't forget that if some letter is not added at all, then all next letters are not added too.

623A - Graph and String Note that all vertices "b" are connected with all other vertices in the graph. Find all such vertices and mark them as "b". Now we need to find any unlabeled vertex *V*, mark it with "a" character. Unlabeled vertices connected with *V* should be also labeled as "a". All other vertices we can label as "c"

Finally we need to check graph validity. Check that all vertices "a" are only connected with each other and "b" vertices. After that we need to perform a similar check for "c" vertices.

At least one of ends (*a*_{1} or *a*_{n}) is changed by at most 1. It means that if gcd > 1 then it divides on of prime divisors of either *a*_{1} - 1, *a*_{1}, *a*_{1} + 1, *a*_{n} - 1, *a*_{n} or *a*_{n} + 1. We will iterate over these primes.

Suppose prime *p* is fixed. For each number we know that it's either divisible by *p* or we can pay *b* to fix it or it should be in the subarray to change for *a*

We can use dynamic programming dp[number of numbers considered][subarray to change not started/started/finished] = minimal cost

Complexity is *O*(*Nd*) = *O*(*Nlog*(*max*(*a*_{i})), where *d* is the number of primes to check.

First of all consider cases where all points are projected to the same axis. (In that case answer is difference between maximum and minimum of this coordinate).

Now consider leftmost and rightmost points among projected to *x* axis. Let *x*_{L} and *x*_{R} are their *x*-coordinates. Notice that points with x-coordinate *x*_{L} ≤ *x* ≤ *x*_{R} may also be projected to *x*-axis and that will not increase the diameter. So, if we sort all points by *x*-coordinate, we may suppose that points projected to *x*-axis form a continuous subarray.

We will use a binary search. Now we will need to check if it's possible to project point in a such way that diameter is <= M.

Let's fix the most distant by *x*-coordinate point from 0 that is projected to *x*-axis. It may be to the left or to the right of 0. This cases are symmetrical and we will consider only the former one. Let *x*_{L} < 0 be its coordinate. Notice that one may project all points such that 0 ≤ *x* - *x*_{L} ≤ *M* and |*x*| ≤ |*x*_{L}| to the *x* axis (and it'll not affect the diameter) and we have to project other points to *y*-axis. Among all other points we should find the maximum and minimum by *y* coordinate. Answer is "yes (*diam* ≤ *M*)" if *y*_{max} - *y*_{min} < = *M* and distance from (*x*_{L}, 0) to both (0, *y*_{max}) and (0, *y*_{min}) is not greater than M.

Let's precalculate maximums and minimums of *y* coordinates on each prefix and suffix of original (sorted) points array. Now iterate over left border of subarray of points projected to *x*-axis and find the right border using binary search or maintain it using two-pointers technique.

So we've got one check in *O*(*M*) or and entire solution in or

Let's denote *q*_{i} = 1 - *p*_{i}.

Main idea: first of all guess each friend once, then maximize probability to end game on current step. Let's simulate first 300000 steps, and calculate . , where *k*_{i} — how many times we called *i*-th friend ().

Expectation with some precision equals . So it is enough to prove that:

1) Greedy strategy gives maximum values for all *Pr*(*t*).

2) On 300000 step precision error will be less than 10^{ - 6}.

Proof:

1) Suppose, that for some *t* there exists set *l*_{i} (), not equal to set produced by greedy algorithm *k*_{i}, gives the maximum value of *Pr*(*t*). Let's take some *k*_{a} < *l*_{a} and *k*_{b} > *l*_{b}, it is easy to prove tgat if we change *l*_{b} to *l*_{b} + 1, *l*_{a} to *l*_{a} - 1, then new set of *l*_{i} gives bigger value of *Pr*(*t*), contradiction.

2) *q*_{i} ≤ 0.99. Let's take set , it gives probability of end of the game not less than optimal. Then *Pr*(*t*) ≥ (1 - 0.99^{t / 100})^{100} ≥ 1 - 100·0.99^{t / 100}. Precision error does not exceed . It could be estimated as sum of geometric progression. If *N* ≥ 300000 precision error doesn't exceed 10^{ - 7}.

First observation is that if the sequence of prefix xors is strictly increasing, than on each step *a*_{i} has at least one new bit comparing to the previous elements. So, since there are overall *k* bits, the length of the sequence can't be more than *k*. So, if *n* > *k*, the answer is 0.

Let's firstly solve the task with *O*(*k*^{3}) complexity. We calculate *dp*[*n*][*k*] — the number of sequences of length *n* such that *a*_{1}|*a*_{2}|... |*a*_{n} has *k* bits. The transition is to add a number with *l* new bits, and choose those *k* bits which are already in the prefix xor arbitrarily. So, *dp*[*n* + 1][*k* + *l*] is increased by *dp*[*n*][*k*]·2^{k}·*C*_{k + l}^{l}. The last binomial coefficient complies with the choice these very *l* bits from *k* + *l* which will be present in *a*_{1}|*a*_{2}|... |*a*_{n + 1}.

Note now that the transition doesn't depend on *n*, so let's try to use the idea of the binary exponentiation. Suppose we want to merge two dynamics *dp*_{1}[*k*], *dp*_{2}[*k*], where *k* is the number of bits present in *a*_{1}|*a*_{2}|... |*a*_{left} and *b*_{1}|... |*b*_{right} correspondingly. Now we want to obtain *dp*[*k*] for arrays of size *left* + *right*. The formula is:

Here *l* corresponds to the bits present in the xor of the left part, and for each number of the right part we can choose these *l* bits arbitrarily. Rewrite the formula in the following way:

So, we can compute *dp*[*k*] for all *k* having multiplied two polynomials and . We can obtain the coefficients of the first polynomial from the coefficients of the second in . So, we can compute this dynamic programming for all lengths — powers of two, in , using the fast Fourier transform. In fact, it is more convenient to compute using the same equation. After that, we can use the same merge strategy to compute the answer for the given *n*, using dynamics for the powers of two. Overall complexity is .

We decided to ask the answer modulo 10^{9} + 7 to not let the participants easily guess that these problem requires FFT :) So, in order to get accepted you had to implement one of the methods to deal with the large modulo in polynomial multiplication using FFT. Another approach was to apply Karatsuba algorithm, our realisation timed out on our tests, but jqdai0815 somehow made it pass :)

Why is the editorial for 623B the same as the one for 624B??

fixed

Where is the Solution of Div2-C Graph and String ?

We can see that, we only need 3 letters.

a node with letter 'b' will must be connected to all other nodes i.e having (n-1) edges.

so for each node with (n-1) edges, assume that it's letter is 'b'.

Then for each node 'x' that is not assigned a letter yet, assume it's 'a', and for each other node 'y' that has an edge with 'x', assume it's 'a', and for each node 'y' that has no edge with 'x', assume it's 'c'.

after that, if the resulting string passes the second condition given in the problem statement, then you can print this string, otherwise print 'No'.

This is my code after the contest is done.

thank you..your solution works perfectly for me too...

Could you please explain the intuition behind this solution. I came up with the b part of the solution but could not fully solve it during contest.

We'll assign a letter to each node, A, B or C.

'B' types nodes are always connected to every other node, so we'll count for each node how many neighbors it has. We'll assign those who count N-1 neighbors the B letter (are connected to every other node). It's important to understand, just in case solution exist there are no more or less B nodes than the ones we've just marked, so every node that we have not marked must be either a 'A' node or a 'C' node.

Both 'A' and 'C' nodes can not be connected, while every A node must be connected with every other A node and every other C node must be connected with every other C node. Also both 'A' and 'C' must be connected to every 'B' node but we already know that from the first step! so we just ignore this detail that we already know. From the definition above you must note that as 'A' nodes and 'C' nodes have exactly the same definition we could easily in a correct solution change every 'A' type node to 'C' type and vice-versa (common sense guys!), so to continue with our solution we'll get any node that is not of 'B' type and we'll assign to it the letter 'A' (could be 'C' and the solution does not change). We know that all 'A' nodes are connected to each other. This means that if the correct solution exist then every node connected to the node we've just marked (except those of type B) must be'A'. So now we assign the letter 'A' to each of them. Then we'll do the same with any of the nodes not marked yet, assigning the 'C' letter to it and then to every of its neighbors.

We now can make the first control to check if the chance is correct. If there are nodes that we did not mark either 'A','B' or 'C' then the graph given is

invalidNodes recently marked as 'B' does not determine the solution because they are connected to each other node and nothing could happen to invalidate the graph with those nodes.

So we need to check if both the 'A' nodes and the 'C' nodes follow the rules To both of those cases we'll check every node of the two groups to be connected to every node of its group and to

not be connectedwith a node of the other group. If the first happens with every node and the second does not happen with any node, then the solutionis correctand all that we need to do is to print the letter assigned to every node.Check my solution 15811518!

I have the exact same solution for C, but I don't know why I failed during contest. I used bipartie graph. I connected all nodes that are not connected, then I check if that graph could be a bipartie graph. My code: http://codeforces.com/contest/624/submission/15799060

Sorry, I understand why I was wrong.

And that is the way editorials should be written :)

thank you :D

But there is symmetry,right? For example: If there is an answer aaabbbc,the answer cccbbba also true?

correct, there is such symmetry because the definition of A nodes is the same as the definition of C onesb's must have edges to all other vertices -> So all index's with N-1 edges must be b's. Now, we can observe that the complement of the Graph must be bipartite. Performing coloring on that we can label each node (or index) as 'a' or 'c' and then print the resultant string.

In the end, just do another check to make sure that the string satisfies the constraints.

Code : http://codeforces.com/contest/624/submission/15810436

Stupid but true: I solved Div. 2 A using Binary Search :| I think you should add binary search tag to the problem haha.

Well, you can always divide using binary search

You should have done it by ternary search :)

You forgot to translate the word

Разборin the title, Sir.My dfs timed out in Problem C div 2. Guess it doesn't work, or perhaps some coding error...

Don't you think that Problem D and E for div 2 are a little bit too difficult? It would be more competitive if Acceptance of D were more than 50 or so.....

Can somebody explain 623D, it's not on editorial...

I haven't proof to this solution, but it's simple and has got AC.

Iterate number of rounds (200000 is enough). Some rounds are already played, and you know probability of each friend to be right guessed (denote as g[i]). Let's guess k-th friend. Then we count probability of situation, when all friends, except k-th, are already right guessed, and now we right guess k-th friend: v[k] = g[1] * g[2] * ... * g[n] / g[k] * (1 — g[k]) * p[k] / 100. Add to answer: answer = answer + number * v[k]. It's optimally to take friend with maximum v[k].

It's enough to choose maximum v[k] in O(n) in each iteration, maintaining value g[1] * g[2] * ... * g[n].

To avoid problem with divide by g[k] = 0, at the beginning you need to try to guess each friend, then answer = (p[1] / 100) * (p[2] / 100) * ... * (p[n] / 100) * n.

Interestingly, when I raise the number of trails to 500000, it starts giving wrong answer towards author's solution (15819467), I think there're something to do with precisions of long double tho.

Edit: looks like long double brings more accurate results (15824577)

Let's say at some stage

xwe take somev_{j}>v_{i}. Note that we must eventually takev_{i}later, or else the expected value will be infinity. So let's say we takev_{i}at positiony>x. Butxv_{i}+yv_{j}<xv_{j}+yv_{i}, which means we would've done better if we had takenv_{i}first.I think Div2 B should be c[i ]= min(a[i], c[i - 1]-1)

Did anyone solve 624C by checking whether complement of the graph is biparite or not? Is there something wrong in this algo?

I made this mistake too. The complement has to be composed of isolated vertices and one

completebipartite graph.b's must have edges to all other vertices -> So all index's with N-1 edges must be b's. Now, we can observe that the complement of the Graph must be bipartite. Performing coloring on that we can label each node (or index) as 'a' or 'c' and then print the resultant string. In the end, just do another check to make sure that the string satisfies the constraints. Code : http://codeforces.com/contest/624/submission/15810436

Solved 624C - Graph and String with a different approach

I checked for any unconnected edge, which implied that one end had to be 'a' and the other 'c'. So mark them as 'a' and 'c' respectively

Now for all the other nodes check their edges with the found nodes in previous step, there would be 4 possibilities:

1) Connected to both, mean the node is 'b'

2) Connected to the one marked 'a' only, mean the node is 'a'

3) Connected to the one marked 'c' only, mean the node is 'c'

4) Connected to none, means such a graph can't exist.

You now have the if and only possible string, (other possible string would just have been, if you taken the node marked 'a' as 'c' and vice versa)

Now just check for its validity

This is my code 15819935

Can somebody please explain Array GCD in more detail? The dp solution as well as the logarithmic term in complexity is not clear to me. Thanks.

Ncan have at most distinct prime factorsp, such that all numbers of that list are divisible byp.Mis at most 10^{9})I followed your method creating a dp[n][3] (haven't/started/finished), my solution got accepted but I didn't took care of the whole array being deleted. Were the test cases too weak or dp takes care of this itself, if yes how? My code is here : VastoLorde95 riadwaw

Oh, sorry got it. All elements are greater than 1 so deleting n-1 elements would ensure gcd > 1.

Problem E:

Let the exponential generating function of

dp_{i}bep_{i}(x), sop_{i}(x) = (e^{x}- 1)p_{i - 1}(2x).The answer is .

The above formula is missing a factor of

e^{x}.In fact, multiplying this out shows that you get , which shows that the answer equals (the nice expression!) after extracting the answer. I have no idea if this leads to anything nice though.

Please can you add editorial for div1 D ?

done

Can you improve it a little? I don't understand anything...how to choose optimal k? I really don't get it.

for the question graph and string test 24 input: 6 4 3 2 1 3 6 5 4 6 output: Yes cccaaa my output: No as there is no edge between 1 and 2 how can they both be c?

^ignore the above comment i read it wrong my bad :/

Look at the full-solution explanation I made of problem E Div2 (C Div1) "Electric Charges" here :)

Could somebody explain the solution to problem Array Gcd?