№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
3 | adamant | 156 |
5 | cry | 155 |
5 | atcoder_official | 155 |
5 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Название |
---|
I don't think so. Informally, you can first place K-1 dominoes in any way you like. Then, if there are two adjacent spots that are both free, you can place the last domino there without decreasing the score. Otherwise, all empty spots are isolated. Pick any two 1x1 spots, then you would like to find a path of adjacent dominoes between these spots that you can 'shift', i.e. do the following operation:
.AABBCC. => XXAABBCC
The question is whether such a path always exists, because it's not always a trivial shortest path, e.g. (where the ? are irrelevant):
Here you cannot pick some shortest path between the two empty spots, so you would need some other route. I can even find an example where there is no path possible between two empty spots (forgetting for a moment that we need an NxN square):
I'm pretty sure there is no "flip path" between the two empty spots on the second row. But of course there are other empty spots (after all, if there were only two empty spots, then 2(K - 1) = N2 - 2, so, 2K = N2, and you can just cover everything), so you'd have to proof that some path always exists.
EDIT: Oh, the rest of the proof is actually quite simple. Try thinking in bipartite graphs :)
I am unable to solve problem C from NEERC, the Cactus Jubilee.
It is clear that what we have to do is essentially find all bridges and compute all cycle lengths and the edges part of every cycle. After that, I think we would have to union the set of disconnected components for finding number of changes to a bridge edge, and for cycle edges, do something similar. But I'm unable to figure out how to do this efficiently. Something to do all this in linear time is something I'm unable to figure out. Please help with clues/ideas.