CODEWITHSUNDEEP
algorithm
user2999524
user2999524

Reputation:

Building a tower from cubes

You can make stable tower from cubes by not putting bigger to a smaller one and you can't put heavier to a lighter cube.

Write a program which gives you the highest tower from N cubes.

The first row of the input txt contains the number of cubes. (1<=n<=100) In the following N rows there are the cube's length and weight.

Example:

Input.txt       Output.txt (from bottom to top)
5               3
10 3            20 5
20 5            10 3
15 6            10 2
15 1
10 2

Memory limit: 16 mb Running Time: 0.2 sec

Can you help me?

Upvotes: 4

Views: 1928

Answers (3)

neeKo
neeKo

Reputation: 4280

Algorithm

The algorithm I came up with works by using a list of ordered pairs. The pairs are first ordered by one element, then by the second.

We maintain lists of pairs, where each new pair is either:

  • added to the end of the highest list, if it can fit after the last element
  • added to the end of a new list, which is a copy of the highest segment found in one of the existing lists, to which it could be appended
  • added to a new list if it can't fit anywhere in existing lists.

Proof

  1. The first element will go in a new list, which will then be the highest.
  2. The n-th element will go to the end of the highest list (or list segment), making it the highest list with that element.
  3. The first element after n, element k, that can be appended to the list with n will be appending to the highest list that contains n, because of 2. If some higher list exists with element i to which element k could be appended, then rule 2 is applied to element i. This makes the list with k the highest list with that element.

By induction, this proves the concept of the algorithm.

Pseudocode

foreach ordered pair
    maximumIndex <- 0
    maximumList <- null
    foreach list
        highest, length <- FindLongestPath(list, pair)
        if highest > maximumHeight
            maximumHeight<- highest 
            maximumIndex <- lenght
            maximumList <- list
    if maximumIndex = 0
        lists.add(new list{pair});
    else if maximumIndex < maximumList.Length
        lists.add(new list{maximumList[0..maximumIndex - 1] + pair});
    else
        list.add{pair};

The FindLongestPath method searches the list for the first place the pair can fit in, and with it it returns the height of this segment. With a straightforward application (for from the start until place is found), I estimate the complexity of the algorithm to be O(N^2) on the worst case.

If implemented as a binary search, the complexity would be O(N log N) I guess, but for N <= 100 it doesn't really matter.

Actual Code

Since nobody likes deciphering other peoples pseudo-code, here's the actual working C# code on pastebin: http://pastebin.com/3vLn343j

The file, "Input.txt", formatted as in the question, should be in the same directory as the executable (in Visual Studio you can put it in the solution root and in properties set 'Copy to Output' to 'Copy if newer').

Upvotes: 1

xbob.ym
xbob.ym

Reputation: 521

First, let us assume there is no equal cube (cubes with identical length/weight), build one directed graph following below definition:

  1. exactly one node for each cube in graph
  2. add edge (A -> B) if cube B can be put on cube A

it's easy to know that this is an DAG (http://en.wikipedia.org/wiki/Directed_acyclic_graph)

original problem is equal to finding longest path in DAG. we can use dynamic programming for this problem.

Back to assumption, even consider equal cubes, we can make slight change to cover equal cubes. (each node have attribute - equalCount, the number of equal cubes. and update longest path definition to sum of equalCount along the path, to replace original definition: the number of node along the path)

Upvotes: 1

Sklivvz
Sklivvz

Reputation: 31143

There are different ways to approach this problem. Here's the naive way which is fairly inefficient in pseudocode:

// `Input` is a list of `Cube` who have a `Size` and `Weight` property

int largestStack(input_cubes_left, currentCube)
{
   max = 0 // at worst, there are no cubes that fit on top of currentCube
   foreach (cube in input_cubes_left)
   {
      // skip all cubes which don't fit
      if (cube.Size <= current.Size and cube.Weight <= current.Weight)
      {

        // measure the stack with currentCube, this cube, and whatever is left
        size = 1 + largestStack(input_cubes_without_cube, cube)

        // but of course we only count the ones 
        // which are bigger than our best result
        if size>max 
          max = size
      }
   }
   return max;
}

Of course, this is a simplified solution which checks all possible combinations (N factorial!). Here are some questions to get you started on optimizing it:

  • How can you leverage sorting to avoid checking a lot of invalid combinations?
  • How can you leverage Linq to solve this problem functionally?

Upvotes: 1

Related Questions