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).

  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!

>>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

Rt.

K means, you need to find a answer <= k, it is not necessary for you to find the min answer.

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

"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...

Email:
miguelangelhdz@hotmail.com
thanks :)

I try to solve it for a month but I can't see any solution so If you have
solution please tell me.
pitchayasit@hotmail.com
Thank you.

mail:miguelangelhdz@hotmail.com

Is it needed, and if it is, what is max value?