Just google a formula for flipping a point over a line

I did that + realize that the pattern depends on the parity of N, so just make a program to print all ranges of answers and then submit a hardcoded solution (because of troubles with ML)

I also got this fact. Also I noticed that we can use ternary search to get the answer. However, for C = 2e5 my solution worked for about 5 — 6 seconds.

I would also mention that 1) we need only two 2000x2000 arrays instead of 4000x4000 (therefore my custom complex<double> was perfectly fine in terms of memory), and 2) we can do only one multiplication, if we assign $$$1$$$, $$$i$$$, and $$$1+i$$$ to cells ., # and _ of the board, and $$$1$$$, $$$-i$$$, and $$$0$$$ to these cells of the vault.

What do you mean by robust? We are working in $$$\mathbb{Z}_7$$$, so there are no precision problems

I was iteratively adjusting the points, each adjustment of a single point was some binary search. However, it costed me +20 to find proper number of iterations of each and I do not think it was intended.

What we did was the following:

First, choose MAGIC points on each circle and choose the best route in O(n * MAGIC^2). Now near each of the points on the optimal path choose MAGIC points again and find the optimal path again.

We did gradient descent to find the optimal route. Each point was parametrised with the angle. However, this solution was very prone to converge to local optimum instead of global optimum if angles were not initialised properly.

The last initialisation that worked for us was finding the optimal point in the circle if only the previous and next circles were relevants. Circles in the endpoints were initialised pointing the adjacent circle.

The "official" solution is to take $$$K$$$ samples on each circle, and compute minimum distance through them using $$$O(N K^2)$$$ dynamic programming. Quite importantly, the case of $$$N = 2$$$ must be considered analytically. For $$$N \gt = 3$$$ it can be proved that relative error of sampling solution does not exceed $$$\Theta(1 / K)$$$ with some constant. Taking $$$K = 2500$$$ should provably suffice, although even something as low as $$$K = 200$$$ passes due to smooth nature of the distance function.

Also, circular shape is too nice to stop various local searches from getting ACCEPTED. I personally implemented one with randomly perturbing polar angle on random circle many times.

My AC solution, you can try to stress with it.

You replace each a[i] with a[i]*i! and do the trie solution. The answer is len(poly1) + len(poly2) — 2 * len(common suffix)

You have a vector $$$v = (a, b)$$$, so consider point $$$P = \frac{v}{||v||} \cdot r$$$ first. This is the point giving maximum dot product, but it is real-valued. Let's round both its coordinates down to integers, and you'll get some pretty good point $$$Q$$$, which gives initial estimate on the goal function.

Which points can be better than $$$Q$$$? Draw a line passing through $$$Q$$$ normal to $$$v$$$, it will cut a thin segment from the circle. The integer points in this segment are better than the initial record. The thickness of the segment is $$$O(1)$$$, so it contains at most $$$O(\sqrt{R})$$$ integer points. Iterate through all of them and find the best one — that would be the answer.

The remaining is technical details. Usually you find $$$X_{min}$$$ and $$$X_{max}$$$ bounding the segment (e.g. compute angle of the segment from thickness and radius, then find min/max points), then iterate through all $$$X \in [X_{min} \ldots X_{max}]$$$, and check $$$Y = \sqrt{R^2 - X^2}$$$ for each of them. Just note that double precision is not enough to compute such $$$Y$$$ precisely, so you might need plus/minor one adjustments.

Here are some hints.