snarknews's blog

OpenCup GP of Eastern Europe
By snarknews, history, 8 years ago, translation, In English

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:

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

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been translated by snarknews (original revision, translated revision, compare)

→ Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

How to register? Where to get login password?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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 a be 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 b be 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?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This test:

      2 3
OXO
...
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve I and D?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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(yi) = N.

    I: If you pick (0, yi) as one point on the line, you can find in linear time the optimal point (xi, 0) by computing the point with the minimum slope. You can then ternary search for the yi which gives the minimum length.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    My solution is deterministic and is a DFS.

    The relevant state information to keep track of is:

    • How many cards of each suit do we still need to play from.
    • Which cards have explicitly been used.
    • The last card in our ordering.

    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.

    → Reply