### chenjb's blog

By chenjb, history, 6 weeks ago, ,

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

Is there an editorial? MiFaFaOvO

• +66

 » 6 weeks ago, # |   0 Is there anyway to reduce computing partition function to counting the number of perfect matchings?
•  » » 6 weeks ago, # ^ |   0 Or is this not the correct way at all? Anyway, how to solve F?
•  » » » 5 weeks ago, # ^ |   +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.
 » 6 weeks ago, # | ← 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.
•  » » 6 weeks ago, # ^ |   +1 So you can calculate this dp by BST (or priority_queue) in $O(N\log^2N)$ time. Could you elaborate on this?
•  » » » 6 weeks ago, # ^ |   +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
•  » » 6 weeks ago, # ^ |   +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.
•  » » » 6 weeks ago, # ^ |   +144 yep, the contest was too easy this way, you should have asked for all 1..n
•  » » » 6 weeks ago, # ^ |   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.
•  » » » » 6 weeks ago, # ^ |   +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
•  » » » » » 5 weeks ago, # ^ |   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)!
 » 6 weeks ago, # |   +8 How to solve G, E, H, B, J?
•  » » 6 weeks ago, # ^ |   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).
•  » » » 6 weeks ago, # ^ |   +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.
•  » » 6 weeks ago, # ^ |   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.
•  » » 6 weeks ago, # ^ |   +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)$.
•  » » 6 weeks ago, # ^ | ← 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.
•  » » » 6 weeks ago, # ^ |   +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?
•  » » » » 6 weeks ago, # ^ | ← 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.
•  » » » » » 6 weeks ago, # ^ |   +141 This is not the right way of saying this — you should respond "This problem is well known in Poland"
•  » » » » 6 weeks ago, # ^ |   +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.
•  » » » 5 weeks ago, # ^ | ← 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?
•  » » » » 5 weeks ago, # ^ |   +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!
 » 6 weeks ago, # |   +14 How to solve div2 problems I and C
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Div2 was really tough one, almost everyone solved only 1 problem
 » 6 weeks ago, # |   +18 How to solve D? Or in general, how to do lazy update in 2D structure (at least partially)? Is it related to this?
•  » » 6 weeks ago, # ^ | ← 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.
•  » » » 5 weeks ago, # ^ | ← 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. Mapping B to $a_{ij}$ ($N$ queries) By line add queries, add $A_{1i}$ to line $i$ for all $i$ ($\sqrt{N}$ queries) max of column $i$ is corresponded to $AB_{1i}$, therefore we get line $1$ of $AB$ ($\sqrt{N}$ queries) repeat 2, 3
•  » » » » 5 weeks ago, # ^ |   0 Thanks, you made my day
•  » » » » 5 weeks ago, # ^ |   +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.
 » 6 weeks ago, # |   +20 F: the best problem in 2020! (until now).
 » 6 weeks ago, # |   +67 Btw, the problemset is just gorgeous. I definitely want to see more kind of contest like this. Thanks to author!
•  » » 6 weeks ago, # ^ |   +110 Thanks ko_osaga teacher. Let‘s wait for Yuhao Du contest 11.
•  » » » 6 weeks ago, # ^ |   +47 I also enjoy the problems a lot! Can't wait to upsolve them all.
•  » » 5 weeks ago, # ^ |   -17 I hope this is sarcasm.
 » 6 weeks ago, # |   +24 Div1 guys, could you check out div2 problems, please, problems were so good, but i have no idea how to solve them.
•  » » 5 weeks ago, # ^ |   0
 » 6 weeks ago, # |   +28 How to solve L?
 » 5 weeks ago, # |   +7 How to solve div2 A, C, D, I?
•  » » 5 weeks ago, # ^ |   +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.
•  » » » 5 weeks ago, # ^ |   +17 Thanks for editorial! Is there a way to upsolve div2 problems?
•  » » » 3 weeks ago, # ^ |   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?
•  » » » » 3 weeks ago, # ^ |   +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)$.
•  » » » » » 3 weeks ago, # ^ |   0 What do you mean by rotating — rotating point (2 * 1e8, 0) around of center?
•  » » » » » » 3 weeks ago, # ^ |   +3 Yeah.
•  » » » » » » » 3 weeks ago, # ^ |   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?
•  » » » » » » » » 3 weeks ago, # ^ |   +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.
•  » » » » » » » » » 3 weeks ago, # ^ | ← 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)
•  » » » » » » » » » 3 weeks ago, # ^ |   +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.
•  » » » » » » » » » 3 weeks ago, # ^ |   +8 Oh, Thank you! Got it.
 » 5 weeks ago, # | ← Rev. 2 →   +8 How to solve I (Interesting Game) and K (Knowledge-Oriented Problem)?MiFaFaOvO?
 » 5 weeks ago, # |   +9 Will be official editorial for all problems published?