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
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
Solution for problem 160: Simply use bitset.
We have tried so hard to prepare this contest and now you've ruined it for everyone! Thanks a bunch...
Lol. The last problem is a simpler version of my own. https://www.codechef.com/problems/HAMILG
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 :).
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.
How to solve 140?
P.S. No bitset allowed.
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).
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.
How to solve Spiral and Birokracija ? I know only 50% solutions for this problems .
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
is it a simple dfs solution ?
Yeah
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.
can you show a example on the picture for your algorithm ? example for this test:
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.
i understand ,thanks!
I've written an analysis for all the problems on my blog: http://blog.brucemerry.org.za/2018/01/coci-20172018-r5-analysis.html
To those problem with special judge,where should I go to download it?
@ipaljak