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

Обсуждение задачи 1035. Вышивка крестиком

Ivan Georgiev Help wanted on 1035!! [3] // Задача 1035. Вышивка крестиком 24 сен 2001 01:34
As far as I can see the problem has relatively small
percent of the difficulty, but I can't think of the way I
should walk the pattern by means of minimal number of
threads..

Is the problem only a DFS (and if it is how should it be
done) or there is something else?

Thank you.
Jivko Ganev Re: Help wanted on 1035!! [1] // Задача 1035. Вышивка крестиком 24 сен 2001 03:36
You need some graph theory and common sense to solve it.
Basically after you do the logic the problem breaks down to
simple bfs/dfs and counting degrees. The idea comes from
the problem of decompossing graph to a minimum amount of
paths which is solved by some simple logic - you should be
able to prove it yourself.


Hint - it has something to do with Euler ...
Helpfull to have math invariant(which right for every algo)
I think that answer=Nc+Ndb/2
where Ndb- sum of disbalances of vertices of grid's graph.
and Nc- number of alternating loops which unreached from
disbalanced vertices by alternating pathes.
But can't go far then test 8.

AC 0.031 now.Idea is right. It taken 3 days to
convert idea in quick algo.

Edited by author 04.01.2009 10:13