### bukefala's blog

By bukefala, history, 10 months ago, ,

Dear friends,

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

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

•
• +45
•

 » 10 months ago, # |   +31 Solution for problem 160: Simply use bitset.
•  » » 10 months ago, # ^ |   +39 We have tried so hard to prepare this contest and now you've ruined it for everyone! Thanks a bunch...
 » 10 months ago, # |   +18 Lol. The last problem is a simpler version of my own. https://www.codechef.com/problems/HAMILG
•  » » 10 months ago, # ^ |   +3 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 :).
•  » » » 10 months ago, # ^ |   +2 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.
•  » » 10 months ago, # ^ |   +6
 » 10 months ago, # |   +1 How to solve 140?P.S. No bitset allowed.
•  » » 10 months ago, # ^ |   +6 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).
•  » » » 10 months ago, # ^ |   +16 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.
 » 10 months ago, # | ← Rev. 2 →   +5 How to solve Spiral and Birokracija ? I know only 50% solutions for this problems .
•  » » 10 months ago, # ^ |   +8 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
•  » » » 10 months ago, # ^ |   +10 is it a simple dfs solution ?
•  » » » » 10 months ago, # ^ |   +9 Yeah
•  » » 10 months ago, # ^ |   +9 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.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +6 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 
•  » » » » 10 months ago, # ^ |   +9 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.
•  » » » » » 10 months ago, # ^ |   +6 i understand ,thanks!
 » 10 months ago, # |   +61 I've written an analysis for all the problems on my blog: http://blog.brucemerry.org.za/2018/01/coci-20172018-r5-analysis.html
 » 8 months ago, # | ← Rev. 2 →   0 To those problem with special judge,where should I go to download it?