ipaljak's blog

Croatian Open Competition in Informatics (COCI) 2019/2020 — Round #5
By ipaljak, history, 4 years ago, In English

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!

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

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Didn't happened, sad :(

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

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

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

    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

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

      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

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

        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
        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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

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

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

          • a_i = a_j
          • a_i = false
          • a_i = true
          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    This post could be helpful.

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

      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.

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

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

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

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

→ Reply