## 103 - Stacking Boxes

Moderator: Board moderators

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

### Re: 103 - Stacking Boxes

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

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

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;
vector<vector<int> >graph(32);
vector<vector<int> >box(32);
int dis,path,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;
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

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

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

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