riadwaw's blog

OpenCup. GP of Xi'An
By riadwaw, history, 5 years ago, In English

Let's discuss problems.

How to solve B, F?

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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Was the TL too tight for C? My soln was 15nlogn and it barely passed with 0.9x second.

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

    I'm the author of C. There are solutions with $$$O(n \log^3 n)$$$ that can pass in 2s~3s.

    And the fastest model solution seems to be $$$O(n \log n \log \log n)$$$ can even finish $$$n=10^6$$$ in about 1.3s.

    We don't want to make it too hard, thus we set this constraint and TL. And all the tester solutions finished in 0.5s.

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

      Actually my soln is logn*sum of number of divisors of all numbers from 1 to n. Which is your second solution perhaps. May be I had to do some additional modulo operation optimization. Not sure.

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

        Can you tell that solution please? We could only come up with a nlognlogk one, which obviously needed some heavy optimizations to pass.

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

          Given initial f's, I tried to generate f^k in paper and I noticed a pattern. f^k(d) = sum over all the products of f(a_i) where product of a_i is d and there are k terms in the product. For example, f^3(4) = 3f(1)^2*f(4) + 3f(1)*f(2)^2.

          Since n is only 1e5, we will have only ~15 non-1 elements in a_i's. So we run a dp, if there are x non-1s and k-x 1's, what is the sum of product of f(a_i)'s. The state of the dp is: x (number of non-1s) and remaining "n". To calculate the dp value, we loop over all divisors and just some up DP(x — 1, n/divisor). Note, divisor = n is a special case, and it helps us computing f(n). Like this, we compute f(1), f(2)...f(N).

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

            O, really nice. That differs radically from ours.

            We relied on a fact $$$f^k(x) = af(x) + b$$$ for some $$$a$$$ and $$$b$$$. That helps us calculate values binpow-style. $$$f^{2k}(x) = f^k(x) + f^k(x)$$$ plus some known values over divisors and $$$f^{2k+1}(x) = f^{2k}(x) + f(x)$$$ plus known values. So for each $$$x$$$ you can calculate $$$O(\log k)$$$ powers on form $$$(a, b)$$$ and turn them into their actual values after solving $$$g(x) = af(x) + b$$$.

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

      How to solve problem C with $$$O(n \log n\log\log n)$$$?

      I'm curious about it.

      Dirichlet sum with $$$O(n \log\log n)$$$ once?

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

How to solve H nicely?

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

    Pick a random $$$i$$$ and try either $$$i + 1$$$ or $$$i + 2$$$ as next element in progression, Then add other elements greedily. Repeat 50 times.

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

      We followed similar approach but to avoid randmoness we computed all possible quotients from elements at distance 1 and distance 2. Then sorted all the elements by frequency, and start testing from higher to lower frequency. We repeated only 22 times (that was the most we can squeeze into time limit, and it was enough).

      Rationale about this solution, is that there should be a lot of elements in the final sequence at distance less than or equal to 2. Now in hindsight I think the right quotient appear at least $$$\frac{n}{4}$$$ times among this selected elements, so probably, testing only first four elements among the potential quotients should be enough.

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

      But how you determine by 2 elements in progression q and p?

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

        Fix two consecutive elements in the progression, then you already know the quotient, and running a simple linear dp you can find maximum progression with this quotient.

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

          Tell me please in detail about linear DP. I found something only with n*logn complexity.

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

            Ohh, it just using unordered_map instead of map.


            def solve(L, q):
    // best[a] = size of the longest progression 
    // that starts in `a` and have quotient `q` 
    // best[a] = 0 for all `a` initially.
    unordered_map<int,int> best;
    L = list of elements in the input
    answer = 0
    for u in reversed(L):
        best[u] = max(best[u], best[u * q % mod] + 1);
        answer = max(answer, best[u]
    return answer

            Read full solution here.

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

    How to solve it not nicely?

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

B:
write naive solution, and find the pattern is n choose i * m choose (i+(m-n+1)/2) * coef.
you can find coef by comparing sum over i with (n+m) choose n. I think coef can be written closed form, yet I can't figure out.

I'm also interested in solution of F. We wrote something like hill-climbing, but it didn't work well.

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

What is solution for task E ?

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

    A bit of hand-waving but still. Let's determine the maximum possible flow, that's $$$\lfloor \frac{sum\_of\_edges}{length\_of\_any\_path} \rfloor$$$. After that let's choose some path which is the cheapest to increase the flow by $$$1$$$ on (that is the number of edges of minimum value on the path). Repeat until the current flow is less than the maximum one. There is no need to find the edges to take the required capacities from, it's enough to know there will be such edges.

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

B: First assume that $$$2 | n + m$$$. There are $$$n+m-1$$$ "left up"-"right down" diagonals on the board of alternating colors, and the first and last diagonal is white and has length $$$1$$$. Add a final black diagonal of length $$$0$$$ so that there is an even number of diagonals.

Let's then pair up the neighboring diagonals into $$$\frac{n+m}{2}$$$ pairs. In each pair, the lower diagonal is white and the higher diagonal is black. When you look at the set of cells to the left of the walk in each pair of diagonals, you'll see that (the number of white cells) — (the number of black cells) is always $$$-1$$$, $$$0$$$ or $$$1$$$.

Let's investigate those more. Draw a line $$$x + y = n$$$ (green line on the image above). It turns out that the difference between the numbers of white and black cells in the $$$i$$$-th pair depends only on the direction of $$$2i$$$-th move and whether this move is above or under the green line:

  • When $$$2i$$$-th move is to the right and below the green line, the difference is $$$-1$$$.
  • When this move is going up, but it's below the green line, the difference is $$$0$$$.
  • When this move is going right and above the line, the difference is $$$0$$$.
  • When going up and above the line, the difference is $$$1$$$.

In other words: by default, the difference is $$$0$$$, but going up increases it by $$$1$$$, and being below the line decreases it by $$$1$$$. There are exactly $$$\left\lfloor \frac{n}{2} \right\rfloor$$$ even-indexed moves below the green line. Let's therefore increase $$$k$$$ by $$$\left\lfloor \frac{n}{2} \right\rfloor$$$. We can now assume that each even-indexed move right leaves the difference intact and each even-indexed move up increases the difference by $$$1$$$.

Therefore, we need to have exactly $$$k$$$ even-indexed moves go up and $$$n-k$$$ odd-indexed moves go up. It's easy to see there are exactly $$${(n+m)/2 \choose k}{(n+m)/2 \choose n-k}$$$ ways to do it.

When $$$2 \not\mid n+m$$$, we can consider both candidates for the final move (we either go up or right). In each case, we reduce the problem to the one with $$$2 \mid n+m$$$.

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

    And you somehow did it in 40 minutes?

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

      Well, we took part in the contest a couple days ago. Without other teams in the scoreboard, we needed to guess the difficulties of the tasks assigned to each of us, and this one somehow looked the easiest to me. ¯\_(ツ)_/¯ (I mean, I didn't really want to solve tasks like G first.)

      I mean, the solution looks long, but it's pretty straightforward if you decide to consider the pairs of diagonals instead of the pairs of columns (which looked very attractive at first).

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

      We also did this exact same solution in first hour, I guess it’s what happens when there’s no scoreboard and you have teammates to solve other problems on keyboard. :)

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

I: Was there any clever way to solve the task, or was it just a sad task checking if you've got a robust $$$O(n \log n)$$$ 3D convex hull in your library?

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

    There is a clever way that is based on the fact that all the points lie in a hemisphere. But there are still many corner cases to deal with. I don't know the details of the model solution.

    I can ask the author xyz2606 to answer the question.

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

      well, it gets somewhat straightforward if you know the hemisphere (or in other words, the plane that gives you this hemisphere). But I think to find it is probably as hard as 3D convex hull?

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

        "it gets somewhat straightforward if you know the hemisphere" — is it? At first I thought so as well, but it's not as simple as projecting onto this plane and doing 2D convex hull, but maybe you have something better on mind.

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

          Hm, yes it's what I had in mind. Now that you pointed it out, I understand that it probably doesn't work because lines do not project to lines.

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

        I think we can do a graham scan on the hemisphere. Maybe this works because we know things don't wrap around.

        I haven't gotten AC yet and I don't know how to deal with multiple points on the same great circle :(

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

        To find the hemisphere, first try all hemispheres with $$$p$$$ (some arbitrary point in the input) on border to see if there is one including all input points. (This can be done by sorting all other points by the angles of their projections on the plane with norm $$$p$$$.) If there is not, find the geodesic convex hull of all points except $$$p$$$ (which is possible with the previous sorting) and try one arbitrary point $$$q$$$ on the convex hull. If you still cannot find a hemisphere with $$$q$$$ on border, that means the answer is $$$0$$$.

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

      What's test #5? Didn't manage to pass it and too lazy to spend time on upsolving.

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

        I think test 5 is the first non-trivial case where all points lie strictly in one hemisphere. I got it wrong when my formula for spherical area was wrong and when my convex hull was wrong.

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

      Are two antipodal points considered to be in the same hemisphere?

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

        that's a good question to the problem statement, because it will give drastically different answer for case {(1,0,0),(-1, 0,0)}.

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

        The border of hemisphere is inclusive.

        I'm very sorry we forgot synchronizing some last modifications of statements with statements in Polygon.

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

How to solve J?

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

    Some outline of solution we had

    0) Note that minimum never moves
    1) Iterate over numbers in order of increasing its value and support set of "roots" and its "segments"
    2) If current element $$$a_i$$$ at position $$$i$$$ is not in any of "segments" in the set, it becomes root with a segment of $$$[i-c,i+c]$$$ -- it will never move
    3) If element is in some segment $$$[l, r]$$$ of root and is on the left of the root, then it may get to any position from $$$[l-c, root)$$$ (symmetrical idea for being on the right)
    4) If segments of 2 roots are intersected, all the numbers can get at any position between them (unless mentioned in previous point)
    5) For the segments on the left of the leftmost root and to the right of rightmost root observations are similar.

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

How to solve D?

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

    Hope this can help. I think it's easier for you to read the code than me trying to explain plus minus 1 in the solution. Basically it's dp on subtrees of two types: if we go through all vertices and return and if we go through all vertices and stay in the subtree. The subtrees from which we return can be sorted by the comparator.

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

      Hmm, why is there no special case where you have to return to the root? Like when the answer with no return is 0 and the root has exactly one child. Won't you need to return to the root to cast the spell there (which can make the answer -1)?.

      Nvm, I reread the statement and it seems like we overcomplicated it too much. We did about the same solution and got stuck in details. Thanks.

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

I love geometry! :)

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

    Bonus : Construct a test case that the origin is no more than $$$10^{-16}$$$ away from the convex hull.

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

Problem K about all pair maximum flow seems very interesting. Does anyone know how to solve it?

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

    Find the smallest edge on the outer face. Let it be e Look at its inner face: each min-cut uses either 0 or 2 edges on that face. It's easy to notice that we can always make one of those edges to be e. This means that we can decrease capacity of e to 0 and increase capacities of all other edges on that face by the same amount, and all min-cuts will stay the same. Repeat this process until there are no more cycles. Congrats, we have built Gomory-Hu tree of the graph! Now on tree the problem can be easily solved with Kruskal's algorithm.

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

How to solve L?

→ Reply