By riadwaw, history, 4 years ago,

Let's discuss problems.

How to solve B, F?

• +52

 » 4 years ago, # |   +3 Was the TL too tight for C? My soln was 15nlogn and it barely passed with 0.9x second.
•  » » 4 years ago, # ^ |   +16 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.
•  » » » 4 years ago, # ^ |   0 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.
•  » » » » 4 years ago, # ^ |   0 Can you tell that solution please? We could only come up with a nlognlogk one, which obviously needed some heavy optimizations to pass.
•  » » » » » 4 years ago, # ^ |   +16 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).
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 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$.
•  » » » 4 weeks ago, # ^ |   0 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?
 » 4 years ago, # |   0 How to solve H nicely?
•  » » 4 years ago, # ^ |   +23 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.
•  » » » 4 years ago, # ^ |   +24 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.
•  » » » 4 years ago, # ^ |   0 But how you determine by 2 elements in progression q and p?
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » » » 4 years ago, # ^ |   0 Tell me please in detail about linear DP. I found something only with n*logn complexity.
•  » » » » » » 4 years ago, # ^ |   0 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 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.
•  » » » » » » » 4 years ago, # ^ |   0 Got it! Thanks
•  » » 4 years ago, # ^ |   +8 How to solve it not nicely?
 » 4 years ago, # |   +8 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.
 » 4 years ago, # |   0 What is solution for task E ?
•  » » 4 years ago, # ^ |   +16 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.
 » 4 years ago, # | ← Rev. 2 →   +85 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$.
•  » » 4 years ago, # ^ |   +31 And you somehow did it in 40 minutes?
•  » » » 4 years ago, # ^ |   +26 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).
•  » » » 4 years ago, # ^ |   +13 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. :)
 » 4 years ago, # |   0 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?
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 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?
•  » » » » 4 years ago, # ^ |   0 "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.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   +8 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 :(
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +10 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$.
•  » » » 4 years ago, # ^ |   0 What's test #5? Didn't manage to pass it and too lazy to spend time on upsolving.
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   +34 Are two antipodal points considered to be in the same hemisphere?
•  » » » » 4 years ago, # ^ |   +10 that's a good question to the problem statement, because it will give drastically different answer for case {(1,0,0),(-1, 0,0)}.
•  » » » » 4 years ago, # ^ |   +38 The border of hemisphere is inclusive.I'm very sorry we forgot synchronizing some last modifications of statements with statements in Polygon.
 » 4 years ago, # |   0 How to solve J?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 Some outline of solution we had0) Note that minimum never moves1) 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 move3) 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.
 » 4 years ago, # |   +26 How to solve D?
•  » » 4 years ago, # ^ |   +16 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.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 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.
 » 4 years ago, # |   +56 I love geometry! :)
•  » » 4 years ago, # ^ |   +20 Bonus : Construct a test case that the origin is no more than $10^{-16}$ away from the convex hull.
 » 4 years ago, # |   +11 Problem K about all pair maximum flow seems very interesting. Does anyone know how to solve it?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » 4 years ago, # ^ |   0 Thanks!
 » 3 years ago, # |   +8 How to solve L?