pllk's blog

By pllk, history, 5 years ago, In English

The Nordic Collegiate Programming Contest (NCPC) 2019 will be held tomorrow. It is the subregional ICPC contest for Denmark, Estonia, Finland, Iceland, Norway, and Sweden.

There will also be an open contest in which anyone can participate. The open contest will begin at the same time as the official contest, Saturday October 5 UTC 9:00, and its duration is five hours.

Welcome! You can also discuss the problems here after the contest.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Reminder: The contest will start soon

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Testcase for Problem F:
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve J?

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

    For each kid, order their preferences of the toys by the time when they started to play with it.

    For each toy, order its preferences of the kids by the duration the kid played with the toy (smallest to largest) because choosing the kid with the larger duration increases the chances another kid will envy them.

    Now this can be modeled as a stable matching problem with indifferences (https://en.wikipedia.org/wiki/Stable_marriage_with_indifference).

»
5 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

How to solve G (Game of Gnomes) and F ?

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

    G:

    Observation 1: If you have $$$x = a \cdot k + r$$$ gnomes in a group, then you can imagine splitting it up into $$$a$$$ groups of size $$$k$$$ and one group of size $$$r$$$. This leads to this equivalent problem: We have $$$g$$$ groups of size exactly $$$k$$$ (for some $$$g$$$), and $$$m$$$ groups of size $$$< k$$$. This equivalent problem is easier because the enemy can take out one group in one move.

    Observation 2: The enemys strategy will be to take out the larger groups first.

    Observation 3: It is optimal to distribute the $$$m$$$ smaller groups as evenly as possible. So there are only three distinct group sizes and the answer for a fixed $$$g$$$ is three arithmetic sums which can be evaluated in $$$O(1)$$$.

    Observation 4: $$$g$$$ is between $$$n/k - m$$$ and $$$n/k$$$, so we can try all $$$m$$$ of them and solve the problem in $$$O(m)$$$.

    Challenge: Can you solve it for $$$n,m,k < 10^{12}$$$ ?

    Challenge: What about even bigger $$$n,m,k$$$ (let's say $$$10^{100}$$$) ?

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

    F:

    There are many solutions for this, here is one:

    We want to find all the unknown leaves, after that we can easily get the rest. The unknown non-leaves are quite useless, they can actually be removed from the tree. So remove them and let their children become children of the parent of the vertex you removed. After this is done we will have a tree (actually a forest since the root may be unknown) where the only unknown vertices are leaves. This situation is much easier to deal with. Go through all non-leaves of this reduced tree, you will get three cases:

    1) All the children are known. Here you don't need to do anything.

    2) Exactly one child is unknown. The unknown child must be the value of the root minus the sum of the other children.

    3) More than one child is unknown, but the only possibility is that all of them have flow $$$1$$$.

    In any other case, the answer is impossible. So after this, you can add back the removed vertices, find their flows, and check that the solution is valid, and you're done.

    I hope this is somewhat clear, otherwise we have some completely different solutions one of which is described in the solution slides that will be available at some point at https://nordic.icpc.io/ncpc2019/ .