11300 - Spreading the Wealth

[sclo]

Any idea on how to solve this problem in O(n), not O(n^2)?

[baodog]

A well coded solution of order O(n (log n)^c) where c is a small constant
will pass the time limit.

Hint: Derive a linear algebra solution.

[goodwill]

I used a nlogn algorithm for finding median. Is there any better algorithm?

[baodog]

Use the median find algorithm to find the median in O(n).

See below for a very clear explanation:

http://www-di.inf.puc-rio.br/~laber/med ... artime.pdf

[sclo]

how do you solve this problem using medians?

Nevermind, I am being stupid, I was computing the median without even knowing it!

[baodog]

Actually for this dataset, the O(n) solution is only about 25% faster
than the O(nlogn) solution. However, for sufficiently larger n, it becomes
significant.

[FAQ]

excuse me, I still don't understand why we need Median here?

[sclo]

excuse me, I still don't understand why we need Median here?

have you solved the linear equations?
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.

[Robert Gerbicz]

Are you using big integer for this problem? Because the result can be larger than 2^64. Or the output will always fit in 64 bits for the testcases?

[sclo]

I didn't use big integers.

[baodog]

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.

[Robert Gerbicz]

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.

That's wrong. Probably the most critical valid input:
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.

[baodog]

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

Code: Select all

The total number of transfered coins will fit inside an unsigned 64 bit integer.

[sclo]

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.

[mysword]

anyone give some I/O?
I got many WAs in this problem.
Although the problem statement says that, the sum of all the elements fit in the unsigned 64-bit integer, does the final result fit in it as well?