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

Автор MikeMirzayanov, 10 лет назад, По-русски
  • Проголосовать: нравится
  • +66
  • Проголосовать: не нравится

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

How to register for this?

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

    commented because of being misinformed please ignore

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

      Before registration: 10+ hours. Before contest: 16+ hours. Everyone has to register, but the registration will open 6 hours before the contest.

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

        Xellos i apologize but what i meant was that one can register for the contest even during the contest is going on. I should have said that there is no prior registration deadline my bad, sorry again.

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

is the statement in English?

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

cant see the contest

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

in russian interface i can see the gym contest but on the english one i can't

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

How to solve C?

  • »
    »
    10 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится -19 Проголосовать: не нравится

    For C: First you need to make everything integers. Do this by multiply everything with 100. Now, because dividing the notes by 2 is always better, let's just do that. --> Then the problem becomes, given a set of notes, check if you can use these notes to make certain sum (note that you can subtract). In math, this is check if an integer S can be represented as:

    x1 * c1 + x2 * c2 + ...

    for some constants c1, c2, ...

    Now this is application of congruence equation, which to check if there is a solution, you just need to check if everything is divisible by gcd.

    Edit: I mistakenly write solution for E here. (and get -10 :( )

    For E: use inclusion exclusion principle and bitmask to iterate over all sets.

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

How to solve H? Thanks :)

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

    Let's create a set of interesting points. We add to this set start and end points. Also let's consider all pairs of towers. Let's look at intersection points of two circles with centers in this towers. If such point isn't covered by any other circle, we add it to our set.

    Now for each pair of points in set we should find if we can go directly between them. So we just intersect this segment with all circles and look if all points in this segment is covered by at least one circle.

    And now we can use dijkstra on this points to find a shortest distance.

    P. S. I don't know how to prove that this algorithm works/works fast enough.

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

Can somebody explain why groningen is the second in a sample in I?

P.S Thanks to Metamorphus and arystan_kalimov for explanations.

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

How to solve A? It seemed like we had to store cumulative weights over paths and then use lowest common ancestor. Can someone share their code?

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

    It is simpler than that ... It is just every edge in the tree acts like a bridge dividing the tree into to disconnected parts ... So the path from any node in the first part to any node in the second part will use that edge.

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

My solution for most problem + qwerty787788's solution for H (copy from comment above just for completeness: link

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

Does anyone have the PDF file with solution outlines?