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: > > #include<stdio.h> > #include<stdlib.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.com<algogeeks%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.
