Блог пользователя chenjb

Автор chenjb, история, 4 года назад, По-английски

Gp of Zhejiang is over...Let's discuss solutions. How to solve C?

Is there an editorial? jqdai0815

  • Проголосовать: нравится
  • +66
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there anyway to reduce computing partition function to counting the number of perfect matchings?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Or is this not the correct way at all? Anyway, how to solve F?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      F:

      For a matching, we can add auxiliary edges between vertex $$$2i-1$$$ and $$$2i$$$. Then the graph becomes disjoint cycles and paths. Since $$$2i-1$$$ and $$$2i$$$ must be in the same set, there are at most $$$2^{n/2}$$$ sets. For each set, we can compute the number of paths and cycles in $$$O(2^{n/2} n^2)$$$, and then merge them. The latter part can be also done in $$$O(2^{n/2} n^2)$$$, but $$$O(3^{n/2})$$$ is good enough.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

C:

Consider subtree dp : dp[v][x] = (maximum sum of distance when selecting x vertices in subtree under v)

When updating dp[v] with dp[(children of v)], these facts are important:

  • dp[w][x] (w is a child of v) will increase by (weight of edge v-w) * min(x,k-x)
  • dp[v][*] is convex (it is easy to prove by the fact above)

So you can calculate this dp by BST (or priority_queue) in $$$O(N \log^2 N)$$$ time.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    So you can calculate this dp by BST (or priority_queue) in $$$O(N\log^2N)$$$ time.

    Could you elaborate on this?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      Actually, we should maintain dp[v][x+1]-dp[v][x] instead of dp[v][x].

      If doing so, updating becomes as follows:

      • add edge weight to biggest [k/2] values of children's set
      • add 0 to (k+1)/2 th largest value of it (if k is odd)
      • minus edge weight to other values of it

      After that, we just merge them and done. (we must use small to large technique.)

      This is my code (not well written, though.) https://ideone.com/AmLhRp

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    The intended solution utilizes the combinatorial structure of the answer much more. Maybe I should work harder to come up with a version before the contest that asks the answer for all $$$k=1\dots n$$$.

    Here is a sketch of the intended solution.

    The intended solution is centroid decomposition. Find the $$$k$$$-th farthest vertices of centroid. If some subtree contains more than $$$\frac{k}{2}$$$, move to this subtree. And we do the same thing in the subtree. However, it only works for $$$k$$$ is an even number. For the odd case, we can prove the optimal solution is the optimal solution for $$$k-1$$$ with one more vertex.

    Time complexity is $$$O(n\log^2 n)$$$. We can improve it to $$$O(n\log n)$$$ using nth_element.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +144 Проголосовать: не нравится

      yep, the contest was too easy this way, you should have asked for all 1..n

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Sorry, I do not quite understand.

      You said that if there is a subtree containing more than $$$k/2$$$ $$$k$$$-th farthest vertices, we then move to the subtree and do the same thing. Do you mean we still find the $$$k$$$-th farthest vertices or other parameters instead of $$$k$$$? And I also wonder how do we use the answer for the subtree to help with the original tree? Could you please elaborate on this? Thanks.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        If you fixed the centroid $$$u$$$ of the chosen vertices, we can find the optimal answer by a simple greedy, denoted as $$$f(u)$$$.

        We can prove when $$$k$$$ is even, $$$f(u)$$$ is something like a convex function. So we can move a subtree with the derivative less than $$$0$$$.

        You can read the solution of this problem as a good start.

        Code

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I manage to upsolve this problem! Thank you for the solution and also the reference of the example problem (it really helps me understand the solution of this problem)!

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve G, E, H, B, J?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Our solution for E required too much case work, is it possible to avoid it.

    In G, using hill climbing we manage to get a solution that satisfied the distance among the points, but was not coplanar enough (the best achieved was 5e-18).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      In G, I first set base triples as (999990,999990,0),(-999990,0,999990) and (0,-999990,-999990). Then I try to adjust those 9 coordinates in the range of [x-10,x+10]. Several solutions can be reached when my program runs about 5 minutes.

      Your local checker should be implemented carefully or some precision errors will cause misjudge.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    H: Assume at some point we add $$$l$$$ elements to the left and after that $$$r$$$ elements to the right. When is it better to change order and add $$$r$$$ right elements first and after that $$$l$$$ elements to the left? When the average of right elements is less than the average of left elements. So let's think geometrically: draw 2 polylines: the first one will contain vectors $$$(1, a[i])$$$ for all elements to the left of start in order in which they are added and similar for elements to the right. Compute lower convex hull of both polylines. Each edge of convex hull corresponds to a group of points that will always be added together. Now all we need to do is to calculate for each edge of the first convex hull number of edges in the second convex hull which are greater than it and vice versa. When we change starting point, both convex hulls and the answer can be easily maintained with stacks. Code.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    B:

    For each query of second type add edge between $$$u_p$$$ and $$$v_p$$$ with weight equal to query index. Now answer to query of first type with query index $$$T$$$ is equal to "how many vertices are achievable from vertex $$$u$$$ if we can move only with edges with increasing weights and with weights $$$\le T$$$ (it is good to think about weights as time).

    This can be solved using centroid decomposition. Assume we found centroid $$$r$$$. Let's root tree in $$$r$$$. We will calculate for each query in $$$u$$$ only vertices $$$v$$$ such that simple path pass centroid.

    For each vertex $$$v$$$ compute $$$travel_v$$$ equal to minimum time required to reach centroid from vertex $$$v$$$ and for each edge from $$$p_v$$$ to $$$v$$$ find maximum time when we can leave centroid and reach vertex $$$v$$$ with this edge.

    Now for query in $$$u$$$ with time $$$T$$$ answer is — how many vertices in our tree (except my subtree) has path which starts in centroid after time $$$travel_u$$$ and reaches that vertex before $$$T$$$. It can be done with sweeping technique. Complexity $$$O(N \log ^2 N)$$$.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +56 Проголосовать: не нравится

    J: take the smallest integer $$$q$$$ so that $$$2^q \ge |S|$$$ and consider the finite field $$$\mathbb{F}_{2^q}$$$. Now, for each integer $$$i$$$ from $$$0$$$ to $$$|S| - 1$$$, compute $$$i^3$$$ in this field (call the result $$$f(i)$$$) and output $$$i \cdot 2^q + f(i)$$$ (computed normally in $$$\mathbb{Z}$$$).

    As $$$f(i) \in \mathbb{F}_{2^q}$$$, then $$$f(i) < 2^q$$$ and therefore $$$i \cdot 2^q + f(i) < |S| \cdot 2^q < |S| \cdot 2|S| = 2|S|^2 \le n$$$.

    Now, assume $$$a_{i_1} \oplus a_{j_1} = a_{i_2} \oplus a_{j_2}$$$. It means that $$$i_1 \oplus j_1 = i_2 \oplus j_2$$$ (or, in $$$\mathbb{F}_{2^q}$$$, simply $$$i_1 + j_1 = i_2 + j_2$$$) and $$$i_1^3 - j_1^3 = i_2^3 - j_2^3$$$. As $$$x^3 - y^3 = (x-y)(x^2 + xy + y^2)$$$ (and $$$y = -y$$$ within this field), we have that $$$i_1^2 + i_1j_1 + j_1^2 = i_2^2 + i_2j_2 + j_2^2$$$. Then, $$$(x + y)^2 = x^2 + y^2$$$ within the field, so we also have $$$i_1j_1 = i_2j_2$$$.

    Let $$$s := i_1 + j_1$$$, $$$p := i_1j_1$$$. Now, each of the values $$$i_1$$$, $$$j_1$$$, $$$i_2$$$, $$$j_2$$$ satisfies the polynomial equation $$$x(s - x) = p$$$. This polynomial has degree 2, so it has at most 2 solutions in the field. As $$$i_1 \neq j_1$$$, $$$i_2 \neq j_2$$$ and $$${i_1, j_1} \neq {i_2, j_2}$$$, we arrive at contradiction.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      The explanation is excellent, thank you ...

      but it gives me no clue about how on earth do you get to this result. What was your thought process in this problem?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

        Well, it's quite sad for me to say, but the same idea was used in some local competition in Poland (Wrocław) a few years ago. :( I can't offer much insight on it, apart from it sharing some high-level ideas with no-three-in-line problem.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +141 Проголосовать: не нравится

          This is not the right way of saying this — you should respond "This problem is well known in Poland"

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +18 Проголосовать: не нравится

        I can try to give some insight on how you can get this by yourself. It is of course pretty hard to think like this, but should make it seem slightly less out of nowhere.

        Instead of thinking "what kind of weird construction can give me $$$a_i \oplus a_j \neq a_k \oplus a_l$$$?" think like this "How can I uniquely restore unordered pair $$$(i,j)$$$ from $$$f(i,j)$$$?". If you forget for a second about some xors and binary world, in real numbers you can uniquely restore $$$(i,j)$$$ from $$$(i+j, i^2+j^2)$$$. But how can we adapt this to binary world?

        First thing is that reals are nice field, so (multiplication is important here), so maybe we should think of these binary vectors as field as well, so correct way of thinking could be not adding/multiplying them as numbers corresponding to binary representation, but as elements of finite field on $$$2^k$$$ elements for some $$$k$$$ (you know, these binary polynomials modulo some other irreducible polynomial).

        Second thing is that we would like to encode pair ($$$(i+j,i^2+j^2)$$$) into one vector — just concatenate binary representations of these

        Third thing is that in $$$\mathbb{Z_2}$$$ world squares will not work — but cubes will.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      For multiplication in the finite field $$$\mathbb{F}_{2^q}$$$, we use an irreducible polynomial of degree $$$q$$$.

      I can just brute force through all polynomials, and substitute all values to check for roots (and effectively reducibility), and this takes $$$O(2^{2q})$$$ to find one. In this case it is just $$$O(n)$$$, which fits in the TL.

      Is there a faster method for doing this? Or is there a different way to define multiplication efficiently?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        In this case it's even easier, you simply take a polynomial at random (afair there's something like 1/q chance you pick a correct one), compute a solution modulo this polynomial, check if it's correct, and repeat until you're lucky.

        As for finding the finite field, I don't have a (really) good answer. You can try using random candidates, which requires $$$O(q)$$$ polynomials to check on average instead of $$$O(2^q)$$$, you can also test the irreducibility modulo the polynomials of degree at most $$$q/2$$$ (so that a single test takes $$$O(2^{q/2})$$$ time instead of $$$O(2^q)$$$).

        There are some efficient algorithms factorizing the polynomials over $$$\mathbb{Z}_2$$$ (and various computer algebra systems can handle it really fast), but unfortunately I don't know much about them. If someone does and has a fairly simple explanation of any of them, please let us know!

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

How to solve div2 problems I and C

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

How to solve D? Or in general, how to do lazy update in 2D structure (at least partially)? Is it related to this?

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

    It looks there should be a conditional lower bound (like $$$\Omega(\sqrt{n})$$$) about fully 2D lazy update.

    The intended solution is D&C and sweep line.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +73 Проголосовать: не нравится

      process $$$N$$$ queries for a $$$\sqrt{N} \times \sqrt{N}$$$ matrix $$$a_{ij}$$$:

      • given $$$r, c, x$$$: assign $$$a_{rc} = x$$$
      • given $$$x$$$, $$$r$$$: for all $$$i$$$, $$$a_{ri}$$$ += $$$x$$$
      • given $$$c$$$: print $$$\max_{i} a_{ic}$$$

      A lowerbound of this problem is $$$\Omega^*(N\sqrt{N})$$$ (If we can not solve the all pair shortest path problem in $$$O(N^{2.999})$$$ time. This conjecture is called an APSP conjecture and well-known)

      Under APSP conjecture, we can not do a matrix multiplication in $$$O(N^{2,999})$$$ time over (min, +)-semiring. (Moreover, we can not check AB=C for given matrix A,B,C [Virginia Vassilevska Williams and Ryan Williams. Subcubic Equivalences Between Path, Matrix, and Triangle Problems])

      However, we can calculate a matrix product of $$$\sqrt{N} \times \sqrt{N}$$$ matrices by above problem.

      1. Mapping B to $$$a_{ij}$$$ ($$$N$$$ queries)
      2. By line add queries, add $$$A_{1i}$$$ to line $$$i$$$ for all $$$i$$$ ($$$\sqrt{N}$$$ queries)
      3. max of column $$$i$$$ is corresponded to $$$AB_{1i}$$$, therefore we get line $$$1$$$ of $$$AB$$$ ($$$\sqrt{N}$$$ queries)
      4. repeat 2, 3
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks, you made my day

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Wow, I was always interested whether it's possible to perform such queries in $$$o(n^{0.5 - \epsilon})$$$ time and the reduction to famous APSP problem is so simple and beautiful.

        You made my day too, that's really cool.

»
4 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

F: the best problem in 2020! (until now).

»
4 года назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

Btw, the problemset is just gorgeous. I definitely want to see more kind of contest like this. Thanks to author!

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Div1 guys, could you check out div2 problems, please, problems were so good, but i have no idea how to solve them.

»
4 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

How to solve L?

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

How to solve div2 A, C, D, I?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Tutorial slides: http://acm.math.spbu.ru/trains/191215.slides.en.pdf.
    Best viewed one per page, otherwise scrolling will be nonsensical.
    Feel free to ask more specific questions if the solutions outlined in the slides are not clear.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      Thanks for editorial! Is there a way to upsolve div2 problems?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I have no idea why for problem C we can't just check square of size at most 2 — 3 centimetres around of the point M and and there will certainly be an answer in it?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Consider a circle with center $$$(0, 0)$$$ and radius $$$10^8$$$.
        Measure the distance from point $$$(2 \cdot 10^8, 0)$$$ to the points on the circle. If we go to $$$(10^8, 0)$$$, the distance is just $$$10^8$$$.
        If we go to $$$(10^8 - \varepsilon, 100)$$$, with $$$\varepsilon$$$ such that the point is on the circle, the distance is very much like $$$10^8$$$ still.
        Consider then rotating the picture slightly, then the image of $$$(10^8 - \varepsilon, 100)$$$ may well be closer to an integer point than the image of $$$(10^8, 0)$$$.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          What do you mean by rotating — rotating point (2 * 1e8, 0) around of center?

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            Yeah.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              But point M(point — intersection between line between given point and center and circle) will also change -> square also change -> and probably point (1e8 — e, 100) will be answer?

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится

                Alright, my example was a bit off. A more practical one, here. The idea is the same.

                Input:

                7
                0 0 100000000 200000000 0
                0 0 100000000 200000000 1
                0 0 100000000 200000000 10
                0 0 100000000 200000000 100
                0 0 100000000 200000000 1000
                0 0 100000000 200000000 10000
                0 0 100000000 200000000 100000
                

                Output:

                1
                200000000 0 100000000 0
                1
                200000000 1 100000000 0
                1
                200000000 10 100000000 0
                1
                200000000 100 100000000 0
                1
                200000000 1000 100000000 0
                1
                200000000 10000 100000000 0
                1
                200000000 100000 99999987 50990
                

                See, with a shift up to $$$10^4$$$ (asymptotically), it is still best to arrive at $$$(10^8, 0)$$$, which is then $$$5000$$$ away from the intersection point.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  Still can't get it:( It would be great, if you show me on the cell field, where I am wrong(if it is possible)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится

                  Alright.

                  Go to https://csacademy.com/app/geometry_widget/, and enter the following:

                  Circle 0 0 100
                  0 0
                  100 0
                  200 10
                  Segment 200 10 100 0
                  Segment 100 0 0 0
                  Segment 200 10 0 0
                  

                  Click "View all", then use dragging and mouse wheel to zoom in.

                  You can see that the optimal path, $$$(200, 10) \to (100, 0)$$$, is 5 cells away from the intersection point already.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится

                  Oh, Thank you! Got it.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

How to solve I (Interesting Game) and K (Knowledge-Oriented Problem)?
jqdai0815?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    jqdai0815 pls help D:

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +28 Проголосовать: не нравится

      Tutorial of I in Chinese

      K: Basically the graph is the Cartisent product of $$$G$$$ and a path graph $$$P_n$$$. The number of spanning tree $$$G$$$ is $$$\frac{1}{n} \prod_{i=1}^{n-1} \lambda_i$$$ where $$$\lambda_i$$$ is the eigenvalue of the Laplacian matrix of $$$G$$$.

      There is a lemma that the eigenvalue of the Cartisent product of $$$G_1$$$ and $$$G_2$$$ is $$$\lambda_i + \mu_j$$$ where $$$\lambda_i$$$ and $$$\mu_j$$$ is the eigenvalue of $$$G_1$$$ and $$$G_2$$$ respectively. Let $$$L(G,x)$$$ be the characteristic polynomial of the Laplacian matrix of $$$G$$$. This can be viewed as the resultant of $$$L(G_1, x)$$$ and $$$L(G_2,-x)$$$.

      Let $$$P_n(x) = L(P_n, x)$$$, $$$Q(x)=L(G,x)$$$. We know $$$\mathrm{res}(P_n, Q) = \mathrm{res} (P_n\bmod Q, Q)$$$. So we only need to compute $$$P_n \bmod Q$$$. There is a linear recurrence for $$$P_n(x)$$$ where $$$P_n=(x+2) P_{n-1}- P_{n-2}$$$, thus it can be computed in $$$O(\log n |Q|^2)$$$.

      The characteristic polynomial of a matrix can be computed in $$$O(n^3)$$$, and resultant can be computed in $$$O(n^2)$$$.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Will be official editorial for all problems published?