ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1142. Relations

Any Help/Hint
Posted by Amil Khare 25 Sep 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
Posted by Mahilewets Nikita [BSUIR] 26 Sep 2017 18:49
There are two dp-approaches already described on the webboard
Re: Any Help/Hint
Posted by Mahilewets Nikita [BSUIR] 26 Sep 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
Posted by Amil Khare 27 Sep 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
Posted by Mahilewets Nikita [BSUIR] 27 Sep 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