103 - Stacking Boxes

[off_algos]

thanx
the idea of lexical sorting by soritng on the last first and then proceeding upwards is correct for sure

id soon write here the reference to this statement

can u still help me

[off_algos]

well please see this example of card sorting in
DONALD E KNUTH
SORTING AND SEARCHING(vol 3)
sec. 5.2.5 Soring by distribution

[epsilon0]

i'm sorry your code is too messy so i can't really read thru it (try to use functions and some comments)

but i can still try to help you since i solved it.

ok i see why you make the 2nd sort of all "strings" in lexicographic order. but this doesn't imply a box will fit in all the boxes after it in this sorted list

the box 2 3 doesn't fit in the box 3 3 because the dimensions of the inner box have to be STRICTLY less than that of the outter box. perhaps you didnt take care of it? it that's the problem, you'll hopefully fix it very easily.

other problems could be that you don't find the LONGER possible chain of nested boxes, or that you don't print them in the correct order (from inner box to outter box), or that you have another formatting problem, like wrong numbering of the boxes (it starts from 1, not from 0, etc...)

i hope this helped... perhaps it's something else too. what is sure is that using functions and comments will make it easier on yourself and will allow others to understand how your program works and detect the problem in it.

good luck

[off_algos]

thanx i got an AC
actually the prob was i was assuming that equality of sides implied fitting
thanx

[minskcity]

My code works good on examples, but I get "Time Limit Exceeded" error when submit it to judge. Is there a problem with speed of my algorithm or wrong way of input? PLAESE HELP!!!

Code I submite:

[cpp]/*
@JUDGE_ID: 19691CE 103 C++ "BSU Lyceum algorithms"
*/
#include <iostream.h>
int k,n,temp,max,iteration;
int data[30][10];
int result[30];
int current[30];

char possible(int n1, int n2){
for(int i = 0; i < n; i++)
if(data[n1] <= data[n2]) return 0;
return 1;
}

void recur(int start){
iteration++;
current[iteration] = start;
if(iteration > max){
max = iteration;
for(int i = 0; i <= max; i++)
result = current;
}
for(int i = 0; i < k; i++)
if(possible(start,i)) recur(i);

iteration--;
return;
}

int main(){
while(cin >> k >> n){
max = -1;
for(int i = 0; i < k; i++)
for(int j = 0; j < n; j++)
cin >> data[j];

for(int i = 0; i < k; i++)
for(int j1 = 0; j1 < n - 1; j1++)
for(int j2 = j1 + 1; j2 < n; j2++)
if(data[j1] > data[j2]){
temp = data[j1];
data[j1] = data[j2];
data[i][j2] = temp;
}
for(int i = 0; i < k; i++){
iteration = -1;
recur(i);
}
cout << (max + 1) << "\n";
for(int i = max; i >= 0; i--)
cout << (result[i] + 1) << " ";
cout << "\n";
};
return 0;
}

// @END_OF_SOURCE_CODE[/cpp]

[turuthok]

Looks like your "recur" function searches for the permutations of possible sequences. For 30 boxes, you would definitely timeout.

You need to find a better strategy to replace your "recur" function.

-turuthok-

[turuthok]

Here's a good resource of dynamic programming by Steven Halim:

http://www.comp.nus.edu.sg/~stevenha/pr ... g_dp1.html

For this 103 - Stacking Boxes problem, you might want to see the section 2.3. Longest Inc/Decreasing Subsequence (LIS/LDS).

-turuthok-

[minskcity]

Thanks a lot - I was so stupid - did not test my code on the worst case -
30 1
1 - 30
Now I know what my mistake was...
PS: Hope I'll not need help on this problem any more.

[Sean]

I'm getting wrong answers for #103, and I've tested it on a bunch of cases (including 0 and 1 boxes, and 30 boxes of 10 dimensions), and it seems to work. I think I'm missing a special case, but I'm not sure what. Anyone have an idea?

Here's the code:

Code: Select all

/*   @JUDGE_ID:  30340XC  103   C++   "Stacking Boxes"   */ 
#include <iostream>

#include <string>
using namespace std;

int Boxes[30][30];
	int num_boxes, dim;

bool Less_Than[30][30];
bool cur_path[30];
int history[30];
int best_nesting = 0;
string best_path;
void Swap(int& x, int &y){
  int temp = x;
  x = y;
  y = temp;
}

void Create_Best_Path(int history[], int cur_nesting){
 best_path = "";
 for(int i = 0; i < cur_nesting; i++){
  if(history[i] > 8)
    best_path = best_path + (char)((history[i]+1)/10 + '0') + (char)((history[i]+1)%10+'0') + " ";
  else
   best_path = best_path + (char)((history[i]+1) + '0') + " ";
   
 }
 
}
void Sort(){
  for(int i = 0; i < num_boxes; i++){
    for(int j = 0; j < dim; j++){
      for(int k = 0; k < dim; k++)
        if(Boxes[i][j] > Boxes[i][k])
          Swap(Boxes[i][j], Boxes[i][k]);
    }
     
  }
  

}

bool Find_Smallest_Path(bool cur_path[], int history[], int cur_nesting){
  if(cur_nesting > best_nesting){
    best_nesting = cur_nesting;
    Create_Best_Path(history, cur_nesting);
    if(best_nesting == num_boxes)
      return true;
      
  }
  for(int i = 0; i < num_boxes; i++){
      if(cur_nesting == 0){
        cur_path[i] = true;
        history[0] = i;
        bool done = Find_Smallest_Path(cur_path, history, 1);
        if(done)
          return true;
        else
          cur_path[i] = false;
      }
      else{
        
      if(Less_Than[history[cur_nesting-1]][i] && !cur_path[i]){
        history[cur_nesting] = i;
        cur_path[i] = true;
        bool done = Find_Smallest_Path(cur_path, history, cur_nesting+1);
        if(done)
          return true;
        else{
          cur_path[i] = false;
       }
      }
    }
  }
  return false;
}

bool Fits_In(int a, int b){
  for(int i = 0; i < dim; i++)
    if(Boxes[a][i] >= Boxes[b][i])
      return false;
      
  return true;
}
int main()
{

	

	while(cin >> num_boxes >> dim){
	  for(int i = 0; i < num_boxes; i++)
	    for(int j = 0; j < dim; j++)
	      cin >> Boxes[i][j];
	
	
	   Sort();
    for(int i = 0; i < num_boxes; i++){
      for(int j = 0; j < num_boxes; j++){
        if(Fits_In(i,j)){
          Less_Than[i][j] = true;
          
         }
        else{
          Less_Than[i][j] = false;
          
        }
       
      }
   
    }
    best_nesting = 0;
    int cur_nesting = 0;
    best_path = "";
    history[0] = 0;
    for(int i = 0; i < dim; i++)
      cur_path[i] = false;
 
    Find_Smallest_Path(cur_path, history, cur_nesting);
    cout << best_nesting << endl;
    cout << best_path << endl;
   }
	return 0;
}

I know it's not the fastest way to do things, and I'm not really worried about that (I'm actually kinda curious to see how fast the judge program is- then I can fix it) But it's not giving me "time limit exceeded", it's giving me "wrong answer".

Any ideas?

[Farid Ahmadov]

I think my program is OK. But I don't know why I WA??? Maybe you can help me.

My program:

[pascal]program Stacking_Boxes;

var
i,j,k,d,x,y,maxx: Integer;
a: array[1..30,1..10] of Integer;
b,f,sum: array[1..30] of Integer;
z: array[1..30] of boolean;

procedure swap(var a,b: Integer);
var
c: Integer;
begin
c:=a; a:=b; b:=c;
end;

procedure insert(x: Integer);
var
y: Integer;
begin
y:=j;
a[i,y]:=x;
while (a[i,y]<a[i,y-1])and(y>1) do
begin
swap(a[i,y],a[i,y-1]);
dec(y);
end;
end;

function fit(x,y: Integer): Boolean;
var
f: Boolean;
i: Integer;
begin
f:=true;
for i:=1 to d do
if a[y,i]<=a[x,i] then
begin
f:=false; break;
end;
fit:=f;
end;

begin
{assign(input,'103.in'); reset(input);
assign(output,'103.out'); rewrite(output);}
while not eof do
begin
readln(k,d);
fillchar(sum,sizeof(sum),0);
fillchar(f,sizeof(f),0);
fillchar(z,sizeof(z),0);
for i:=1 to k do
begin
for j:=1 to d do
begin
read(x); insert(x);
inc(sum,x);
end;
b:=i;
readln;
end;
for i:=1 to k do
for j:=1 to k-i do
if sum[b[j]]>sum[b[j+1]] then swap(b[j],b[j+1]);
for i:=1 to k-1 do
begin
for j:=i+1 to k do
if fit(b,b[j]) then
begin
f[b]:=b[j];
break;
end;
end;
maxx:=1;
for i:=1 to k-1 do
if not z[b] then
begin
j:=b; x:=1;
while (f[j]>0)and(x<k) do
begin
z[b[j]]:=true;
j:=f[j];
inc(x);
end;
if x>maxx then
begin
maxx:=x; y:=b;
end;
end;
writeln(maxx);
write(y); y:=f[y];
while y<>0 do
begin
write(' ',y); y:=f[y];
end;
writeln;
while not (eoln or eof) do readln;
end;
{close(input); close(output);}
end.

[/pascal]

My questions:
1. What must I answer if dimension is 1? Is there any box or polygon?
2. WA?

If you can please give some tests to test it or the other version of it.

THANK YOU.

[danielrocha]

Hello everyone, I'm needing some help with 103. I've tried EVERY test input I could find (and even made out a couple), the output is OK (always remembering: "If there is more than one longest nesting string then any one of them can be output. ") but the judge is giving me Wrong Answer. I've tried everything!!! My code is below, and here is some quick explanation about it:
1. "tabuleiro" is a [numberofboxes][numberofdimensions] array that stores the so-called "boxes" (vectors).
2. After reading the vectors I order the dimensions of each one of them. (ex. 2 3 1 -> 1 2 3);
3. Then I order the vectors according to their first dimension (ex. 2 3 4 \n 1 2 3 -> 1 2 3 \n 2 3 4).
4. Then I try to fit the first "box" into the second (the "encaixa" function, wich uses the "encaixou" function -> "encaixou" returns 0 or 1 if two vectors fit into each other). If it fits, I try to fit the second one into the third. Etc.
5. Some quick notes: the final order of the longest nest is stored in "ordem", the original order of the vectors is stored in "tabelaantiga" (the relation between the new/reordered table and the original is trough the "linhanaantiga" function).

I would really appreciate if someone could help me out here. If you don't have enough pacience to read my code, just reply with some test inputs.

[cpp]
#include <iostream>
#include <stdio.h>
using namespace std;

int numcaixas, dimensoes, *ordem, longest=0;
int ** tabuleiro, **tabuleiroantigo;

int linhanaantiga(int linhanova)
{
int contador=0;
for (int i=0;i<numcaixas;i++)
{
for (int j=0;j<dimensoes;j++)
{
if (tabuleiro[linhanova][j]==tabuleiroantigo[j]) contador++;
else break;
}
if (contador>=dimensoes) return i;
contador = 0;
}
return 0;
}

int encaixou(int linha1, int linha2) {
int contador=0;
for (int i=0;i<dimensoes;i++)
{
if (tabuleiro[linha1]<tabuleiro[linha2]) contador++;
else break;
}
if (contador==dimensoes) return 1;
else return 0;

return 0;
}


int encaixa(int linha) {
int contadordeencaixes=0;
int ultimo = linha;
for (int i=linha;i<numcaixas-1;i++) {
if (encaixou(ultimo,i+1)) {

ordem[contadordeencaixes]=(linhanaantiga(ultimo)+1);
contadordeencaixes++;
ordem[contadordeencaixes]=(linhanaantiga(i+1)+1);
ultimo = i+1;

}
}
return contadordeencaixes;
}

void ordernarlinha(int linha)
{
int aux;
for (int i=0;i<dimensoes;i++)
for (int j=i;j<dimensoes;j++)
if (tabuleiro[linha]>tabuleiro[linha][j])
{
aux = tabuleiro[linha];
tabuleiro[linha] = tabuleiro[linha][j];
tabuleiro[linha][j] = aux;
}
}


void ordenarcolunas()
{
int *aux;
for (int i=0;i<numcaixas-1;i++)
{
for (int j=i;j<numcaixas;j++)
{
for (int k=0;k<dimensoes;k++)
{
if (tabuleiro[k]>tabuleiro[j][k])
{
aux = tabuleiro;
tabuleiro = tabuleiro[j];
tabuleiro[j] = aux;
break;
}
else if (tabuleiro[k]<tabuleiro[j][k])
break;
}
}
}
}

int main()
{

int i,j,contador=1;
int *novaordem;

while (scanf("%d %d",&numcaixas,&dimensoes)!=EOF)
{
if (numcaixas>0) {
if (contador!=1) cout << "\n";
// CRIA A MATRIZ QUE VAI COMPORTAR AS CAIXAS
tabuleiro = (int **) new int[numcaixas];
for (i=0;i<numcaixas;i++)
tabuleiro[i] = (int*) new int[dimensoes];

// CRIA A MATRIZ QUE VAI SERVIR DE ESPELHO, APOS A ORDENACAO
tabuleiroantigo = (int **) new int[numcaixas];
for (i=0;i<numcaixas;i++)
tabuleiroantigo[i] = (int*) new int[dimensoes];

for(i=0;i<numcaixas;i++)
for(j=0;j<dimensoes;j++)
cin >> tabuleiro[i][j];

for (i=0;i<numcaixas;i++) ordernarlinha(i);

for(i=0;i<numcaixas;i++)
for(j=0;j<dimensoes;j++)
tabuleiroantigo[i][j]= tabuleiro[i][j];

ordenarcolunas();

ordem = new int[numcaixas];
novaordem = new int[numcaixas];
for (i=0;i<numcaixas;i++) {
ordem[i] = -1;
novaordem[i] = -1;
}

longest = 0;

int atual=0;
for (i=0;i<numcaixas;i++) {
atual = encaixa(i);
if (atual>longest) {
longest = atual;
for (j=0;j<numcaixas;j++) novaordem[j] = ordem[j];
}
}

cout << longest+1 << "\n";
if (longest+1==1) cout << "1";
else {
for (i=0;i<longest+1;i++) {
if (i==longest) cout << novaordem[i];
else cout << novaordem[i] << " ";
}
}

// DESTROI AS MATRIZES, LIMPANDO A MEMORIA
for (i=0;i<numcaixas;i++)
{
delete [ ] tabuleiro[i];
delete [ ] tabuleiroantigo[i];
}
delete [ ] tabuleiroantigo;
delete [ ] tabuleiro;
contador++;
}
}

return 0;
}
[/cpp]

Thanks again for the pacience, and sorry for my (really) bad english!


Greetings from Brazil,

Daniel Rocha

[danielrocha]

Some sample inputs/outputs from my program:

Code: Select all

INPUT
1 7
1 2 3 0 0 0 0
OUTPUT
1
1

INPUT
4 7
3 2 1 1 2 3 4
0 0 0 5 6 7 9
9 3 2 2 35 8 9
-1 -1 -1 -20 2 5 6
OUTPUT
3
4 2 3

INPUT (sample input, from the problem's page)
5 2
3 7
8 10
5 2
9 11
21 18
OUTPUT
5
3 1 2 4 5

INPUT (sample input, from the problem's page)
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
OUTPUT
4
7 2 5 8

INPUT
0 0
OUTPUT
(ignores)

INPUT
0 1
OUTPUT
(ignores)

INPUT
5 1
1
3
2
5
4
OUTPUT
1 3 2 5 4

INPUT (sample input given at another message in the board)
10 10
1 2 3 4 5 6 7 8 9 10
4 5 2 3 3 5 6 7 9 10
20 30 2 1 3 4 5 6 9 10
1 2 3 4 5 6 7 8 9 10
5 2 3 4 5 6 9 10 22 30
2 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11 12
98 23 43 53 23 43 53 10 4 90
1 1 1 2 3 4 5 9 10 11
OUTPUT
4
1 6 8 9

Are there any inputs I'm missing?

Thanks,
Daniel Rocha

[powerboy]

Can anyone give me some hints as to the solution to problem 103, the stacking boxes one

[Hisoka]

1. sort descending for each box dimension.
2. sort descending for each box.
3. use LDS to solve this problem.

for point 1 adn 2 I mean like this:
input:
1 5 2 6 3 7
4 2 6 1 7 4
8 4 2 8 4 6

point 1:
7 6 5 3 2 1
7 6 4 4 2 1
8 8 6 4 4 2

point 2:
8 8 6 4 4 2
7 6 5 3 2 1
7 6 4 4 2 1

after that you use LDS.

GOOD LUCK

[Mr Ekted]

Can someone please provide some test data that creates a very complex graph. I'm starting to think the special processing code is wrong.