0
$\begingroup$

I have a sorted array of integers of size n. These values are not unique. What I need to do is : Given a B, I need to find an i<A[n] such that the sum of |A[j:1 to n]-i| is lesser than B and to that particular sum contribute the biggest number of A[j]s. I have some ideas but I can't seem to find anything better from the naive n*B and n*n algorithm. Any ideas about O(nlogn) or O(n) ? For example: Imagine

A[n] = 1 2 10 10 12 14 and B<7 then the best i is 12 cause I achieve having 4 A[j]s contribute to my sum. 10 and 11 are also equally good i's cause if i=10 I got 10 - 10 + 10 - 10 +12-10 + 14-10 = 6<7

These A[j]s must be contiguous. Because the problem is not trivial feel free to ask me if you find my descriptions ambiguous at some point

Improve this question
$\endgroup$
4
  • $\begingroup$ It seems that what you really want to find is $i,j,k$ such that $i<A[n]$ and $\sum_{l=j}^k |A[l]-i| \leq B$ and $k-j$ is as large as possible. As it stands your description does not match your example. $\endgroup$
    – Tony Huynh
    Commented Nov 13, 2012 at 16:55
  • $\begingroup$ Why it does not? Can you explain? $\endgroup$
    – paramar
    Commented Nov 13, 2012 at 20:42
  • $\begingroup$ For your sum you are summing over the entire array, but in your example you want the best contiguous subarray. I assume your example is what you want. $\endgroup$
    – Tony Huynh
    Commented Nov 14, 2012 at 0:17
  • $\begingroup$ It is linear, actually. Just realize that if $a_k$ to $a_m$ is the answer, then $i$ is just the middle term. Now just move three markers left to right, spending constant time on the updates of a few relevant quantities. I'll post the algorithm when I have more time unless somebody else does it earlier :-). $\endgroup$
    – fedja
    Commented Nov 15, 2012 at 13:20

2 Answers 2

Reset to default
0
$\begingroup$

It seems that $O(n \log (n))$ is possible. Just process the array from left to right as follows. At time $t$ we store both $\mathbf{X}_t$ and $\mathbf{Y}_t$ which are respectively the best valid sequence with indices in $\{1, \dots, t\}$ and the best valid sequence which ends with $A[t]$. At time $t+1$ we update $\mathbf{X}_t$ and $\mathbf{Y}_t$ as follows. If $(\mathbf{Y}_t, A[t+1])$ is a valid sequence of length longer than $\mathbf{X}_t$, then we set

$\mathbf{X}_{t+1}:=(\mathbf{Y}_t, A[t+1])$ and $\mathbf{Y}_{t+1}:=(\mathbf{Y}_t, A[t+1])$.

Otherwise, we set $\mathbf{X}_{t+1}:=\mathbf{X}_t$ and we can compute $\mathbf{Y}_{t+1}$ in $O(\log (n))$-time via binary search.

Improve this answer
$\endgroup$
0
$\begingroup$

This seems to work, but you'd better check for idiotic mistakes :).

import math;

srand(23);

int N=60;

int[] a;
for(int k=0;k<N;++k) a[k]=rand()%55;
a=sort(a); 


int B=18;

a[N]=a[N-1]+B+1;

int K=0,k=0,m=0,s=0,S=0;

while(true)
{
while((k+m<N)&&(S<=B))
{
++m; S+=a[k+m]-a[s]; s+=m%2;  
K=k; 
}
if (k+m==N) {write(K,m-1); break;}
else {++k; ++s; S+=a[k+m]-a[s-1]-a[s-m%2]+a[k-1];} 
}

write(a);
pause();
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .