11300 - Spreading the Wealth

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11300 - Spreading the Wealth

Post by sclo »

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

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by 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
New poster
Posts: 25
Joined: Mon Sep 03, 2007 10:54 am

Post by goodwill »

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

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

how do you solve this problem using medians?

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

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by 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
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ »

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

FAQ wrote: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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

I didn't use big integers.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by 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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz »

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.
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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by 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
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

Post by 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?

Post Reply

Return to “Volume 113 (11300-11399)”