11300  Spreading the Wealth
Moderator: Board moderators
11300  Spreading the Wealth
Any idea on how to solve this problem in O(n), not O(n^2)?
Use the median find algorithm to find the median in O(n).
See below for a very clear explanation:
http://wwwdi.inf.pucrio.br/~laber/med ... artime.pdf
See below for a very clear explanation:
http://wwwdi.inf.pucrio.br/~laber/med ... artime.pdf
have you solved the linear equations?FAQ wrote:excuse me, I still don't understand why we need Median here?
I suppose that the variables are x(i,i+1), denoting the number of units passed from i to i+1. It can be positive, 0 or negative. In case of negative it means that i+1 pass to i. Here, i+1 = i+1 mod n
If you solve the proper linear equations, you will find that you can write all x(i,i+1) in the form Ai+x(k,k+1), where k is fixed.
Now, sort in the order of increasing Ai.
Now consider minimizing the sum of absolute value of all x(i,i+1).
Think about how the median can be used.
At first I didn't even realized that the median is used.

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
That's wrong. Probably the most critical valid input:baodog wrote:It says in the problem, that the
sum of the numbers fit inside 64 bits unsigned.
Depending on how you implemented your solution,
your intermediate values might exceed 64 bits.
However, in most reasonable implementations you
won't need BigInt.
Suppose that there are 1000000 peoples at the table and one of them has got 18446744073709000000 coins, others hasn't got coins. What do you think how many coins will be transferred? About 250000*2^64 coins. So the answer can be larger than 2^64.
Yes, you are right. As stated, the problem requires BigInt (only 2 long long's suffice and only BigInt addition and comparison is needed).
What I meant to say in the problem is
What I meant to say in the problem is
Code: Select all
The total number of transfered coins will fit inside an unsigned 64 bit integer.
Something that I have learned from previous experience: Make reasonable assumptions whenever I can, if I get WA, then just check whether the assumption is valid or not.
Many problems don't even give size of input, or any bounds on the input numbers, so anything is fair game. In those cases, one needs some experience to make the correct judgement, or one can simply send in clarifications.
Many problems don't even give size of input, or any bounds on the input numbers, so anything is fair game. In those cases, one needs some experience to make the correct judgement, or one can simply send in clarifications.