Local time:  
CET time:  
Balkan Olympiad in Informatics by NET
 

View problem

Problem title: Euro
Problem number: 2
Round: DAY 2
Solution: Problem: euro

Authors: Mugurel Ionut Andreica , Mihai Patrascu

There are several solutions for this problem, having different time complexities. The most obvious solution uses a DP algorithm and has time complexity O(N2).

Let’s examine an O(N*sqrt(T)) solution (which is not so obvious). The first step is to “compress” the N values of the sequence into several contiguous intervals. The first interval contains the first K elements of the sequence, having the following property: K is N, or the sum of the first K elements is less than zero, but the sum of the first J elements is at least 0 (for any 1<=J<K). The next interval is obtained the same way, considering only the remaining N-K elements. This way, we split the subsequence into M “compressed” intervals. We can now use DP on the sequence of “compressed” intervals, the same way as for the original subsequence. This is, indeed, an improvement, as M is at most N, but the time complexity of the algorithm may still be O(N2) in the worst case. The catch is that, in order to find the optimal solution for the sequence ending with the ith interval, it is only necessary to look at the solutions for the previous sqrt(T)+1 intervals. This leads to an O(N*sqrt(T)) algorithm.

An even less obvious solution uses a geometrical approach. First, let’s consider the sequence of partial sums: S0,S1,..,SN. S0=0 and Si=Ei+Si-1 , where Ei is the ith number in the sequence given in the input file. Next, let’s consider another sequence C, where Ci=SN-Si (for any 0<=i<=N). Obviously, CN is 0. The recurrent expression for the maximum value which can be obtained by optimally splitting into intervals the first J elements (the same expression which is used for the DP solution) is: MAX[J]=max{MAX[I]+(SJ-SI)*J}, for any 0<=I<J. MAX[0]=0.

Let’s consider the following transformation. We will compute the sequence MAXV[I] (virtual max). First, we consider the integers from 0 to N, placed on the OX-axis. Then, we will consider N+1 straight lines, defined in the following way: the ith line will have the slope Ci and the origin at the point (I,MAXV[I]). MAXV[0]=0. MAXV[1]=MAXV[0]+(1-0)*C0-T. In general, MAXV[I]=max{MAXV[J]+(I-J)*CJ}-T, with 0<=J<I. The meaning of MAXV[I] is the “virtual” maximum value which can be obtained by optimally splitting into intervals the first I elements of the sequence given in the input file. The connection between MAXV[I] and MAX[I] is the following: MAXV[I]=MAX[I]+I*CI. Since CN=0, MAXV[N]=MAX[N] (the required answer). In order to compute MAXV[I], we may use different ideas. One observation is that a straight K line is “useful”, only if it is used in the computation of MAXV[K+P], with 1<=P<=T+1. This leads to an O(N*T) algorithm. A better solution would be to find the interval for which one straight line is above all other lines, by using binary search and a data structure similar to a binary indexed tree, thus obtaining an O(N*(logN)2) algorithm.

Scoring:

30% for an O(N2) solution

80% for an O(N*T) solution

100% for an O(N*sqrt(T)) and an O(N*(logN)2) solution

Source codes:

(1) -> O(N*sqrt(T))

#include <stdio.h>

#define filein "euro.in"

#define fileout "euro.out"

#define MAXN 34567

int t;

struct val {

int val, pos, back;

long long max;

} e[MAXN];

int ne;

void read_in(void)

{

int i, n, a[MAXN];

freopen(filein, "r", stdin);

scanf("%d%d", &n, &t);

for(i = 0; i < n; i++)

scanf("%d", a + i);

for(i = 0; i < n - 1; i++) {

e[ne].val += a[i];

if(e[ne].val < 0)

e[ne++].pos = i + 1;

}

e[ne].val += a[n - 1];

e[ne++].pos = n;

}

int main()

{

int i, j, totsum, parsum, back;

long long max;

read_in();

totsum = e->val;

e->back = 0;

e->max = (long long) totsum * e->pos - t;

for(i = 1; i < ne; i++) {

totsum += e[i].val;

max = (long long) totsum * e[i].pos;

back = 0;

parsum = e[i].val;

for(j = i - 1; (j >= e[i - 1].back) && (i - j <= 200); j--) {

if((long long) parsum * e[i].pos + e[j].max > max) {

max = (long long) parsum * e[i].pos + e[j].max;

back = j;

}

parsum += e[j].val;

}

e[i].back = back;

e[i].max = max - t;

}

freopen(fileout,"w",stdout);

printf("%Ldn", e[ne - 1].max);

return(0);

}

(2) -> O(N*(logN)2)

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define filein "euro.in"

#define fileout "euro.out"

#define maxn 34568

typedef struct { long li,ls,fs,fd,tata,lineindex; } nod;

double s[maxn],c[maxn],max[maxn],t;

long list[maxn];

nod arb[2*maxn];

long n,narb;

void readdata(void);

void buildtree(void);

void compute(void);

void writedata(void);

int main()

{

readdata();

buildtree();

compute();

writedata();

return 0;

}

void readdata(void)

{

long i;

double e;

freopen(filein,"r",stdin);

scanf("%ld %lf",&n,&t);

s[0]=0;

for (i=1;i<=n;i++)

{

scanf("%lf",&e);

s[i]=s[i-1]+e;

}

}

void buildtree(void)

{

long i,j,k,p;

for (i=1;i<=n;i++)

{

arb[i].li=arb[i].ls=list[i]=i;

arb[i].fs=arb[i].fd=arb[i].tata=0;

}

k=narb=n;

while (k>1)

{

j=0;

for (i=1;i<k;i++)

if (i%2==1)

{

narb++;

arb[narb].li=arb[list[i]].li;

arb[narb].ls=arb[list[i+1]].ls;

arb[narb].fs=list[i];

arb[narb].fd=list[i+1];

arb[list[i]].tata=narb;

arb[list[i+1]].tata=narb;

arb[narb].tata=0;

j++;

list[j]=narb;

}

if (k%2==1)

{

j++;

list[j]=list[k];

}

k=j;

}

}

double getmax(long i,long& lineindex)

{

long line,p;

double res;

line=-1;

p=i;

while (p>0)

{

if (arb[p].lineindex>line)

line=arb[p].lineindex;

p=arb[p].tata;

}

res=max[line]+c[line]*(i-line);

lineindex=line;

return res;

}

long locatelow(long line)

{

long poz,li,ls,m,lm;

double vline,vm;

li=line+1; ls=n; poz=n+1;

while (li<=ls)

{

m=(li+ls)>>1;

vline=max[line]+c[line]*(m-line);

vm=getmax(m,lm);

if (c[lm]<c[line])

{

if (vm<vline)

{

poz=m;

ls=m-1;

}

else

li=m+1;

}

else

ls=m-1;

}

return poz;

}

long locatehigh(long line)

{

long poz,li,ls,m,lm;

double vline,vm;

vm=getmax(n,lm);

vline=max[line]+c[line]*(n-line);

if (c[line]>c[lm] && vline>vm)

return n;

li=line+1; ls=n; poz=line;

while (li<=ls)

{

m=(li+ls)>>1;

vline=max[line]+c[line]*(long long)((m-line));

vm=getmax(m,lm);

if (c[lm]>c[line])

{

if (vm<vline)

{

poz=m;

li=m+1;

}

else

ls=m-1;

}

else

li=m+1;

}

return poz;

}

void setmax(long li,long ls,long num,long x)

{

long fs,fd;

fs=arb[num].fs;

fd=arb[num].fd;

if (li==arb[num].li && ls==arb[num].ls)

arb[num].lineindex=x;

else

if (li==arb[num].li)

{

if (arb[fd].li<=ls)

{

setmax(li,arb[fs].ls,fs,x);

setmax(arb[fd].li,ls,fd,x);

}

else

setmax(li,ls,fs,x);

}

else

if (ls==arb[num].ls)

{

if (arb[fs].ls>=li)

{

setmax(li,arb[fs].ls,fs,x);

setmax(arb[fd].li,ls,fd,x);

}

else

setmax(li,ls,fd,x);

}

else

{

if (ls<=arb[fs].ls)

setmax(li,ls,fs,x);

else

if (li>=arb[fd].li)

setmax(li,ls,fd,x);

else

{

setmax(li,arb[fs].ls,fs,x);

setmax(arb[fd].li,ls,fd,x);

}

}

}

void compute(void)

{

long i,j,p1,p2;

/* compute the C array */

for (i=0;i<=n;i++)

c[i]=s[n]-s[i];

/* init the tree */

for (i=1;i<=narb;i++)

arb[i].lineindex=0;

max[0]=0;

/* do the smart things */

for (i=1;i<n;i++)

{

max[i]=getmax(i,j)-t;

p1=locatelow(i);

p2=locatehigh(i);

if (p1<=p2)

{

setmax(p1,p2,narb,i);

}

}

}

void writedata(void)

{

long nouse;

freopen(fileout,"w",stdout);

printf("%.0lfn",getmax(n,nouse)-t);

}

Back

 
© 2003 Vâlsan Mihai Liviu & exist:create
Webmaster contact address: liviuvalsan@yahoo.com
Organisers contact address: ema@mail.dntis.ro