Comments
|
0
This is solution of problem C from tutorial:
http://ideone.com/lHtSZ |
|
+3
The proof is in short looks like this: First, compress all vertices between which distance is equal to zero in one component (get graph of connected components). Note that if we repaint some cell, it can be repainted and all its component, as a result coloring will not change. 1) we can prove that any coloring can be reduced to a form such that each subsequent repainting is a subset of the previous one. 2) the last repainting will consist of exactly one vertex (possibly the whole monochromatic connected region of the original board). Therefore, one of the best answers will be of the form described in the review. If as the initial vertex, we take a cell, lying in the last repainting of the optimal sequence, the algorithm finds the solution not worse than optimal. |
|
-3
My apologies ... in the problem D in one point there was a typo. Initially, the restrictions on X and Y were as follows: 0 <= Xi, Yi <= 100.
|
|
0
It is already available, if i'm not mistaken.
|
|
0
Test #4: |
|
0
Test #3:
10 100 5 61 3 55 2 12 6 39 5 21 10 39 7 16 1 10 1 70 5 100 7 Possible answer: YES 21 6 0 10 15 9 17 1 18 2 19 6 20 5 |
|
0
Pretest #3:
10 4 4 4 4 4 4 4 4 4 4 Possible answer: YES 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 |