bukefala's blog

COCI 2017/2018 round 5
By bukefala, history, 7 years ago, In English

Dear friends,

Come and show your skills on the 5th round of this year's COCI!

Click here to see when the coding begins in your timezone.

Pro tip for the contest: make clever use of the biggest monster in the current programming scene -> bitset. It is almost so good that it should be banned from competitions.

Thank you

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

»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Solution for problem 160: Simply use bitset.

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

    We have tried so hard to prepare this contest and now you've ruined it for everyone! Thanks a bunch...

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

Lol. The last problem is a simpler version of my own. https://www.codechef.com/problems/HAMILG

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

    Do you mind elaborating on your solution? Also I'm wondering how the graph being bipartite helps the computation, but I wouldn't mind if you'll just explain the solution to your own problem.

    Thanks :).

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

      The solution is basically: find a maximum matching, then find vertices at the end of an alternating path from some unmatched vertex (in the first partition). In this case, the first part is maxflow and the second part one BFS from the source, since all alternating paths from unmatched vertices can be extended to start in the source.

      In my problem, maximum matching is much harder to compute; the second part is O(N) times BFS, but otherwise the same.

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

    Hi , so to me seems like a notorious coincidence.

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

How to solve 140?

P.S. No bitset allowed.

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

    First, note that we only need to add edges between city pairs (a, ba) where a and b are integers. There are only such edges. Then, we can efficiently simulate the process using a disjoint set data structure. Finally, I used parallel binary search to process the queries (there are also other ways).

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

      A much simpler way to process queries is to build a spanning tree with depth during the DSU algorithm, where we add edges from the root of a smaller subtree to the root of a larger one, and edge weights correspond to the time when they're created. Processing queries online with this is just brute force.

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

How to solve Spiral and Birokracija ? I know only 50% solutions for this problems .

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

    Birokracija: for each child of a node, add the child's money + the number of nodes in the child's subtree to the current node

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

    Spiral: do a spiral around each starting position, the number that will fill up the whole array is not greater than 51*51 so the complexity is 50^4 which is under the TL limit.

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

      can you show a example on the picture for your algorithm ? example for this test:

      5 5 3
2 2 1
2 3 0
3 3 0
      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Well for the first query, you will start a spiral and mark all those which are not visited with the current count, basically just do a spiral, if it is not visited set that element of the matrix to be equal to the value in the spiral, wherever you put the spiral it must go through the whole matrix in 100*100 (I think this is the right value, the one above is not correct).

        You end when the counter is over 100*100, or 101*101 if you want to be safer.

        For the second query you do the same thing, if you somehow see an element which is not visited you just give it the value of the spiral, otherwise if it was already visited you check if the value of the spiral is smaller than the current value in the matrix. If it is then you set the value of the matrix to be equal to the value of the spiral and repeat.

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

I've written an analysis for all the problems on my blog: http://blog.brucemerry.org.za/2018/01/coci-20172018-r5-analysis.html

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

To those problem with special judge,where should I go to download it?

@ipaljak

→ Reply