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

Обсуждение задачи 1431. Сертификаты

Very bad test, which fails many algos... (+)
Послано Lampabash 20 май 2006 22:41
in:
10 3 5
out:
2
Re: Very bad test, which fails many algos... (+)
Послано Taloi Bogdan 4 апр 2007 21:40
How????????
I think that the answer is 3
Re: Very bad test, which fails many algos... (+)
Послано Peter Huggy (Pskov) 17 сен 2007 20:19
if you mean:
3
10 3 5
then the answer (accepted) is 3
Re: Very bad test, which fails many algos... (+)
Послано And IV 24 окт 2007 15:34
Надо учесть:
И вот последний нанятый дизайнер заявил, что все дипломы одного типа (например, за полуфинальные соревнования) должны висеть в одном ряду
Re: Very bad test, which fails many algos... (+)
Послано Morbidel 14 фев 2008 19:13
can't we split the 10 in 6 and 4 and then:
1 row: 6 5
2 row: 4 3

?
Re: Very bad test, which fails many algos... (+)
Послано Seyyed Mehran Kholdi 29 июн 2008 23:53
No, we can't. You can refer to the problem statement:
"A hired designer reckons that all diplomas of the same kind (for example, for winning semifinals) must be in the same row"
Re: Very bad test, which fails many algos... (+)
Послано Partisan 26 июн 2009 15:54
I think, this comment should be added in statement, because it's easy to confuse, thinking that ALL designer claims were dismissed.
Re: Very bad test, which fails many algos... (+)
Послано Partisan 26 июн 2009 16:26
It's interest to solve problem if we can split. I have O(2^(3*n/2)) probably right solution using DP of bitmasks. If we have group of k diplomas where no 2 of them cannot be fully situated exactlty in one row, than we can situate these k diplomas in k or k-1 rows. For each bitmask we check, can we situate its k(mask) diplomas in k-1 rows. Than in DP for mask with k bits we check all submasks with size of <=k/2 as first such group. These get us the complicity written before.