ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1609. Трамвайная плитка

But how to solve this problem??
Послано caoqinxiang 6 апр 2008 07:49
Re: But how to solve this problem??
Послано DK [Samara SAU 1: X2008] 27 апр 2008 01:58
Use the "SHAMANIZM" to overcome time-limit ;)
Re: But how to solve this problem??
Послано svr 18 июн 2008 13:53
Another advice:
I guess that rested  domino must form graph with next specific:
It must be reduced to empty by sequental removing of
vertex with degree=1 and adjacent with one.
("должен общипываться").What kind of these graphs?

Edited by author 18.06.2008 14:10
Re: But how to solve this problem??
Послано Denis Koshman 26 авг 2008 07:04
Dominos are usually solved by finding perfect bipartie matching between odd and even cells (for their x+y). Now the problem is to fix minimal number of matched edges, so that maximum matching over remaining graph is unique. If there is alternating cycle, then matching is not unique.

Edited by author 26.08.2008 07:12
Re: But how to solve this problem??
Послано svr 12 фев 2009 12:10
What algo could we design based on it?
1. Find all cycles.
2. For each edge form set of all circles containig it.
3. Find minimal covering of set of all circles.
Shortly, we should use minimal covering problem?

Edited by author 12.02.2009 12:11
Re: But how to solve this problem??
Послано Shen Yang 10 май 2018 13:46
sure there is not more than min(n,m)/2+3 ones, but how we can prove or say its wrong there is no more optimal solution