Very bad test, which fails many algos... (+)
in:
10 3 5
out:
2
Re: Very bad test, which fails many algos... (+)
How????????
I think that the answer is 3
Re: Very bad test, which fails many algos... (+)
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... (+)
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... (+)
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... (+)
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... (+)
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.