690 - Pipeline Scheduling

[wassup_online]

Need help in the Pipeline Schedulig, the 690 problem.
My problem exactly is that I don't know how to start, and I need to do this problem to a class. Please Help!!

[Yu Fan]

Code: Select all

#include <stdio.h>
bool map[5][30];
int e[5];
int n,would[30],w;
bool insertable(int a1,int a2,int a3,int a4,int a5);
void test(int s1,int s2,int s3,int s4,int s5,int i,int start,int x);
int min;
inline int _min(int a,int b) {
    if(a<b)
        return a;
    return b;
}
int main() {
    int i,j;
    char p[30];
    int s[5];
    while(scanf("%d",&n)&&n>0) {

        for(i=0;i<5;i++) {
            scanf("%s",&p);
            for(j=0;j<n;j++)
                map[i][j]=(p[j]=='X');
        }
        for(i=0;i<5;i++) {
            e[i]=0;
            for(j=n-1;j>=0;j--)
                e[i]=e[i]*2+map[i][j];
            s[i]=e[i];
        }
        w=0;
        for(i=0;i<n;i++) {
            if(insertable(s[0],s[1],s[2],s[3],s[4]))
                would[w++]=i;
            for(j=0;j<5;j++)
                s[j]/=2;
        }
        would[w++]=n;
        min=10*n;
        test(e[0],e[1],e[2],e[3],e[4],1,0,0);
        printf("%d\n",min+n);
    }
    return 0;
}
void test(int s1,int s2,int s3,int s4,int s5,int i,int start,int x) {
    if(start+would[x]*(10-i)>=min)
        return;
        
    if(i==10) {
        if(start<min)
            min=start;
        return ;
    }
    
    int ss1,ss2,ss3,ss4,ss5,prev=0,k;
    ss1=s1;
    ss2=s2;
    ss3=s3;
    ss4=s4;
    ss5=s5;
        
    if(i==1) {
        for(int j=0;j<w;j++) {
            for(;prev<would[j];prev++) {
                ss1/=2;
                ss2/=2;
                ss3/=2;
                ss4/=2;
                ss5/=2;
            }
                    
            if(insertable(ss1,ss2,ss3,ss4,ss5))
                test(ss1+e[0],ss2+e[1],ss3+e[2],ss4+e[3],ss5+e[4],i+1,would[j]+start,j);
        }
    } else {
        for(int j=x;j<w;j++) {
            for(;prev<would[j];prev++) {
                ss1/=2;
                ss2/=2;
                ss3/=2;
                ss4/=2;
                ss5/=2;
            }
            if(insertable(ss1,ss2,ss3,ss4,ss5))
                test(ss1+e[0],ss2+e[1],ss3+e[2],ss4+e[3],ss5+e[4],i+1,would[j]+start,x);
        }
    }
}
bool insertable(int a1,int a2,int a3,int a4,int a5) {
    return ((a1+e[0])==(a1^e[0]))&&((a2+e[1])==(a2^e[1]))&&((a3+e[2])==(a3^e[2]))&&((a4+e[3])==(a4^e[3]))&&((a5+e[4])==(a5^e[4]));
}

[stubbscroll]

Your program gives the wrong answer on this test case:

Code: Select all

11
X..........
...........
...........
X..........
.X.......XX
0

Correct answer is 38, your program outputs 40. By the way, here's the schedule that my program found (for the bottom two lines:)

Code: Select all

0123456789012345678901234567890123456789
----------------------------------------
0  1 2 3  4      5  6 7 8  9
 0  1 2 30041122335446 7 8559667788 99

[Yu Fan]

Thanks for your input and i now have to fight with TLE......

[Yu Fan]

Finally I got AC in 3.7sec...
how slow it is.......><