103 - Stacking Boxes

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

Moderator: Board moderators

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

Re: 103 - Stacking Boxes

Post by LazyTym » Tue Nov 25, 2014 11:30 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 103 - Stacking Boxes

Post by brianfry713 » Wed Dec 03, 2014 4:40 am

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
Check input and AC output for thousands of problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

Re: 103 - Stacking Boxes

Post by LazyTym » Thu Dec 11, 2014 8:18 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 103 - Stacking Boxes

Post by brianfry713 » Thu Dec 11, 2014 10:15 pm

Don't print a space at the end of a line.
Check input and AC output for thousands of problems on uDebug!

TrL
New poster
Posts: 2
Joined: Sun Dec 06, 2015 3:01 pm

Large inputs

Post by TrL » Sun Dec 06, 2015 3:10 pm

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
New poster
Posts: 2
Joined: Thu Mar 30, 2017 10:30 am

Re: 103 - Stacking Boxes

Post by Hallway » Thu Aug 31, 2017 11:37 am

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

Post Reply

Return to “Volume 1 (100-199)”