11598 - Optimal Segments

[ravael]

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

[sohel]

Try this case

Code: Select all

Input
30 5
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

Output
Case 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)


[ravael]

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 -9999
char 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

[serur]

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?