Let's discuss problems.

How to solve B, F?

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 210 |

2 | awoo | 188 |

3 | Errichto | 186 |

3 | rng_58 | 186 |

5 | SecondThread | 182 |

6 | Um_nik | 176 |

6 | Ashishgup | 176 |

8 | maroonrk | 172 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 169 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/07/2021 10:58:50 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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.

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.

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

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

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

How to solve H nicely?

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.

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.

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

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.

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

Ohh, it just using unordered_map instead of map.

Read full solution here.

Got it! Thanks

How to solve it not nicely?

B:

write naive solution, and find the pattern is

n choose i*m choose (i+(m-n+1)/2)*coef.you can find

coefby comparing sum over i with (n+m) choose n. I thinkcoefcan 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.

What is solution for task E ?

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.

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:

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

And you somehow did it in 40 minutes?

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

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

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?

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.

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?

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

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.

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 :(

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

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

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.

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

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

The border of hemisphere is inclusive.

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

How to solve J?

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.

How to solve D?

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.

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

I love geometry! :)

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

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

Thanks!

How to solve L?