| ENG RUS | Timus Online Judge |
Обсуждение задачи 1144. The Emperor's Riddlewangbicheng1 solution // Задача 1144. The Emperor's Riddle 13 ноя 2015 09:22 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! raggzy 4 MB Java 1.7? [1] // Задача 1144. The Emperor's Riddle 4 апр 2014 04:13 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). raggzy Re: 4 MB Java 1.7? // Задача 1144. The Emperor's Riddle 4 апр 2014 04:38 Solved. Ignore pls. HINT: Don't use java.util.Scanner! Серовиков Андрей Hint // Задача 1144. The Emperor's Riddle 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. Yermak Statement // Задача 1144. The Emperor's Riddle 17 ноя 2012 05:44 I suggest to replace "K is the maximum result" with "K is the maximum difference of gold". YSYMYTH Any fast solutions? // Задача 1144. The Emperor's Riddle 14 авг 2012 15:40 If so, please send one to ysymyth@gmail.com please! xurshid_n Algo [1] // Задача 1144. The Emperor's Riddle 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! Erop [USU] Re: Algo // Задача 1144. The Emperor's Riddle 27 мар 2012 13:29 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? Huang WenHao K's meaning [2] // Задача 1144. The Emperor's Riddle 20 май 2006 10:04 K means, you need to find a answer <= k, it is not necessary for you to find the min answer. UdSU: Ajtkulov, Kotegov, Saitov Re: K's meaning [1] // Задача 1144. The Emperor's Riddle 23 окт 2006 12:23 Then, what is the answer for this test 2 2 1 100 200 ? Edited by author 23.10.2006 12:24 svr Re: K's meaning // Задача 1144. The Emperor's Riddle 19 ноя 2010 21:38 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. Blue cat A very nice DP problem.My algorithm is the best of all,it's only O(n*m). [6] // Задача 1144. The Emperor's Riddle 1 мар 2002 11:12 Sqr (5) Re: A very nice DP problem.My algorithm is the best of all,it's only O(n*m). // Задача 1144. The Emperor's Riddle 1 мар 2002 15:13 Could you give me any hints of the DP algorithm? Thanks! (mail to: comars@hotmail.com ) Alyosha Popovich Isn't the problem NP (the multi-knapsack problem) ? (+) // Задача 1144. The Emperor's Riddle 16 май 2002 23:05 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 Jerry Re: A very nice DP problem.My algorithm is the best of all,it's only O(n*m). // Задача 1144. The Emperor's Riddle 17 авг 2007 16:34 Could you give me any hints of the DP algorithm? Thanks! (mail to: cpp_student@163.com ) love_lq Re: A very nice DP problem.My algorithm is the best of all,it's only O(n*m). // Задача 1144. The Emperor's Riddle 26 авг 2008 19:48 I also think it's nice!My algorithm use 0.5s.I use some random.It's nearly O(n*m) John Re: A very nice DP problem.My algorithm is the best of all,it's only O(n*m). // Задача 1144. The Emperor's Riddle 27 окт 2008 13:22 guy in countryside. Edric Mao Re: A very nice DP problem.My algorithm is the best of all,it's only O(n*m). // Задача 1144. The Emperor's Riddle 2 сен 2010 18:33 can you give your solution?? Thx remdy21@live.cn Nemets Ilya I can't memorize, but somone said that it's NP - problem...? [5] // Задача 1144. The Emperor's Riddle 19 мар 2002 18:12 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? Mephistos Re: I can't memorize, but somone said that it's NP - problem...? [3] // Задача 1144. The Emperor's Riddle 19 мар 2002 20:31 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. Miguel Angel Do you think so?? [2] // Задача 1144. The Emperor's Riddle 20 мар 2002 08:52 "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 Mephistos Re: Do you think so?? [1] // Задача 1144. The Emperor's Riddle 20 мар 2002 12:09 > "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 :). Scythe (Berinde Radu) Re: Do you think so?? // Задача 1144. The Emperor's Riddle 4 янв 2003 13:16 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 :). грузик Re: I can't memorize, but somone said that it's NP - problem...? // Задача 1144. The Emperor's Riddle 17 авг 2009 08:57 It's a NPC problem. Partisan What is bound for K? // Задача 1144. The Emperor's Riddle 19 июн 2009 17:13 >>There are no bounds for K. What can they be? Sorry, the answer is in condition. Edited by author 19.06.2009 17:25 Burunduk1 AC at long last =) // Задача 1144. The Emperor's Riddle 14 сен 2008 02:24 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 Cheryl Could a general get nothing? // Задача 1144. The Emperor's Riddle 19 июн 2006 18:34 Rt. ILTK! People, give me some hint, please, please, please !!!!!! // Задача 1144. The Emperor's Riddle 15 авг 2005 22:51 ILTK! Stupid Problem // Задача 1144. The Emperor's Riddle 28 июл 2005 19:11 What is a stupid problem ! Must we think out super heuristic to got ac? What is purpose of putting NP problems ? plg Can anyone give me the solution that's DP? // Задача 1144. The Emperor's Riddle 14 июн 2003 18:33 Please mail to snow_whiteiq@yahoo.com Antonina Baskova Does this problem has a deterministic polynomial solution? If such solution exists, can anybody send it to me (ioi@list.ru) [2] // Задача 1144. The Emperor's Riddle 29 ноя 2002 19:11 Miguel Angel No, combination of deterministics and NP is one solution, but the algorithm is elementary greedy (-) [1] // Задача 1144. The Emperor's Riddle 1 дек 2002 05:26 > Mephistos Re: No, combination of deterministics and NP is one solution, but the algorithm is elementary greedy (-) // Задача 1144. The Emperor's Riddle 2 дек 2002 15:49 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 :) GhostII And once again: What means K? // Задача 1144. The Emperor's Riddle 12 ноя 2002 22:10 "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... Blue cat A very nice DP problem.My algorithm is the best of all,it's only O(n*m). [1] // Задача 1144. The Emperor's Riddle 1 мар 2002 11:10 Mohammad Hossein Bateni any help? // Задача 1144. The Emperor's Riddle 6 ноя 2002 06:54 > Really, would you help me a little, or more?! plz email me at mhbateni@yahoo.com . thanx King Without Kingdom What is k?????? [2] // Задача 1144. The Emperor's Riddle 9 авг 2002 20:07 Orlov Dmitry Re: What is k?????? [1] // Задача 1144. The Emperor's Riddle 10 авг 2002 19:37 "K is the maximum result that the emperor accepts. " King Without Kingdom Re: What is k?????? // Задача 1144. The Emperor's Riddle 12 авг 2002 17:10 What result? Is it a maximum difference between the reachest general and the poorest general? Miguel Angel Someone could help me :| with this problem...(+) // Задача 1144. The Emperor's Riddle 18 июн 2002 08:00 Email: miguelangelhdz@hotmail.com thanks :)
|