0
$\begingroup$


recently i was solving a programming question on uva judge Stacking boxes
link to the problem : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
EXPLANATION PART
consider a box with n-dimension and there are k different boxes with n dimension each
so the task is simple we have two insert one box into another and we have to find maximum number of boxes which can be inserted one after the another rotation is also allowed around different axis
for example there are 4 box with 2 dimension
5 2
1 1
5 8
3 2
so the boxes 1 can be rotated and can be inserted into 3 and 2 can be inserted into 1 so the maximum is 3
i have a question that why topological ordering works here why not normal sorting works what i did was first i sorted all the edges of one boxes in increasing order and then sorted all the boxes in increasing order based on their first index and after that i calculated the longest increasing subsequence

$\endgroup$
  • $\begingroup$ You should include a complete description of the problem in your question. The linked page might disappear in the future. $\endgroup$ – Yuval Filmus Jul 1 '18 at 9:11
0
$\begingroup$

Standard sorting algorithms assume a total ordering: given any two elements, the first is either greater than, equal to, or less than the second. (And this relationship has a few other useful properties, like transitivity.)

However, what you have here is only a partial ordering. Given two boxes, the first might fit into the second, or the second might fit into the first, or they might be the same size…or, neither might fit inside the other. (10, 1) and (2, 5) fall into this last category.

Standard sorting algorithms will choke on this. But topological sorting only needs a partial ordering, and is also more efficient (running in linear time instead of linearithmic). So it's the right tool for the job here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.