By some reason opencup.ru seem to be down.

Div1 Entry link:

https://official.contest.yandex.ru/opencupXVII/contest/3268

Statement link:

http://opentrains.snarknews.info//upload/div1.pdf

Div2:

http://opentrains.snarknews.info//team.cgi?contest_id=10366

Statements:

Auto comment: topic has been translated by snarknews (original revision, translated revision, compare)Auto comment: topic has been updated by snarknews (previous revision, new revision, compare).Auto comment: topic has been updated by snarknews (previous revision, new revision, compare).How to register? Where to get login password?

So, I googled a lot and found the 'sector' thing. Certainly I can see the problems now. I just want a place where I can upsolve the problems. Even upsolving for all(after the contest has ended) cannot be implemented on opencup.ru? @snarknews

How to solve F?

First ignore 'X' and consider the shortest fence that surrounds all 'O's. When there are multiple possibilities find the one with minimum area. Let

abe the length of this fence.Then find the shortest path from 'X' to some cell outside the fence that doesn't pass through any 'O' cells. Let

bbe the length of this path.Except for some special cases we can construct a valid fence of length

a+ 2b. Though I'm not sure why this is always optimal — does anyone has a proof?This test:

Yes that's the special case. (The bounding box of 'O's is 1xn)

How to solve I and D?

D: Assume without loss of generality that you're looking for the optimal rectangle containing the origin (you can reflect the rectangle to handle all four corners). Sort the points by x-coordinate, and discretize the y-coordinates. Looping over the x-coordinates from left to right, you can store the corresponding y-coordinates in a BIT, and then query for the minimum index in the BIT where 2 *

query(y_{ i}) =N.I: If you pick (0,

y_{ i}) as one point on the line, you can find in linear time the optimal point (x_{ i}, 0) by computing the point with the minimum slope. You can then ternary search for they_{ i}which gives the minimum length.Thanks!

You can build a convex hull of {input points + (0; 0) point}, then check for every point in this hull(except (0; 0)) what is the minimum length(via ternary search or math and derivatives). Of course there's no possible answer for some point, just skip them. Note that there's no more than O(10^4) points in convex hull, 'cause all cooridinates are <= 10^4, so this is like O(n*log(n) + 10^4 * C), where C is ternary search precision.

Has anyone got a deterministic solution for A? (Randomwalking 7000 times worked for me, but that seems like to cheap of a solution.)

My solution is deterministic and is a DFS.

The relevant state information to keep track of is:

In our DFS, we only care about transitions between suits. If it is possible for us to play more than one card in a suit before transitioning to a different suit, then the suit is "resolved". We initiate the DFS by considering all pairs of cards with the same value (and resolving the suit of the first card in the pair).

The base case of the DFS is when we have already played all cards from each suit, or if we have resolved all suits. Note that the last card in the ordering can resolve that suit if it is the final suit transition that we do.

Otherwise, you are stuck in some suit. You may either transition immediately to another suit, which does not resolve the current suit, or you can play a different value in that suit and then transition to another suit, which does resolve the current suit.

Finally, you can cap the DFS to depth at most 5, since there is no point in transitioning between resolved suits too many times.