Page 3 of 14
Posted: Tue Jan 07, 2003 7:36 am
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
Posted: Tue Jan 07, 2003 8:33 am
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
Posted: Tue Jan 07, 2003 1:55 pm
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
accepted in 0.00.008 sec
Posted: Wed Jan 08, 2003 2:22 pm
by off_algos
thanx i got an AC
actually the prob was i was assuming that equality of sides implied fitting
thanx
PLEASE, help with 103 - Time Limit Exceeded
Posted: Fri Feb 07, 2003 11:13 pm
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!!!
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]
Posted: Sat Feb 08, 2003 7:23 am
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-
Posted: Sat Feb 08, 2003 7:37 am
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-
Posted: Sat Feb 08, 2003 8:53 am
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...
PS: Hope I'll not need help on this problem any more.
103- what case am I missing?
Posted: Mon Apr 21, 2003 10:47 pm
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?
103 Stacking Boxes. Appeal to everyone who can help.
Posted: Thu Apr 24, 2003 5:30 pm
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?
2. WA?
If you can please give some tests to test it or the other version of it.
THANK YOU. 
103 - WA (i'm going crazy!) need test inputs!
Posted: Sun Apr 27, 2003 3:38 am
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!
Greetings from Brazil, 
Daniel Rocha
Some input/output from my WA program
Posted: Sun Apr 27, 2003 1:11 pm
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
103 help
Posted: Sun Jun 01, 2003 5:27 am
by powerboy
Can anyone give me some hints as to the solution to problem 103, the stacking boxes one
Posted: Sun Jun 01, 2003 6:29 am
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
103
Posted: Tue Jun 03, 2003 10:59 am
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.