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

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

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

How to register for this?

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

is the statement in English?

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

cant see the contest

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

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

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

How to solve C?

  • »
    »
    12 лет назад, скрыть # ^ |
    ← 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.

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

How to solve H? Thanks :)

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.

»
12 лет назад, скрыть # |
← 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.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 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?

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

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

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

Does anyone have the PDF file with solution outlines?