Блог пользователя snarknews

Автор snarknews, история, 8 лет назад, По-русски

По непонятной пока причине упал сайт opencup.ru (проблемы у провайдера).

Старт был сдвинут на 11:30

Ссылка для команд первого дивизиона на вход:

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

Ссылка на условия Div1:

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

Вход в Div2:

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

Ссылка на условия Div2:

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

Так как на Div2 проходят два четвертьфинала, то русскоязычных условий в этот раз не предоставляется.

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

А есть ли ссылка на 2ой дивизион?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Сейчас всё будет, сайт свалился за 10 мин до старта (.

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем snarknews (предыдущая версия, новая версия, сравнить).

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

А как отправлять решения? в яндекс.контест не пускает.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем snarknews (предыдущая версия, новая версия, сравнить).

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Check failed на D. Это системное?

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

How to register? Where to get login password?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    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?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How to solve I and D?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Планируется ли добавить дорешивание Гран-при Сибири и сегодняшнего контеста ?