eolymp
bolt
Try our new interface for solving problems
Problems

Испорченный паркет

published at 6/6/11, 2:24:42 pm

А правда ли, что рекомендованный автором алгоритм проходит тайм-лимит на сайте?

awpris replied:
Правда. Вот авторское решение в системе: http://www.e-olimp.com.ua/solutions/332422
published at 6/9/11, 7:37:07 pm

Тогда вопрос такой: автор писал максимальное паросочетание Куном или каким-то потоковым алгоритмом?

published at 6/9/11, 8:55:44 pm

Если две плитки размером 1х1 дешевле,чем одна размером 2х1, то можно всё замостить единичными плитками. В противном случае необходимо положить как можно больше плиток размером 2х1.

Построим граф, вершинами которого будут испорченные клетки, а ребром будут соединены клетки, которые можно замостить одной плиткой 2х1. Заметим, что это двудольный граф, в котором нужно найти максимальное паросочетание. Это можно сделать с помощью любого алгоритма нахождения потока.

published at 6/12/11, 1:46:32 pm

Видимо, не любого :) Диниц не считается самым медленным алгоритмом, особенно для единичных графов. Тем не менее он получает ТЛЕ.

Видимо, автором умалчивается о некотором жадном предподсчёте.

published at 6/15/11, 11:12:05 am

В мене теж Диниц, але не ТЛ, взагалі чогось помилку на майже всіх тестах викидає (

published at 6/15/11, 3:23:22 pm

А на домашнем компе в релизе все тесты проходят?

published at 6/15/11, 4:21:04 pm

Незрозуміло...що означає "в релизе" ? ТЛ на тих же тестах :)

published at 6/20/11, 9:32:44 pm

Ну, есть дебаг-мод, когда система по ходу прослеживает значения всех переменных и прочее, что удобно для дебага. И есть релиз-мод, когда всё соптимизировано под быстродействие. Во втором компилирутся и запускаются наши программы на сайте. И в нём же нужно ловить крэши - больше шансов, чем в дебаге.

published at 5/18/12, 6:19:45 am

Надуюсь ЭК пройдет тоже, с оптимайзами какими-нибудь. olpetOdessaONU, думаю, вы имели в виду ловить креши нужно наоборот - в дебаге. :)

published at 8/13/14, 8:26:19 pm

Решаю эту задачу. Дошёл до того, что нужно прочитать со стандартного входа матрицу и преобразовать в граф (точнее, в матрицу пропускных способностей, по которой будет построен граф). Кто-нибудь может намекнуть, как это лучше сделать?