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

Автор mango_lassi, история, 5 лет назад, По-английски

The 2019 NWERC (Northwestern European regional contest) is tomorrow. You should see the scoreboard here once the contest starts.

There will be an online mirror here.

Let's discuss the problems after the contest!

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

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

The contest starts in 20 minutes, the online mirror starts in 50.

There will also be a live stream on ICPC Live

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

How to solve B, D, H, J and K?

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

    J: Make a segment tree that tells us for every interval how many removals we need to make to make that interval of posts into a alternating sequence that starts with negative / positive and ends with negative/positive. Combining this information is trivial.

    Initially each post must either be deleted or have the sign it initially has. Loop the amount of new accounts we create, when the number of accounts goes over $$$abs(votes_i)$$$, that position in the segment tree can now have any sign, so we update it. Every position gets updated at most once, and the segment tree operations work in $$$O(\log n)$$$, so that's our time complexity.

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

    D: For each edge count, find the shortest path with exactly this many edges when ignoring the constant x that is added to each edge. The actual length of such a path is then a line equation in terms of x. You then need to find all the lines which are minimal for at least one value (kind of like in the convex hull trick). Finally you need to find all the vertices which are on at least one of these paths.

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

    You can also see the solution presentation if you skip back in the live broadcast.

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

Did anybody manage to solve B?

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

    Idk if my solution is correct, but I did manage to squeeze it in 4s

    solution

    I maintained all possible subtree sizes with a specific height by a vector of intervals. To get lexicographically smallest subtree I just checked if a specific prefix is possible. This needs some nasty optimizations because in almost all cases dp value is just one interval, but not always. Can anyone find a counter test for my solution?

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

    I tried to write $$$O(n\log n)$$$ and got WA, but $$$O(n\log^2n)$$$ passes easily anyways. Designate a set of nodes such that none of them may be erased, and try adding nodes to this set in DFS order. After adding a node to the set, test whether the minimum possible size of a BBST containing all nodes in the set has size at most $$$k;$$$ if not, remove the node from the set.

    Code

    UPDATE: Here's $$$O(n\log n)$$$ (apparently it's slower tho lol)

    Code

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

What did happen with Oxford team ? They had 5 harder before frozen, and currently they are not on the leaderboard.

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

Will this contest be put into gym/opentrains for virtual participation?