| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| solution | wangbicheng1 | 1144. The Emperor's Riddle | 13 ноя 2015 09:22 | 1 |
Assume each general's gold a[1],a[2],...,a[m]
divide them into b[1]&c[1],b[2]&c[2],...,b[m]&c[m],and b[1]+c[1]=a[1],b[2]+c[2]=a[2],...
(b[i] can be any partition from a[i])
Then sort b from big to small, sort c from small to big.
We can prove that between b[1]+c[1],b[2]+c[2],...,b[m]+c[m], the biggest minus the smallest would not be worse than the previous one. Continuously do this and we'll get the answer.
This solution is developed by Wenbin Tang. Thanks to him! |
| 4 MB Java 1.7? | raggzy | 1144. The Emperor's Riddle | 4 апр 2014 04:38 | 2 |
Well, i spent a lot of time for optimizing memory stuff in Java, but it seems that even empty program takes 5 MB.
I'm kindly asking administration to increase memory limit to doable one (9-10 MB). Solved. Ignore pls.
HINT:
Don't use java.util.Scanner! |
| Hint | Серовиков Андрей | 1144. The Emperor's Riddle | 21 апр 2013 02:43 | 1 |
Hint Серовиков Андрей 21 апр 2013 02:43 First of all, it should be noted that in the literature such problem is known as "bottleneck multiple subset sum problem" (B-MSSP) and it's a variation of knapsack problem. This problem even with such restrictions is an NP-complete.
So, the aproximate solution even needed. Precision??? The precision is mystic (based on statement of the problem).
I don't know how other people solved this problem, but I aproximate solution through aproximation of every pair of subsets. To aproximate a pair of subsets we need to solve B-MSSP just for 2 subsets. This can be solved in O( (|S1|+|S2|)*max(Ai) ) time and O( max(Ai, |S1|+|S2|) ) space complexity. |
| Statement | Yermak | 1144. The Emperor's Riddle | 17 ноя 2012 05:44 | 1 |
I suggest to replace "K is the maximum result" with "K is the maximum difference of gold". |
| Any fast solutions? | YSYMYTH | 1144. The Emperor's Riddle | 14 авг 2012 15:40 | 1 |
If so, please send one to ysymyth@gmail.com please! |
| Algo | xurshid_n | 1144. The Emperor's Riddle | 27 мар 2012 13:29 | 2 |
Algo xurshid_n 19 янв 2012 18:52 A[] - values.
B[] - rewards.
1. sort A[] by not increasing order.
2. i=1..n B[j] += A[i], which B[j] - minimal value of B[].
3. while ( not <= K)
try to equate with minimal of B[] and all other B[]s.
try to equate with maximal of B[] and all other B[]s.
4. print.
only how to equate ? use simple DP!
if M=2 we get knapsack problem, and how to solve it faster than N*sum(A[i])?
or your solution uses fact that a B[]s are approximately equal? |
| K's meaning | Huang WenHao | 1144. The Emperor's Riddle | 19 ноя 2010 21:38 | 3 |
K means, you need to find a answer <= k, it is not necessary for you to find the min answer. Then, what is the answer for this test
2 2 1
100 200
?
Edited by author 23.10.2006 12:24 I think that imperator was not so bad
to formulate unsolvable problem before girls.
His bound K was established kindly acording with opportunities of two girls and young programmers. So good greedy must work. |
| A very nice DP problem.My algorithm is the best of all,it's only O(n*m). | Blue cat | 1144. The Emperor's Riddle | 2 сен 2010 18:33 | 7 |
Could you give me any hints of the DP algorithm? Thanks!
(mail to: comars@hotmail.com ) If it is NP, the complexity of the algorithm should be O
(K*something) right ?
Can you give me any hints on your solution ?
mail: scythe@toughguy.net
thanx a lot Could you give me any hints of the DP algorithm? Thanks!
(mail to: cpp_student@163.com ) I also think it's nice!My algorithm use 0.5s.I use some random.It's nearly O(n*m) can you give your solution??
Thx
remdy21@live.cn |
| I can't memorize, but somone said that it's NP - problem...? | Nemets Ilya | 1144. The Emperor's Riddle | 17 авг 2009 08:57 | 6 |
Sorry, but I don't beleive in such a simple solution as DP.
It looks like a good heuristic, but not a real solution.
Has anyone another opinion? I've just read the problem and don't know the solution, but I can
suppose that the point is that all wheights are whole numbers. I
think it's like the problem about the bag (given the set of things,
each of weight Wi and value Vi, find the subset with maximal value
and total weight not exeeding some number W). This is NP problem, but
in case of descrete and not very large weights it has DP solution. "in case of descrete and not very large weights it has DP solution."
I saw a comment of blue cat saying that he has a DP solution about
this problem but I think it's more likely to be a good heristhic, i
wish to know how to do it. BTW there's another problem like
this, "Ships"(right now i don't remind the number) but it's more easy
to get AC than this one. (I have had TL).
mail:miguelangelhdz@hotmail.com > "in case of descrete and not very large weights it has DP solution."
I was speaking about "bag" problem. It really has DP solution.
I cannot say anyting certain about the DP solution of the subj
problem, because I don't know it :). The solution to the kanpsack (bag) problem is a DP solution, but the
time complexity is O(n*W) (W is the total weight the knapsack can
hold), and it is pseudo-polynomial. For the multiknapsack problem,
the search space is much more than O(W).
Anyway a DP solution on O(n*m) is out of the question. If it would
be a solution, that means he could solve the knapsack problem (which
is NP) in O(n) and that is impossible. I cannot begin to think how
one could solve such a problem (unless indeed one can find a
solution that is not perfect, but passes the given tests)
> > "in case of descrete and not very large weights it has DP
solution."
> I was speaking about "bag" problem. It really has DP solution.
>
> I cannot say anyting certain about the DP solution of the subj
> problem, because I don't know it :). |
| What is bound for K? | Partisan | 1144. The Emperor's Riddle | 19 июн 2009 17:13 | 1 |
>>There are no bounds for K. What can they be?
Sorry, the answer is in condition.
Edited by author 19.06.2009 17:25 |
| AC at long last =) | Burunduk1 | 1144. The Emperor's Riddle | 14 сен 2008 02:24 | 1 |
But I'm wonder, how so many people have got AC in 0.1 seconds and less... If you could give me your fast solutions, please, send it to sk1@hotbox.ru |
| Could a general get nothing? | Cheryl | 1144. The Emperor's Riddle | 19 июн 2006 18:34 | 1 |
|
| People, give me some hint, please, please, please !!!!!! | ILTK! | 1144. The Emperor's Riddle | 15 авг 2005 22:51 | 1 |
|
| Stupid Problem | ILTK! | 1144. The Emperor's Riddle | 28 июл 2005 19:11 | 1 |
What is a stupid problem ! Must we think out super heuristic to got ac? What is purpose of putting NP problems ? |
| Can anyone give me the solution that's DP? | plg | 1144. The Emperor's Riddle | 14 июн 2003 18:33 | 1 |
Please mail to snow_whiteiq@yahoo.com |
| Does this problem has a deterministic polynomial solution? If such solution exists, can anybody send it to me (ioi@list.ru) | Antonina Baskova | 1144. The Emperor's Riddle | 2 дек 2002 15:49 | 3 |
I can't understand how the solution can be greedy :). If we take M =
2, we'll get problem about stones and two piles, which is NP-hard.
Maybe I misunderstood the problem? And I can realize WHAT IS K :) |
| And once again: What means K? | GhostII | 1144. The Emperor's Riddle | 12 ноя 2002 22:10 | 1 |
"K is the maximum result that the emperor accepts."
What result? Is it a maximum difference between the reachest general
and the poorest general?
But why it have been entered? As hint?
I think, it plays an essential role for the decision of a problem... |
| A very nice DP problem.My algorithm is the best of all,it's only O(n*m). | Blue cat | 1144. The Emperor's Riddle | 6 ноя 2002 06:54 | 2 |
any help? Mohammad Hossein Bateni 6 ноя 2002 06:54 > Really, would you help me a little, or more?!
plz email me at mhbateni@yahoo.com .
thanx |
| What is k?????? | King Without Kingdom | 1144. The Emperor's Riddle | 12 авг 2002 17:10 | 3 |
"K is the maximum result that the emperor accepts. " What result?
Is it a maximum difference between the reachest general
and the poorest general? |
| Someone could help me :| with this problem...(+) | Miguel Angel | 1144. The Emperor's Riddle | 18 июн 2002 08:00 | 1 |
Email:
miguelangelhdz@hotmail.com
thanks :) |
