After ordering, you can solve it like the Longest Increasing Sequence (LIS)
problem, using Dynamic Programming.
2010/5/19 bob198107 robertosp...@gmail.com
Hi.
First: I'm new in ACM. 2 day took me to find out how to read and write
data in the tasks. There should be some sample code for beginners for
this.
Second: For me it is not clear what should be done, even if I read the
text of the tasks few times. I wonder if I am so intellectually
limited or it has to be so, but I don't know how to bite it.
Third: I sit on problem
103 Stacking Boxes. I sorted input rows (each box lengths
increasingly). Then I thought I have to sort boxes by the capacity or
something like that. So I sorted boxes by perimeter increasingly. And
then check if boxes nest to each other starting from the smallest one.
For sample input data from uva.onlinejudge.org and www.algorithmist.com
it works fine. For my data too. But it has to be wrong cause' of
Wrong answer if I submit the code. I would like my algorithm to
work.
Fourth: Solution from
http://cmagical.blogspot.com/2010/01/dowloads-1submitted-solutions-to...
works but I found place which I don't really understand:
#includestdio.h
#includestdlib.h
const int MAX = 33;
int boxes[MAX][12];
int rawIndex[MAX], v[MAX];
int path[MAX], rawsNumber, dimention;
int compare(const void *a, const void *s) {
return *(int *)a - *(int *)s;
}
int compareRaws(int n, int m){
for (int i = 0; i dimention; i++) {
if (boxes[n][i] = boxes[m][i]) {
return 0;
}
}
return 1;
}
void sortIndexes() {
for (int i = 0; i rawsNumber - 1; i++) {
for (int j = i + 1; j rawsNumber; j++) {
if (compareRaws(rawIndex[i], rawIndex[j])) {
rawIndex[i] ^= rawIndex[j] ^= rawIndex[i] ^=
rawIndex[j];
}
}
}
}
void print(int n){
if (path[n] == -1) {
printf(%d, rawIndex[n] + 1);
return;
}
print(path[n]);
printf( %d, rawIndex[n] + 1);
}
void solveCase() {
int max, indexSize = 0, last;
int par;
sortIndexes();
-- THIS PLACE I
DON'T UNDERSTAND
for (int i = 0; i rawsNumber; i++) {
max = 0;
par = -1;
for (int j = i - 1; j = 0; j--) {
if (compareRaws(rawIndex[i], rawIndex[j])) {
if (v[j] max) {
max = v[j];
par = j;
}
}
}
path[i] = par;
v[i] = max + 1;
if (v[i] indexSize) {
indexSize = v[i];
last = i;
}
}
printf(%d\n, indexSize);
print(last);
putchar('\n');
}
void readCase(){
for (int i = 0; i rawsNumber; i++) {
rawIndex[i] = i;
for (int j = 0; j dimention; j++) {
scanf(%d, boxes[i][j]);
}
qsort(boxes[i], dimention, sizeof(int), compare); // sorting
every read raw
}
}
int main(int argc, char *argv[]) {
while (scanf(%d%d, rawsNumber, dimention) == 2) {
readCase();
solveCase();
}
return 0;
}
It's kind of sorting indexes of raws by comparing values of two fields
i and j for each i and j. Rest of it is the algorithm I can imagine.
So any suggestions or reply to my rubbishy writing pleased welcome.
--
You received this message because you are subscribed to the Google
Groups acm_solver group.
To post to this group, send email to acm_sol...@googlegroups.com.
To unsubscribe from this group, send email to acm_solver
+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/acm_solver?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mario Ynocente Castro
Undergraduate Student of System Engineering
National University of Engineering, Peru
http://sites.google.com/site/ycmario
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
