chenjb's blog

XX Open Cup: GP of Zhejiang
By chenjb, history, 5 years ago, In English

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

Is there an editorial? jqdai0815

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

Comments Comments (53)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

      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.

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

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.

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

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

    Could you elaborate on this?

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

      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

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

    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.

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

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

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

      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.

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

        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

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

          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)!

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

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

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

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

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

      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.

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

    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.

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

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

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

    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.

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

      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?

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

        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.

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

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

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

        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.

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

      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?

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

        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!

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

How to solve div2 problems I and C

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

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

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

    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.

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

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

        Thanks, you made my day

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

        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.

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

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

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

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

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

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

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

How to solve L?

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

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

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

    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.

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

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

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

      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?

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

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

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

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

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

            Yeah.

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

              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?

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

                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.

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

                  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)

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

                  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.

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

                  Oh, Thank you! Got it.

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

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

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

    jqdai0815 pls help D:

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

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

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

Will be official editorial for all problems published?

→ Reply