Maximizing number of factors contributing in the sum of sorted array bounded by a value - MathOverflow

Maximizing number of factors contributing in the sum of sorted array bounded by a value

2012-11-13T13:51:33Z

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

Answer by Tony Huynh for Maximizing number of factors contributing in the sum of sorted array bounded by a value

2012-11-13T17:31:54Z

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.

Answer by fedja for Maximizing number of factors contributing in the sum of sorted array bounded by a value

2012-11-16T05:06:16Z

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();