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

Обсуждение задачи 1142. Отношения

Any Help/Hint
Послано Amil Khare 25 сен 2017 22:27
Hello,
I am not that strong in DP but I have been trying hard to understand the problem. I tried coming up with a solution however got WA. I cannot completely understand the hints given before, PLEASE HELP !!!
Re: Any Help/Hint
Послано Mahilewets Nikita [BSUIR] 26 сен 2017 18:49
There are two dp-approaches already described on the webboard
Re: Any Help/Hint
Послано Mahilewets Nikita [BSUIR] 26 сен 2017 21:50
So I have accepted with dp
I have two dp
Stirling numbers of the second kind and factorial
Then precalculate answer array
Re: Any Help/Hint
Послано Amil Khare 27 сен 2017 12:34
I have seen the 2 DP solutions however I still don't understand how do they arrive at the relation?
Can you describe in detail if possible, Please !
Re: Any Help/Hint
Послано Mahilewets Nikita [BSUIR] 27 сен 2017 15:33
There are X groups consisting of equal numbers.
X=1,2,..n.

What does it mean, to put some '<' and '>' signs between them?
It is just to define some order relation.
Just assign one group as the greatest, another group as the second greatest etc.

So we find number of ways to make groups and multiply it by number of ways to make ordering

https://ideone.com/00UUdf