Зіпсований паркет
А правда ли, что рекомендованный автором алгоритм проходит тайм-лимит на сайте?
Тогда вопрос такой: автор писал максимальное паросочетание Куном или каким-то потоковым алгоритмом?
Если две плитки размером 1х1 дешевле,чем одна размером 2х1, то можно всё замостить единичными плитками. В противном случае необходимо положить как можно больше плиток размером 2х1.
Построим граф, вершинами которого будут испорченные клетки, а ребром будут соединены клетки, которые можно замостить одной плиткой 2х1. Заметим, что это двудольный граф, в котором нужно найти максимальное паросочетание. Это можно сделать с помощью любого алгоритма нахождения потока.
Видимо, не любого :) Диниц не считается самым медленным алгоритмом, особенно для единичных графов. Тем не менее он получает ТЛЕ.
Видимо, автором умалчивается о некотором жадном предподсчёте.
В мене теж Диниц, але не ТЛ, взагалі чогось помилку на майже всіх тестах викидає (
А на домашнем компе в релизе все тесты проходят?
Незрозуміло...що означає "в релизе" ? ТЛ на тих же тестах :)
Ну, есть дебаг-мод, когда система по ходу прослеживает значения всех переменных и прочее, что удобно для дебага. И есть релиз-мод, когда всё соптимизировано под быстродействие. Во втором компилирутся и запускаются наши программы на сайте. И в нём же нужно ловить крэши - больше шансов, чем в дебаге.
Надуюсь ЭК пройдет тоже, с оптимайзами какими-нибудь. olpetOdessaONU, думаю, вы имели в виду ловить креши нужно наоборот - в дебаге. :)
Решаю эту задачу. Дошёл до того, что нужно прочитать со стандартного входа матрицу и преобразовать в граф (точнее, в матрицу пропускных способностей, по которой будет построен граф). Кто-нибудь может намекнуть, как это лучше сделать?