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! 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! 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. I suggest to replace "K is the maximum result" with "K is the maximum difference of gold". If so, please send one to ysymyth@gmail.com please! 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 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. 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 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 :). >>There are no bounds for K. What can they be? Sorry, the answer is in condition. Edited by author 19.06.2009 17:25 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 What is a stupid problem ! Must we think out super heuristic to got ac? What is purpose of putting NP problems ? Please mail to snow_whiteiq@yahoo.com > 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 :) "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... > Really, would you help me a little, or more?! plz email me at mhbateni@yahoo.com . thanx "K is the maximum result that the emperor accepts. " What result? Is it a maximum difference between the reachest general and the poorest general? Email: miguelangelhdz@hotmail.com thanks :) |
|