Uva 103 Stacking Boxes

Problem: Download

---

Background Study

---

Input: Given a sequence
Output: The longest subsequence of the given sequence such that all values in this longest subsequence is strictly increasing/decreasing.
DP solution for LIS problem: Complexity O(N^2) (this code check for increasing values):
Example of LIS height sequence: 1,6,2,3,5
length initially: [1,1,1,1,1] - because max length is at least 1 rite...
Predecessor initially: [nil,nil,nil,nil,nil] - assume no predecessor so far
We can reconstruct the solution using recursion and predecessor array.
Reference: "Art of Programming Contest, C programming | Data Structure | Algorithms" , "Ahmed Shamsul Arefin", 2nd Edition.


Another Alogrithm:

Implementation in C:
Implementation in C++:
Faster Algorithm
There's also an O(nlogn) solution based on some observations. Let Ai,j be the smallest possible tail out of all increasing subsequences of length j using elements a1,a2,a3,...,an
Observe that, for any particular i, Ai,1<Ai,2<...<Ai,jThis suggests that if we want the longest subsequence that ends with ai + 1, we only need to look for a j such that Ai,j < ai + 1 < = Ai,j + 1 and the length will be j + 1.
Notice that in this case, Ai + 1,j + 1 will be equal to ai + 1, and all Ai + 1,k will be equal to Ai,k for K !=j+1.
Furthermore, there is at most one difference between the set Ai and the set Ai + 1, which is caused by this search. Since A is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single a1,a2,...,an.

---

Solution Of the above ACM Problem

---

Algorithm:
1. First Sort dimensions for each box.
2. Then sort the individual box, corresponding sorting the position of that box.
3. Now apply the LIS[least Increasing Sequence]. In LIS, the parent box is save in parent[] array.
4. From the Maximum value of inside[] array we find last box which is include Large box sequence.
5. Then By applying Backtracing algorithm we find reverse large sequence in an arr[].
6. Reverse the array
7. Then we find the corresponding box number.
8. If we use 0 index , then print the box number adding 1 to show the output.

Code in C/C++: (1)

Detail Description of the code:
Input:
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
1 2 3 4 5 6
80 37 47 18 21 9

Step 1:
Sort each box Dimension :data[i][0…5] [i=0…7]
1 2 5 10 20 30 -->Box no -1
3 7 9 11 15 23
4 14 24 34 40 50
9 10 11 12 13 14
4 8 17 18 27 31
13 19 19 32 41 44
1 2 3 4 5 6
9 18 21 37 47 80 -->box No 8

Step 2:
Sort each box:
Position--> box sorted dimension
6-->1 2 3 4 5 6
0-->1 2 5 10 20 30
1-->3 7 9 11 15 23
4-->4 8 17 18 27 31
2-->4 14 24 34 40 50
3-->9 10 11 12 13 14
7-->9 18 21 37 47 80
5-->13 19 19 32 41 44
Position[]={6,0,1,4,2,3,7,5}

Step3:
Now LIS Algorithm:
Do Yourself…
Note: parent help us to determin when increase the value of inside [] element value….
Let you find
Inside[]= 1 1 2 3 3 2 4 4
Par[]= -1 -1 0 2 2 0 3 3

So max 4 which position 7 or 6
7-> parent of 7 is 3 -> parent of 3 is 2 -> parent of 2 is 0 -> parent of 0 is unknown -1 break
Reverse Sequence: 7->3->2->0
Sequence: 0->2->3->7
We now from position array: position[0]+1 ->position[2]+1->position[3]+1->position[7]+1
RESEULT: 7->2->5->6

Code in C/C++: (2)
Code in Java:
Thank You.