Комментарии
|
+6
Поздравляю!
|
|
+36
Поезд: Москва - Саратов, вагон 12 :)
|
|
0
This is solution of problem C from tutorial:
http://ideone.com/lHtSZ |
|
0
Тест №4: |
|
+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. |
|
0
Доказательство довольно громоздкое, но вкратце выглядит примерно так:
Сперва сожмем все вершины между которыми расстояние равно нулю в одну компоненту (получим граф компонент связности). Заметим, что если мы перекрашиваем какую-то клетку, то можно перекрасить и всю её компоненту, так как в итоге раскраска не изменится. 1) можно доказать, что любую раскраску можно привести к такому виду, что каждое следующее перекрашивание будет подмножеством предыдущего. 2) последнее перекрашивание будет состоят ровно из одной вершины (возможно целая одноцветная связная область исходной доски). Поэтому один из оптимальных ответов будет иметь вид описанный в разборе. Если в качестве начальной вершины мы возьмем клетку, лежащую в последнем перекрашивании этого оптимального ответа, алгоритм найдет решению не хуже чем оптимальное. |
|
-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.
|
|
+1
Тест #4: |
|
0
It is already available, if i'm not mistaken.
|
|
+3
Да, в С можно было неудачно выбрать алгоритм построения кодов, и в результате получить много много строк глючного кода :)
|
|
0
Большой тест из почти 900 свитков, но в ответе их всего 2, и соответственно минимальное количество секунд также равно 2.
|
|
0
Тест 15 - один из средних рандомных тестов:
31 |
|
0
Тест 36, как ни странно, довольно тривиальный :) |
|
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
Тест 86:
10 1000 8Возожный ответ: YES |
|
0
Довольно болшой рандомный тест из 70 свитков.
|
|
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 |
|
+1
Тест номер 3:
10 100 5 61 3 55 2 12 6 39 5 21 10 39 7 16 1 10 1 70 5 100 7 Один из возможных ответов: YES 21 6 0 10 15 9 17 1 18 2 19 6 20 5 |