103 Stacking Boxes

>> শনিবার, ২১ নভেম্বর, ২০০৯


                                   Longest Increasing Subsequence
According to Arefin book
Input: Given a sequence
Output: The longest subsequence of the given sequence such that all values in this
longest  subsequence is strictly increasing/decreasing.
O(N^2) DP solution for LIS problem (this code check for increasing values):

for i = 1 to total-1
  for j = i+1 to total
    if height[j] > height[i] then
      if length[i] + 1 > length[j] then
        length[j] = length[i] + 1
        predecessor[j] = i

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


After first loop of j: 
  length: [1,2,2,2,2], because 6,2,3,5 are all > 1
  predecessor: [nil,1,1,1,1]
After second loop of j: (No change)
  length: [1,2,2,2,2], because 2,3,5 are all < 6
  predecessor: [nil,1,1,1,1]
After third loop:
  length: [1,2,2,3,3], because 3,5 are all > 2
  predecessor: [nil,1,1,3,3]
  After fourth loop:
  length: [1,2,2,3,4], because 5 > 3
  predecessor: [nil,1,1,3,4]


DOWNLOAD Code :

Download to click
 
Algorithm:


function lis_length( a )
    n := a.length
    q := new Array(n)
    for k from 1 to n:
        max := 0;
        for j from 1 to k-1, if a[k] > a[j]:
            if q[j] > max, then set max = q[j].
        q[k] := max + 1;
    max := 0
    for i from 1 to n:
        if q[i] > max, then set max = q[i].
    return max;

DOWNLOAD C CODE:
DOWNLOAD CPP CODE :
Download to click


103 Stacking Boxes

Background

Some concepts in Mathematics and Computer Science are simple in one or two dimensions but become more complex when extended to arbitrary dimensions. Consider solving differential equations in several dimensions and analyzing the topology of an n-dimensional hypercube. The former is much more complicated than its one dimensional relative while the latter bears a remarkable resemblance to its ``lower-class'' cousin.

The Problem

Consider an n-dimensional ``box'' given by its dimensions. In two dimensions the box (2,3) might represent a box with length 2 units and width 3 units. In three dimensions the box (4,8,9) can represent a box tex2html_wrap_inline40 (length, width, and height). In 6 dimensions it is, perhaps, unclear what the box (4,5,6,7,8,9) represents; but we can analyze properties of the box such as the sum of its dimensions.
In this problem you will analyze a property of a group of n-dimensional boxes. You are to determine the longest nesting string of boxes, that is a sequence of boxes tex2html_wrap_inline44 such that each box tex2html_wrap_inline46 nests in box tex2html_wrap_inline48 ( tex2html_wrap_inline50 .
A box D = ( tex2html_wrap_inline52 ) nests in a box E = ( tex2html_wrap_inline54 ) if there is some rearrangement of the tex2html_wrap_inline56 such that when rearranged each dimension is less than the corresponding dimension in box E. This loosely corresponds to turning box D to see if it will fit in box E. However, since any rearrangement suffices, box D can be contorted, not just turned (see examples below).
For example, the box D = (2,6) nests in the box E = (7,3) since D can be rearranged as (6,2) so that each dimension is less than the corresponding dimension in E. The box D = (9,5,7,3) does NOT nest in the box E = (2,10,6,8) since no rearrangement of D results in a box that satisfies the nesting property, but F = (9,5,7,1) does nest in box E since F can be rearranged as (1,9,5,7) which nests in E.
Formally, we define nesting as follows: box D = ( tex2html_wrap_inline52 ) nests in box E = ( tex2html_wrap_inline54 ) if there is a permutation tex2html_wrap_inline62 of tex2html_wrap_inline64 such that ( tex2html_wrap_inline66 ) ``fits'' in ( tex2html_wrap_inline54 ) i.e., if tex2html_wrap_inline70 for all tex2html_wrap_inline72 .

The Input

The input consists of a series of box sequences. Each box sequence begins with a line consisting of the the number of boxes k in the sequence followed by the dimensionality of the boxes, n (on the same line.)
This line is followed by k lines, one line per box with the n measurements of each box on one line separated by one or more spaces. The tex2html_wrap_inline82 line in the sequence ( tex2html_wrap_inline84 ) gives the measurements for the tex2html_wrap_inline82 box.
There may be several box sequences in the input file. Your program should process all of them and determine, for each sequence, which of the k boxes determine the longest nesting string and the length of that nesting string (the number of boxes in the string).
In this problem the maximum dimensionality is 10 and the minimum dimensionality is 1. The maximum number of boxes in a sequence is 30.

The Output

For each box sequence in the input file, output the length of the longest nesting string on one line followed on the next line by a list of the boxes that comprise this string in order. The ``smallest'' or ``innermost'' box of the nesting string should be listed first, the next box (if there is one) should be listed second, etc.
The boxes should be numbered according to the order in which they appeared in the input file (first box is box 1, etc.).
If there is more than one longest nesting string then any one of them can be output.

Sample Input


5 2

3 7

8 10

5 2

9 11

21 18

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

10 2

1 1

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

1 10

6 1

6

8

10

4

5

4

30 10

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

200 201 202 203 204 205 206 207 208 209 

100 101 102 103 104 105 106 107 108 109 

300 301 302 303 304 305 306 307 308 309 

200 201 202 203 204 205 206 207 208 209 

100 101 102 103 104 105 106 107 108 109 

300 301 302 303 304 305 306 307 308 309 

400 401 402 403 404 405 406 407 408 409 

500 501 502 503 504 505 506 507 508 509 

411 412 413 414 415 416 417 418 419 420 

521 522 523 524 525 526 527 528 529 530

50 60 70 80 90 50 60 70 80 90

20 30 40 50 60 70 80 90 10 99

10 9 8 7 6 5 4 3 2 1

19 29 39 49 59 69 79 89 95 9

15 35 25 45 65 55 85 75 93 5

50 60 70 80 90 50 60 70 80 90

20 30 40 50 60 70 80 90 10 99

10 9 8 7 6 5 4 3 2 1

19 29 39 49 59 69 79 89 95 9

15 35 25 45 65 55 85 75 93 5

Sample Output


5

3 1 2 4 5 

4

7 2 5 6 

1

1 

5

4 5 1 2 3 

13

1 2 3 4 5 21 12 11 13 17 19 18 20 


Discussion: Algorithm described by rizoan toufiq
  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.
To read it, You will be in trouble…..
So try yourself.
Or download the code in Cpp & java both



More details: described by rizoan Toufiq

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


Any Way: Is It easy?  I don’t know
Rizoan toufiq        

DOWNLOAD NETCODE :RUN TIME: 0.012 sec
Download to click

DOWNLOAD MY CODE : run time: .008
Download to click

DOWNLOAD Java CODE:
Download to click



একটি মন্তব্য পোস্ট করুন

  © Rizoan Toufiq , Copy Right @ 2009

Back to TOP