ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1431. Diplomas

Very bad test, which fails many algos... (+)
Posted by Lampabash 20 May 2006 22:41
in:
10 3 5
out:
2
Re: Very bad test, which fails many algos... (+)
Posted by Taloi Bogdan 4 Apr 2007 21:40
How????????
I think that the answer is 3
Re: Very bad test, which fails many algos... (+)
Posted by Peter Huggy (Pskov) 17 Sep 2007 20:19
if you mean:
3
10 3 5
then the answer (accepted) is 3
Re: Very bad test, which fails many algos... (+)
Posted by And IV 24 Oct 2007 15:34
Надо учесть:
И вот последний нанятый дизайнер заявил, что все дипломы одного типа (например, за полуфинальные соревнования) должны висеть в одном ряду
Re: Very bad test, which fails many algos... (+)
Posted by Morbidel 14 Feb 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... (+)
Posted by 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"
Re: Very bad test, which fails many algos... (+)
Posted by Partisan 26 Jun 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... (+)
Posted by Partisan 26 Jun 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.