OpenCup. GP of Xi'An

4 года назад, # ^ |

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

→ Ответить

dragoon

4 года назад, # ^ |

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 года назад, # ^ |

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

→ Ответить

dragoon

4 года назад, # ^ |

+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 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

kpw29

4 года назад, # |

How to solve H nicely?

→ Ответить

aid

4 года назад, # ^ |

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

→ Ответить

mnaeraxr

4 года назад, # ^ |

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

→ Ответить

BOGDAN_

4 года назад, # ^ |

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

→ Ответить

mnaeraxr

4 года назад, # ^ |

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.

→ Ответить

BOGDAN_

4 года назад, # ^ |

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

→ Ответить

mnaeraxr

4 года назад, # ^ |

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<int,int> 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.

→ Ответить

BOGDAN_

4 года назад, # ^ |

Got it! Thanks

→ Ответить

Tutis

4 года назад, # ^ |

How to solve it not nicely?

→ Ответить

HIR180

4 года назад, # |

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.

→ Ответить

allllekssssa

4 года назад, # |

What is solution for task E ?

→ Ответить

4 года назад, # ^ |

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

→ Ответить

mnbvmar

4 года назад, # |

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

→ Ответить

Um_nik

4 года назад, # ^ |

+31

And you somehow did it in 40 minutes?

→ Ответить

mnbvmar

4 года назад, # ^ |

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

→ Ответить

ksun48

4 года назад, # ^ |

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

→ Ответить

mnbvmar

4 года назад, # |

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 года назад, # ^ |

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 года назад, # ^ |

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?

→ Ответить

Swistakk

4 года назад, # ^ |

"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 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

ehnryx

4 года назад, # ^ |

← Rev. 4 →

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

→ Ответить

xyz2606

4 года назад, # ^ |

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

→ Ответить

zemen

4 года назад, # ^ |

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

→ Ответить

ecnerwala

4 года назад, # ^ |

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.

→ Ответить

ehnryx

4 года назад, # ^ |

+34

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

→ Ответить

4 года назад, # ^ |

+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 года назад, # ^ |

+38

The border of hemisphere is inclusive.

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

→ Ответить

Timur_Sitdikov

4 года назад, # |

How to solve J?

→ Ответить

4 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

4 года назад, # |

+26

How to solve D?

→ Ответить

Kostroma

4 года назад, # ^ |

+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 года назад, # ^ |

← Rev. 3 →

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.

→ Ответить

aid

4 года назад, # |

+56

I love geometry! :)

→ Ответить