103 - Stacking Boxes

[LazyTym]

i solve this problem using LIS then i am trying to solve by DFS(topological sort).
But the problem is:
1. how can i find the maximum sequence from the topological order.
2.and the path of the maximum sequence from the topological order.
can anyone solve this prob using dfs.......and want some help.

[brianfry713]

Here's how I solved it:
Sort the measurements of each box, then sort the boxes by the first dimension. Then you can use LIS, making sure that the box completely fits in all dimensions.

Here is another solution description:
http://www.outsbook.com/uva/?page=probl ... ory=1&id=0

[LazyTym]

WHY WA..............

my procedure is:
1.first i take dimentions and sort them.
2.then make a directed graph according to (u,v) is the index of boxes and if v fits in u then there is a direction u to v.
3.then find topological sort of the directed graph and take the order in a stack.
4.form the stack,find the length of the longest nesting string and path.

Code: Select all

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>


using namespace std;

int k,n;
bool visited[32];
vector<vector<int> >graph(32);
vector<vector<int> >box(32);
int dis[32],path[32],index;


bool cmp(int a,int b) {
    for(int i=0;i<k;i++) {
        if(box[a][i]<=box[b][i]) return false;
    }
    return true;
}

void topoUtil(int v,stack<int>&Stack,bool visited[]) {
    visited[v]=true;
    for(int i=0;i<graph[v].size();i++) {
        if(!visited[graph[v][i]]) {
            topoUtil(graph[v][i],Stack,visited);
        }
    }
    Stack.push(v);
}

int topological_Sort()
{
    bool visited[32];
    stack<int>Stack;
    int m=0;
    for(int i=0;i<=32;i++) {
        visited[i]=false;
    }

    for(int i=1;i<=n;i++) {
        if(visited[i]==false) {
            topoUtil(i,Stack,visited);
        }
    }
    //cout<<endl<<endl;
    index=0;
    while(!Stack.empty()) {
            int u=Stack.top();
           // cout<<u<<" ";
            for(int i=0;i<graph[u].size();i++) {
                if(dis[graph[u][i]]<dis[u]+1) {
                    dis[graph[u][i]]=dis[u]+1;
                    path[graph[u][i]]=u;
                }
                
                if(dis[graph[u][i]]>m) {
                    m=dis[graph[u][i]];
                    index=graph[u][i];
                }
            }
            Stack.pop();
        }
       // cout<<endl;
   return m;
}

int main()
{

    while(cin>>n>>k) {

        for(int i=0;i<=n;i++) {
            dis[i+1]=1;
            path[i+1]=i+1;
            graph[i].clear();
            box[i].clear();
        }
        int a;
        for(int i=0;i<n;i++) {
            //box[i].id=i+1;
            for(int j=0;j<k;j++) {
                cin>>a;
                box[i].push_back(a);
            }
            sort(box[i].begin(),box[i].begin()+k);
        }

        if(n==1) {
            cout<<"1"<<endl;
            cout<<"1"<<endl;
            continue;
        }

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

            for(int j=i+1;j<n;j++) {
                if(cmp(i,j)) {
                    graph[i+1].push_back(j+1);
                }
                else if(cmp(j,i)) {
                    graph[j+1].push_back(i+1);
                }
            }
        }


        cout<<topological_Sort()<<endl;
        while(path[index]!=index) {
            cout<<index<<" ";
            index=path[index];
        }
        cout<<index<<" ";
        cout<<endl;
    }
    return 0;
}

[brianfry713]

Don't print a space at the end of a line.

[TrL]

Are we to assume that any measurement given will fit into a 32-bit int? If not then I think that comparisons will need to be done on the basis of strings for each slide length of each box, but this strikes me as complicated. Can anyone confirm whether or not this assumption leads to CA?

i.e. do we need to handle the following input or larger?

Code: Select all

2 2
100000000000000001 100000000000000002
100000000000000003 100000000000000004

[Hallway]

i am wandering why this kind of compare works

Code: Select all

struct box {
	int id;
	vector<int> dimension;
};
bool operator<(const box &b1, const box &b2) {
	int size = b1.dimension.size();
	for (int i = 0; i < size; i++) {
		if (b1.dimension[i] != b2.dimension[i])
			return b1.dimension[i] < b2.dimension[i];
	}
	return 0;
}

but this kind of compare does not work for sorting the boxes

Code: Select all

bool operator<(const box &b1, const box &b2) {
	int size = b1.dimension.size();
	for (int i = 0; i < size; i++) {
		if (b1.dimension[i] >= b2.dimension[i])
			return 0;
	}
	return 1;
}