Petr's blog

A week during NEERC
By Petr, history, 9 years ago, In English

http://petr-mitrichev.blogspot.com/2015/12/a-week-during-neerc.html

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

»
9 years ago, # |
← Rev. 5   Vote: I like it +8 Vote: I do not like it

Another interesting question about this problem is: does it matter that we require exactly K dominoes, not “at most K dominoes” as one would normally expect? More precisely, do there exist such K and N, such that 2K<=NxN, and a NxN field of non-negative integers, such that we can get a higher sum by placing K-1 dominoes than by placing K dominoes?

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):

?A?
.A.

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):

AABCCDD
E.B.FFG
EHHII.G

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 :)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply