[algogeeks] Re: Nice question!!

Mon, 26 Jun 2006 19:55:31 -0700

Hi Pradeep,
 
I don't think a DP will work... (unless it is single dimensional DP)...
 
My idea was on the same lines of Gene... But I was thinking about an easy implementation which runs in O(n log n) on average case... (Of course... in worst case it takes... O(n^2)... But... why not give it a try on the judge?)
 
What about a quick sort like algorithm?
Find the min, then split the array... and find the best... also find the Average of the array.... Select the best among these (the 2 halves + the original array)....
 
When the array is already sorted, this will take O(n^2)... Let me think, whether I can improve on this... :(


 
On 6/27/06, Gene <[EMAIL PROTECTED]> wrote:

Pradeep Muthukrishnan wrote:
> I have been trying this problem for quite some time now...but havent
> found anything concrete...can anyone solve this?
> http://acm.zju.edu.cn/show_problem.php?pid=2642

Hello Pradeep.  Here is an idea.

I am going to write [a..b] for a potential solution range with l=a,
r=b.

Suppose the minimum of the series of happiness numbers is at position
m1.  Now, if the correct solution contains a[m1], then the range must
be [1..n]. I.e. the total happiness is

a[m1]*sum{i=1..n}a[i]  .

That's because once you've included the minimum, you can't lose
anything by including more numbers to the left and right.

Now suppose m1 is _not_ in the correct solution, so the correct range
is _not_ [1..n].  Let m2 be the position of the second-smallest number
and hypothisize that m2 might be included in the correct solution
range.  In this case either 1 <= m2 < m1 or else m1 < m2 <= n.  If the
first case, the best possible total happiness is

a[m2]*sum{i=1 .. m1-1}a[i]

and in the second,

a[m2]*sum{i=m1+1 .. n}a[i] .

This is by the same reasoning as the m1 case.  See the pattern?

So a proposed algorithm.

Let S = {  [1..n]  }

let BestRange = [1..n],  BestHappiness = 0

foreach m in the sequence of positions of happiness values taken in
ascending order
Remove from S the element [L,R], which is the (unique) range that
contains m.
Let X = a[m] * sum{i=L..R}a[i]
if X > BestHappiness { Set BestRange=[L..R], BestHappiness=X }
Insert [L..m-1] (if L<=m-1) and [m+1..R] (if m+1<=R) in S.
end foreach;

For the example, m1= 2
1 * (3+1+6+4+5+2) = 21
then S = { [1..1], [3..6] } so we try m2=6
2 * (6+4+5+2) = 34
then S = { [1..1], [3..5] } so we try m3=1
3 * (3) = 9
then S= { [3..5] } so we try m4=4
4 * (6+4+5) = 60
then S={ [3..3], [5..5] } so try m5=5
5 * (5) = 25
then S={ [3,3] } so try m6=3
6 * (6) = 36

So we see that BestHappiness=60 and BestRange=[3..5].

Now with such big n you don't want compute the sums from scratch each
time.  This is easily fixed by computing an auxiliary array of
accumulated sums, s[i] = a[i] + s[i-1] (with s[0]=0) .  Then
sum{i=L..R}a[i] is just s[R] - s[L-1].

You also need an efficient representation for S.  A balanced search
tree indexed on L (or R) values ought to work fine.

So with these implementation ideas the run time will be O(n log n).  I
guess it ought to be fast enough to run in 10 seconds on 100,000 input
values, thought it might be close!

So far I've convinced myself this is right.  Happy to discuss.



--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to