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

off_algos
New poster
Posts: 29
Joined: Wed Nov 13, 2002 11:37 am
Location: india

Post by 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
New poster
Posts: 29
Joined: Wed Nov 13, 2002 11:37 am
Location: india

Post by 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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli
off_algos
New poster
Posts: 29
Joined: Wed Nov 13, 2002 11:37 am
Location: india

accepted in 0.00.008 sec

Post by off_algos »

thanx i got an AC
actually the prob was i was assuming that equality of sides implied fitting
thanx
minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

PLEASE, help with 103 - Time Limit Exceeded

Post by 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!!! :oops: :-? :o

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
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by 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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by 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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by 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... :P
PS: Hope I'll not need help on this problem any more.
Sean
New poster
Posts: 3
Joined: Mon Apr 21, 2003 10:39 pm

103- what case am I missing?

Post by 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
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

103 Stacking Boxes. Appeal to everyone who can help.

Post by 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? :o
2. WA? :-?

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

THANK YOU. :)
_____________
NO sigNature
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

103 - WA (i'm going crazy!) need test inputs!

Post by 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! :oops:


Greetings from Brazil, 8)

Daniel Rocha
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Some input/output from my WA program

Post by 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
New poster
Posts: 8
Joined: Mon May 12, 2003 6:13 am
Contact:

103 help

Post by powerboy »

Can anyone give me some hints as to the solution to problem 103, the stacking boxes one
Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by 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 :wink:
Mr Ekted
New poster
Posts: 1
Joined: Mon Jun 02, 2003 6:33 am

103

Post by 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. :)
Post Reply

Return to “Volume 1 (100-199)”