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 1431. Diplomas

Show all messages Hide all messages

in:
10 3 5
out:
2
How????????
I think that the answer is 3
Re: Very bad test, which fails many algos... (+) Peter Huggy (Pskov) 17 Sep 2007 20:19
if you mean:
3
10 3 5
then the answer (accepted) is 3
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 Jun 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"
I think, this comment should be added in statement, because it's easy to confuse, thinking that ALL designer claims were dismissed.
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.
Надо учесть:
И вот последний нанятый дизайнер заявил, что все дипломы одного типа (например, за полуфинальные соревнования) должны висеть в одном ряду