Дан квадрат NxN. N > 2.

Закрасим чёрным цветом N клеток так, что никакие две из них не смежны по стороне. Закрасим белым цветом клетки, смежные по стороне с чёрными. Доказать что количество белых клеток  ≥ N + floor(N / 2) при любой такой покраске.

Например для квадрата 3x3. Красим диагональ в чёрный цвет. Количество белых 4.

Через какое время по истечении 2 часов, отведённых на участие в виртуальном контесте, появляется возможность просматривать тесты? Прорешал http://codeforces.me/contest/56 час назад и до сих пор не могу посмотреть где же валится решение.

Начал изучать потоки.

Пусть есть транспортная сеть G = (V, E). c(u, v) — пропускная способность. Если есть ребро (u, v), то нет (v, u). Исток s, сток t. Для любой вершины v верно то, что она достижима из s, и t достижима из v.

Пусть есть поток на этой сети f.

0 ≤ f(u, v) ≤ c(u, v).

Для любой верно .

То есть всё как в Кормене (3 издание). У меня такой вопрос. Верно ли то, что исходя из ограничений на функцию потока мы не можем пропустить через какое-то ребро (u, v) вещества меньше чем f(u, v). Иными словами, верно ли то, что если мы доставили вещество в сток, то не существует ребра, через которое прошло вещества меньше, чем f(u, v)? Или я вообще спрашиваю глупость?=)

Привет! Читаю про префикс-функцию на e-maxx и не могу понять пункт про сжатие строки. А именно, из чего следует в части где n не делится на k, что все буквы блока совпадают? В примере на картинке это очевидно. А что если у нас сдвиг суффикса относительно второго блока будет больше чем на 1 символ?

http://e-maxx.ru/algo/prefix_function#12

Пусть есть связный неориентированный граф G = (V, E), на рёбрах определена весовая функция w. Пусть существуют два дерева T и T′. Возьмём их списки рёбер L и L′. Отсортируем их (дальше при упоминании списков L и L' понимается, что они отсортированные). Пусть первая позиция их весового различия k, где выполняется L[k] > L′[k].

Требуется доказать или опровергнуть следующее утверждение: существует ребро e из первых k рёбер списка L' такое, что при добавлении e в лес F, образованный первыми k - 1 рёбрами списка L, в F не возникнет цикла и количество деревьев уменьшится.

Операция вводится на целых положительных числах. верно, если , где значит конкатенацию строковых представлений чисел x, y и последующий перевод результата в число.

Требуется доказать, что если и , то .

Дан взвешенный ориентированный граф G = (V, E). Нужно найти кратчайшие пути из s до всех остальных вершин. Известно, что веса рёбер кратчайшего пути из s в любую вершину v образуют битоническую последовательность.

Битоническая последовательность вначале монотонно возрастает, а затем монотонно убывает, или можно путём сдвига получить такую.

Какой есть эффективный алгоритм решения данной задачи? Я как понимаю, что-нибудь лучше чем Беллман-Форд и с использованием свойства битонизма.

Ещё интересует вопрос. Необходимо найти кратчайшие простые пути в взвешенном ориентированном графе из вершины s до всех остальных. Граф может содержать отрицательные циклы. Как оптимально решается эта задача? Увеличением весов на константу, так чтобы не было отрицательных рёбер и последующий алгоритм Дейкстры или Беллмана-Форда?

Дано два выпуклых многоугольника C1 и C2. Требуется доказать, что существует прямая L, которая делит одновременно и C1 и C2 на две равные части.

Спасибо.

Расскажите, пожалуйста, или дайте ссылку, где можно почитать про O(E) алгоритм поиска узкого остовного дерева.

Узкое остовное дерево неориентированного графа G есть остовное дерево G, в котором наибольший вес ребра минимален среди всех возможных остовных деревьев.

Двусвязный компонент неор. графа — максимальное множество рёбер, такое что любые два ребра принадлежат общему простому циклу.
Удаление мостов из графа раскладывает граф на двусвязные компоненты.
Собственно со вторым утверждением проблемы. Подскажите как доказать, что любой компонент после удаления мостов двусвязен?

Тренировка
Задача А.
Постоянно выходит "Ошибка исполнения на тесте 5". В реализации структуры ошибок нет (скорее всего), так как остальные задачи были решены с помощью этой реализации.
Попробовал повтыкать try catch и выяснил, что падает в методе ReadArray(' ') (строка 93 в Pastebin), который сплитит строку. (Всегда пользуюсь подобным считыванием, до сего момента проблем не возникало)
Подскажите, пожалуйста, где ошибка.
Код

Опишите реализацию процедуры Random(a,b), которая может использовать только один вызов — процедуры Random(0,1). Чему равно математическое ожидание времени работы вашей реализации и как оно зависит от a и b?
Random(0,1) — 50% вернёт 0, и 50 % вернёт 1.
Random(a,b) — с вероятностью 1/(b-a+1) вернёт число из интервала [a,b].
Гугл показывает реализации с побитовым (Random(0,1)) заполнением числа. Но многие из них у меня вызвали сомненния (одна выходит за интервал, другая показалась неравновероятной).

Sorry for the weird name of topic.
We have two arrays of non-negative integers A and B. Their length is N
Let's sort these arrays.
A' — a permutation of A.
How to prove that there is no A' such that:
A'[1]*B[1]+..+A'[N]*B[N] > A[1]*B[1]+...+A[N]*B[N]. (A and B are sorted)
I understand that it is a clear fact but I can't prove it.
Sorry for my English. I tried to write correctly:)

0 ≤ x ≤ 1
0 ≤ a ≤ 1
1 ≤ V_p, V_f ≤ 10⁵
Заранее спасибо, за подсказки и помощь.