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

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

Hi all,

join us on the fifth round which will be held on Saturday, February 8th at 14:00 UTC.

If you are not familiar with the COCI contest format, we encourage you to read the announcement for the new season. You can also find the problems from the previous rounds here.

Feel free to discuss the problems in the comment section after the contest ends.

See you on Saturday!

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

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

How do you solve problem 'Matching' faster than $$$N^2$$$?

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

    Build a graph of adjacent guys, deal with degree 1 vertices, and then check that all cycles are even.

    After that, quadratic solution is just two-sat, because for each cycle there are only two possible shifts.

    To optimize this solution, you can build a two-sat graph more efficiently using sweep line and persistent segment tree, similar to this problem: link

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

      2sat is more like dsu in this case, because any 2 intersecting segments just means that all involved vertices should have their segments in the same direction

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

        I don't think this is true. There are cases where two points A and B are allowed to have A vertical and B horizontal, but not A horizontal and B vertical.

        Here's a case that should illustrate this:

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

          I think I was not clear. My solution is as follows — consider all intersecting pairs. I postulate that all 4 involved vertices should have the same orientation. Also any 2 vertices with same coordinate should have the same orientation. So now we have some sets of vertices that all have same orientation. Now for some vertices we know that they should have vertical segment (because no other vertex have same y) or we know that it should have horizontal segment. If some set have vertices of both this types, answer is NE. If only one — we should direct all segments in the set in corresponding direction. If all vertices in the set can be connected either way — we can arbitrary select which way we will connect

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

          In other words, all conditions in the problem lead to 3 kind of equivalences:

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

    This post could be helpful.

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

      There is a relatively simple way of building the graph.

      For a segment S, let C[s] denote it's component.

      Do a sweep from left to right and maintain a segment tree for y-coordinates:

      1. a horizontal segment can become active/inactive, mark that position in segment tree with C[s]

      2. merge a vertical segment with all horizontal segments which are active and intersect it

      For 2, query the minimum and maximum in the interval and while they are different merge one of them with the vertical segment. The merges can be done small-to-large. The total complexity is O(N log^2 N) because when merging we also update the segment tree.

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

    Btw I used sqrt decomposition, and it passed after fixing stupid bug

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

You can solve all the problems here: https://oj.uz/problems/source/446