MikeMirzayanov's blog

2014-2015 CT S02E06: Codeforces Trainings Season 2 Episode 6
By MikeMirzayanov, 10 years ago, translation, In English

Because of the Codeforces Round 273 (Div. 2) the training contest 2014-2015 CT S02E06: Codeforces Trainings Season 2 Episode 6 - 2007 Benelux Algorithm Programming Contest (BAPC 2007) will be moved one day forward.

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to register for this?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it -9 Vote: I do not like it

    commented because of being misinformed please ignore

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

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

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

        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.

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

is the statement in English?

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

cant see the contest

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

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

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

How to solve C?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it -19 Vote: I do not like it

    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.

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

How to solve H? Thanks :)

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

    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.

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

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

P.S Thanks to Metamorphus and arystan_kalimov for explanations.

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

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?

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

    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.

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

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

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

Does anyone have the PDF file with solution outlines?

→ Reply