ACM Contest Problem 105: Skyline

Greetings,

I just solved the Skyline problem on the online judge. I have to say, this is a very enjoyable problem after that Arbitrage problem. It is very, very straightforward and the only problem is actually getting how the output works. Once that is understood, though, things are easy

In the skyline problem, you are supposed to compute the skyline of a city, given the starts, ends and heights of buildings. The skyline is segmented into 10.000 discrete segments, which all have a certain integer height. Your input consists of triples (L, H, R). Inside such a tripel, L is the lower inclusive coordinate of the building described, R is the exclusive upper coordinate of the building described and H is the height of the building. Common sense applies, as if there are two buildings overlapping in certain segments of the skyline, you will see the higher building.

Given this, you are supposed to compute a description vector for the resulting skyline. I found the ACM-description of the output to be pretty unclear and thus, it took some time to actually see what they wanted. Basically, the output O = <o₁, o₂, o₃, o₄, …, o_2n-1, o_2n> has to be read as: (1) walk to the right until cooridinate o₁, and walk to height o₂, walk to the right until coordinate o₃, walk to height o₄, … and so on. Thus, one needs to count the amount of steps to the right one has to take until the height changes, output this amount and output the new height (and repeat this for the entire distance).

Being armed with this understandings, the implementation is straightforward. It is not even necessary to store the buildings, because in order to compute the output, we just need an array which contains the maximum heights at each coordinate of the skyline. Given this, the output can be easily computed via:

function print_result(array height of int with n elements) {
    for i = 1 ... n {
        if (height[i] != height[i-1]) {
            print(i + " " + height[i]);
        }
    }

Given this, it suffices to compute this height array, given the input triples mentioned above. This can be done initializiing the array heights with 0′s and whenever a triple (L, H, R), you compute max(H, heights[i]) for all L <= i < R.

Regards, tetha.

ACM Problem 104: Arbitrage

Greetings,

I just solved the problem Arbitrage from the Online Judge. This is quite a tricky problem, since at first, the desired output contains is quite subtle and second, it contains some floating point troubles (at least it did for me)

At first, the problem. You get a conversion table, which contains the exchange ratios from one currency to another — conversion[x][y] is pretty much how much money in currency Y you get for 1 money in currency X (hey, I am no trader, I have no clue how this would be formulated in english ). Given this, you are supposed to find an arbitrage sequence. An arbitrage sequence is a sequence of ratios so the overall product of all conversion ratios between these currencies is more than 1.01. However, the arbitrage sequence must contain less steps than overall currencies exist. However, and this is the tricky part, a shorter arbitrage sequence is better than a longer arbitrage sequence no matter what the profits are. This was my first stumbling point.

Given this, my first approach was a simple depth-first search to find these sequences, but it turned out to be too slow. Thus, I had to think further. Finally I figured that this could be solved somehow via dynamic programming, and after looking at the Floyd-Warshall-algorithms, things grew pretty clear. It is necessary to modify the Floyd-Warshall-algorithm so the algorithm preserves intermediate results (that is, paths of length less than maximum length), and also it needs to perform multiple such maximum path computations (one for each step). Once this is done, the result can be found by checking the overall results.

There are two sources which probably explain the modifications of the algorithm better than I do:
Frédéric de Mesmay’s ACM-Solver site and Gits blog

Regards, Tetha.

ACM 103: solved

Greetings,

the quest for more green problems on the ACM-Onlinejudge is going further. As I have solved problem 102 during some university course already, the next one on the list was problem 103, Stacking Boxes.

This problem is pretty much about stacking n-dimensional boxes as much as possible. A box is specified by a n-dimensional vector of sizes. A box A can be stacked into another box B if it is possible to permute the sizes of A in such a way that the permuted size vector is smaller than the size-vector of B elementwise.

Given this, the problem consists of two sub-problems one needs to solve:

• When can I stack two boxes into each other?
• How can I find the maximum amount of boxes to stack into each other?

The first problem looks a bit tricky at first, but if you think about it, it becomes pretty simple. The idea is: If you are unable to fit the smallest dimension of box A into the smallest dimension of B, then you cannot stack A into B. If this is possible, however, you need to check this for the second smallest dimension of A and B, and so on. Implementing this efficiently requires that you sort the size-vectors of A and B and check if the sorted size vector of A is less than the sorted size vector of B, element-wise. If this is the case, A can be stacked into B.

Furthermore, we have to find the maximum amount of boxes to stack into each other. It should be easy to notice this as a graph problem: Define the set of vertices as the set of boxes, and the set of edges via “A -> B” is an edge iff “A can be stacked into B”. Given this, we need to find the longest path in the resulting graph. Well, duh. Longest path is hard (NP-hard). However, consider the resulting graph further. It is directed, and it cannot contain cycles (“A can be stacked into B” is transitive, because if you can stack A into B, and if you can stack B into C, you certainly can stack A into C), so if there was a cycle, you could stash A into itself (for some A), which makes no sense. Thus, we have a DAG. Splendid, because in a DAG, the longest path problem can be solved in linear time, as one can compare on Wikipedia (I extended the longest path problem-stub into an article containing several algorithms and further explanations of the NP-hardness. The article is currently getting reassessed ).

Given all of this, the overall algorithm and implementation of this is quite simple, as all we need is some integer sorting, a topological order and a simple, known dynamic programming algorithm. The dynamic programming algorithm needs to be extended a bit in order to actually compute a longest path, not only the actual length of the longest path. I did this by adding an array predecessor, which contains NO_PREDECESSOR or the predecessor index. This array is set whenever the length of a node is updated. Given this, one can just find the vertex where the longest path ends and reconstruct the path to this vertex via the predecessors

.

Regards, tetha.

ACM problem 101: solved

Greetings,

I am back on trying to get more problems green on the Online Judge. Todays problem was problem 101, The Blocks Problem.

Overall, this problem is a neat little simulation problem, so solving it mostly requires one to understand the world to simulate and the actions to perform in this world. Once this is done, all one needs to do is to implement the world in a good way and add the actions on this and (hopefully) one is done well then.

In this case, the world is parametrized by the number of blocks, N. The world then consists of N stacks of blocks, and that is everything. The commands are a bit trickier to understand, as they are kind of convoluted. They are ‘move a onto b’ and ‘pile a over b’ and the other combinations of move, pile and over, onto with 2 integers in there. Thus, it looks like there are 4 pretty different commands to implement, does it? Well, no.If one reads the description of the commands further, “Pile vs Move” and “Over vs Onto” encodes the very same fact, just with a different parameter: If you move a block, you clean this block by removing all blocks on top of it, however, if you pile a block, you do not clean it. Similarly, if you are supposed to put something ONTO a block, you need to clean this destination block in order to execute the order correctly, but if you move OVER a certain block, you must not clean the destination block. Thus, the set of commands one really needs boils down to finding the blocks, cleaning a block and moving the blocks. This is neat

Regarding implementation, there are two possible ways to implement the stacks (at least I could immediately think of two implementations): One based on linked lists, and one based on plain old arrays. If you implement the stacks with linked lists, you basically have a datastructure ‘Block’ which consists of an index I of the block and a next-pointer to the next block. In order to move a block, you then set the next-pointer of the block below the block you move to 0 and set the pointer of the block you move on to the moved block. On the other hand, moving a stack in the array based solution requires one to copy each block one of the time.

Overall, I decided to use the array based solution, because I figured that the amount of blocks (at most 25) will be so small that the added complexity of using a linked list approach is not worth it and indeed, overall, my implementation of the problem was fast enough.