riadwaw's blog

AIM Tech Round Tutorial
By riadwaw, 9 years ago, translation, In English

624A - Save Luke

Width of free space is decreasing by v1 + v2 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.

624B - Making a String

Sort array in descending order.

Iterate over all letters, First letter is added c1 = a1 times, each other letter is added ci = min(ai, ci - 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.

623B - Array GCD

At least one of ends (a1 or an) is changed by at most 1. It means that if gcd > 1 then it divides on of prime divisors of either a1 - 1, a1, a1 + 1, an - 1, an or an + 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(ai)), where d is the number of primes to check.

623C - Electric Charges

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 xL and xR are their x-coordinates. Notice that points with x-coordinate xL ≤ x ≤ xR 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 xL < 0 be its coordinate. Notice that one may project all points such that 0 ≤ x - xL ≤ M and |x| ≤ |xL| 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 ymax - ymin <  = M and distance from (xL, 0) to both (0, ymax) and (0, ymin) 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

623D - Birthday

Let's denote qi = 1 - pi.

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 ki — 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 li (), not equal to set produced by greedy algorithm ki, gives the maximum value of Pr(t). Let's take some ka < la and kb > lb, it is easy to prove tgat if we change lb to lb + 1, la to la - 1, then new set of li gives bigger value of Pr(t), contradiction.

2) qi ≤ 0.99. Let's take set , it gives probability of end of the game not less than optimal. Then Pr(t) ≥ (1 - 0.99t / 100)100 ≥ 1 - 100·0.99t / 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.

623E - Transforming Sequence

First observation is that if the sequence of prefix xors is strictly increasing, than on each step ai 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(k3) complexity. We calculate dp[n][k] — the number of sequences of length n such that a1|a2|... |an 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]·2k·Ck + ll. The last binomial coefficient complies with the choice these very l bits from k + l which will be present in a1|a2|... |an + 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 dp1[k], dp2[k], where k is the number of bits present in a1|a2|... |aleft and b1|... |bright 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 109 + 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 :)

  • Vote: I like it
  • +92
  • Vote: I do not like it

Comments Comments (42)
| Write comment?
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    We can see that, we only need 3 letters.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 4   Vote: I like it +12 Vote: I do not like it

        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 invalid

        Nodes 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 connected with a node of the other group. If the first happens with every node and the second does not happen with any node, then the solution is correct and all that we need to do is to print the letter assigned to every node.

        Check my solution 15811518!

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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://mirror.codeforces.com/contest/624/submission/15810436

    → Reply
»
9 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

You forgot to translate the word Разбор in the title, Sir.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.....

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let's say at some stage x we take some vj > vi. Note that we must eventually take vi later, or else the expected value will be infinity. So let's say we take vi at position y > x. But xvi + yvj < xvj + yvi, which means we would've done better if we had taken vi first.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think Div2 B should be c[i ]= min(a[i], c[i - 1]-1)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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://mirror.codeforces.com/contest/624/submission/15810436

    → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +20 Vote: I do not like it
    1. A number N can have at most distinct prime factors
    2. If the gcd of the array is greater than 1, then there exists at least one prime p, such that all numbers of that list are divisible by p.
    3. Since we can't delete the entire array using operation one, then we can deduce that at least 1 of array[1] and array[n] are not delete using operation 1.
    4. WLOG, assume that array[1] is not deleted using operation 1. Then some prime factor of array[1] or array[1]+1 or array[1]-1 divides all other elements of the final list.
    5. Iterator over each prime factors of each of the following elements — array[1], array[1]+1, array[1]-1, array[n], array[n]+1, array[n]-1 and see what is the best answer we can get.
    6. To maintain the answer we can use dp, which says what is the minimum cost to make the gcd of the first i elements > 1 if a) we have already removed some subarray from the list b) if we are in the process of removing some subarray from the list c)if we haven't removed any subarry from the list yet. This can be done in time.
    7. According to point one we do step 6 at most times thus giving the said complexity (here M is at most 109)
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

Problem E:

Let the exponential generating function of dpi be pi(x), so pi(x) = (ex - 1)pi - 1(2x).

The answer is .

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 22   Vote: I like it +10 Vote: I do not like it

    The above formula is missing a factor of ex.

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please can you add editorial for div1 D ?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    done

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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?

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Could somebody explain the solution to problem Array Gcd?

→ Reply