## 11598 - Optimal Segments

All about problems in Volume CXV. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

### 11598 - Optimal Segments

Hi, i am really curious about this problem. i manage to solve this using some kind of DP similar to partitioning problem but with additional upper-bounding rule. But still, i got WA from time to time. Is there something i am missing? or is there any crucial or tricky cases, or perhaps, "dirty" string input data?
Please help me , i have checked my solution using many many cases, but still i can't find any mistake.... maybe those who have solved this one can share their ideas?

Thx before
ravael
New poster

Posts: 2
Joined: Wed Sep 02, 2009 8:24 pm

### Re: 11598 - Optimal Segments

Try this case

Code: Select all
`Input30 516 X 25 X 2 9 22 X 19 10 15 X 1 11 11 X 16 3 9 10 12 13 25 3 4 21 X 24 X XOutputCase 1: 17179869184 (16 X 25 X 2)(9 22 X 19)(10 15 X 1 11 11)(X 16 3 9 10 12 13)(25 3 4 21 X 24 X X)`

sohel
Guru

Posts: 865
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

### Re: 11598 - Optimal Segments

thx for the case. But my solution still produce the correct one. is there any special case or any tips?
btw here is my code :

Code: Select all
`#include<cstdio>#include<algorithm>using namespace std;#define INF -9999char ch,*ptr;int v[110][110],ok,pos[110][110],b[110],n,k,f,ts,i,j,p,kk,sum,id,r,jum,mini,lim,par[110],res[110],ans,mm[1000],ar[1000];char s[11100];int go(int x,int y){    int ada,sum=0;    if(x==n && y==k){        ok=1;        return -INF;    }    if(x==n) return INF;    if(y==k) return INF;    if(v[x][y]!=-1) return v[x][y];    v[x][y]=INF;    ada=0;    for(int i=x;i<n;i++){        sum+=b[i];           if(sum>lim) break;        if(b[i]==0) ada=1;        if(ada){            if(go(i+1,y+1)==INF) continue;            int xx=min(sum,go(i+1,y+1));               if(v[x][y]<=xx){                v[x][y]=xx;                pos[x][y]=i;               }           }    }       if(ada) return v[x][y];    return INF;}bool gt(){    for(int i=0;i<kk;i++)       if(par[i+1]-par[i]>res[i+1]-res[i]) return true;       else if(par[i+1]-par[i]<res[i+1]-res[i]) return false;            return false;}int main(){    scanf("%d",&ts);    while(ts--){        scanf("%d %d",&n,&k);        scanf("%c",&ch);        gets(s);        while(strcmp(s,"")==0) gets(s);        ptr=strtok(s," ");        n=sum=0;        int total=0;        while(ptr!=NULL){            if(strcmp(ptr,"X")==0) b[n++]=0;            else b[n++]=atoi(ptr);            total+=b[n-1];            ptr=strtok(NULL," ");           }        memset(mm,0,sizeof(mm));        for(i=0;i<n;i++){            sum=b[i];            mm[sum]=1;            for(j=i+1;j<n;j++){                sum+=b[j];                mm[sum]=1;               }           }        int num=0;        for(i=0;i<=total;i++) if(mm[i]) ar[num++]=i;        r=-INF;        f=0;        //printf("sum %d\n",total);        for(int x=total;x>=0;x--){            ans=x;            //printf("%d\n",ans);            ok=0;            lim=ans;            memset(v,-1,sizeof(v));            mini=go(0,0);            //printf("hm %d\n",ans);            if(!ok) continue;            f=1;            if(r<ans-mini) continue;            p=0;            kk=0;            par[0]=0;            while(p<n){                p=pos[p][kk]+1;                kk++;                   par[kk]=p;            }                   if(r>ans-mini || gt()){                //printf("%d %d %d\n",r,ans,go(0,0));                r=ans-mini;                for(i=0;i<=kk;i++) res[i]=par[i];               }        }        id++;        printf("Case %d: ",id);        if(!f){            printf("not possible!\n");            continue;        }        if(r>49) printf("overflow\n");        else{            printf("%lld ",(1LL<<(long long)r));            for(i=0;i<kk;i++){                for(j=res[i];j<res[i+1];j++){                    if(j==res[i]) printf("(");                    else printf(" ");                    if(b[j]==0) printf("X");                    else printf("%d",b[j]);                   }                   printf(")");            }                   printf("\n");                   }    }   }`

can someone please point out what's wrong with it
thx again
ravael
New poster

Posts: 2
Joined: Wed Sep 02, 2009 8:24 pm

### Re: 11598 - Optimal Segments

My algo is:
value[i] is 0, if the i-th cell is special, otherwise it is given in the input;
sm[i] = sm[i-1] + value[i], thus the weight of the segment [i,j] is calculated as follows: (1ULL << sm[j]-sm[i-1]);
pref[i] = pref[i-1] + (is_special[i] ? 1 : 0);
Now suppose (j,k) be such a state that we have optimally divided the first 1..j part into k segments,
DP: z[j][k].x = the sum of the values of the heaviest segment,
z[j][k].y = the sum of the values of the lightest segment;
So the optimal ratio is (1ULL << z[j][k].x-z[j][k].y);
Although n >= 2 and k >= 2, it does make sense to initialize z[j][1].x = z[j][1].y = sm[j],
so long as pref[j] >= 1.
To go on with our initialization, if pref[j] < k, then we mark the state (j,k) as "impossible",
otherwise we assign z[j][k].x = 63, z[j][k].y = 0 (overflow).
Now we do DP:
Code: Select all
`for k =2 to K:     for j = k to n:          if pref[j] < k:               continue //impossible          for i = j downto k:               if state z[i-1][k-1] is impossible:                       continue               w = sm[j]-sm[i-1]               p = max( w, z[i-1][k-1].x )               q = min( w, z[i-1][k-1].y )               if ( p-q < z[j][k].x-z[j][k].y ):                      z[j][k].x = p                      z[j][k].y = q                      parent[j][k] = (i-1,k-1)               else if p-q == z[j][k].x-z[j][k].y:                      u = getSolution(j,k)                      v = getSolution(i-1,k-1), v.append(j-i+1)                      if v is "better" than u:                             parent[j][k] = (i-1,k-1)`

"better" means this: u and v are the sequences of lengths of the corresponding divisions,
u is "better" than v iff for some i u[i] > v[i], and for all j < i u[j] == v[j]

My code is getting WA. What do you say?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Return to Volume CXV

### Who is online

Users browsing this forum: No registered users and 1 guest