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

Обсуждение задачи 1779. Великая команда

Who can give me some hints?
Послано adrian 9 окт 2010 18:38
I thought it for a long time,but I still do not know how to do it.
Hint
Послано vgu 9 окт 2010 20:36
1) If we know the degree of the vertices, we can determine: is such graph exist.
2) Write a full search. You will quickly find an answer. You can sent this code and get AC or look at the answer and found a pattern.
Re: Hint
Послано svr 9 окт 2010 22:11
1)Havel-Hakimi algorithm
2) Hypothesis(my): sequence n/2 n/2 ... 3 3 2 2 1 1 0 0
realizable for each n
P.S. In timus there is a problem about full search:
monkey aplly full search on keyboard. When it create theorem.

Edited by author 09.10.2010 22:30
Re: Hint
Послано luckysundog 23 окт 2011 01:21
svr, your hypothesis is true. It's obvious if we draw the adjacency matrix of these graphs (for even N):

N = 4:
0 0 0 1
0 0 1 1
0 1 0 0
1 1 0 0

N = 6:
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 1 1 1
0 0 1 0 0 0
0 1 1 0 0 0
1 1 1 0 0 0

N = 8:
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 1 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 0
0 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0