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