All Possible Increasing Subsequences

Problem Name: All Possible Increasing Subsequences
LightOJ ID: 1085
Keywords: sorting, binary indexed tree

Continuing with my plan to write about data structures I have recently discovered, I’ll talk about a problem that can be solved with the help of a binary indexed tree. But we’ll get to that in a moment; let’s focus on the problem first.

In this problem we’re asked to consider sequences of integers. An increasing subsequence is simply an arbitrary subset of integers from the original sequence, kept in the same relative order, such that the numbers in the subsequence are in strictly ascending order. Putting it into more formal terms, let \(A\) be an array of \(N\) integers (indexed from zero to \(N-1\)). Then an increasing subsequence of length \(k\) can be described by a list of indices \(s_1, s_2, \ldots, s_k\) such that \(0 \leq s_1 < s_2 < \ldots < s_k < N\) and \(A[s_1] < A[s_2] < \ldots < A[s_k]\). Note that a subsequence can be of length one, which means that any number in \(A\) by itself forms an increasing subsequence.

The problem consists of finding the total number of increasing subsequences that can be found in a given sequence of integers. Let’s get our hands dirty with a simple example, which is always helpful to wrap our heads around problems and their solutions.

Here we have an array \(A\) of 10 elements, all distinct integers (pretty integers, by the way). At this point, you can try to find out the number of increasing subsequences in \(A\) by yourself, if you feel inclined to do so.

If you haven’t figured out a way to solve it yet, I recommend you give it a try, at least for a few minutes. It is important to spend the time doing that mental workout. Here’s a little hint, before I blurt out the strategy I have in mind: think about going step by step, in order.

Okay, here’s how the process might look like for this example. Hopefully it will help you get a grip on the core of the algorithm we’re going to use. We’ll take elements from the original sequence, one by one and in ascending order, and find out the number of increasing subsequences (ISS) we have found so far at each step:

A few steps have been left out (try to complete the list), but did you get the gist of it? Let’s put it into words:

• Let \(S\) be an array of length \(N\), where \(S[i]\) will represent the number of increasing subsequences that end at position \(i\) (so the last number of those subsequences would be \(A[i]\)). Initially, all positions inside \(S\) will be set to zero.
• Consider tuples of the form \((A[i], i)\) for all \(0 \leq i < N\). Create all these tuples and sort them by their first element.
• Take each tuple \((A[i], i)\) in order, and perform the following calculation: \(S[i] = 1 + \sum_{j=0}^{i - 1}{S[j]}\)

With this, we have successfully calculated the number of ISS that end on each position of the array. The final answer is simply the sum of all elements from \(S\).

You might be thinking, all of this is very nice except for one small detail: the array \(A\) can be very large (its size can be up to \(10^5\)), and calculating all those sums make up for a complexity of \(O(N^2)\), which is prohibitively high!

That’s where our new data structure comes out to save the day. A binary indexed tree —also called a Fenwick tree— is a data structure that can store and update cumulative sums (prefix sums) in logarithmic time, as opposed to the traditional \(O(n)\) from a naive loop to accomplish the same task in an array. The way BITs work is fascinating, in case you want to delve into it a little more, but what’s important in the context of this problem is that by using a BIT, we can calculate all those sums in our algorithm very efficiently. So our problems disappear if we simply choose to implement \(S\) as a BIT (some adjustments are necessary, though, because BITs are not zero–indexed).

There is only one additional detail we haven’t considered yet. What happens if there are repeated numbers in \(A\)? Try it with pen and paper. Create a small array with some numbers occurring more than once. Now try to apply the algorithm described here. Can you identify the exact adjustment that needs to be done? Here’s a hint: it’s related to the sorting of the tuples. They need to be sorted by their first element first, but if there’s more than one tuple with the same first element, then the comparison needs to be done by their second element. But how? I’ll leave it as an exercise… Have fun :).

Ahoy, Pirates!

Problem Name: Ahoy, Pirates!
UVa ID: 11402
Keywords: segment tree, lazy propagation

Working on algorithm problems has been one of my favourite hobbies for a while now, and I’m constantly inspired by the fact that, although there is a finite (and not too large) set of concepts that cover the landscape of all possible problems you can encounter, in practise it feels like there are no boundaries to the amount of things you can learn. In a very real sense, you can always keep learning new things, and the more you learn, the more you find new things that you want to learn next.

I still have many gaps in some basic areas, so I like diving into new things whenever I have the chance to do it. For example, it’s only recently that I have learned a little about a few data structures that were a mystery to me for a long time; segment trees, binary indexed trees, sparse tables, k-d trees… For this reason, I think the next few entries I’ll write for this blog will be for problems related to these data structures. I’ll start with the segment tree by having a crack at this problem —Ahoy, Pirates!— which I think is a very nice exercise for developing a deeper understanding of a ST and the subtleties of implementing update operations on it.

The Problem

Consider a large array of boolean values, represented as zeroes and ones. You have to implement four types of operations that can be performed over this array:

1. Set, or “turn on” a range of adjacent positions in the array (set them to 1).
2. Clear, or “turn off” a range (set to 0).
3. Flip a range (turn zeroes into ones and vice–versa).
4. Query the number of ones in a given range.

Very interesting problem, if you ask me. We’ll begin with a simple example, as usual. Let’s say we start with an array \(A\) of size 8, and with the following contents:

Querying, First Approach

Now, let’s say we receive a query that asks for the number of ones in a range \([i:j]\) with \(0 \leq i \leq j < N\), where \(N\) is the size of the array (8 in this example). One simple idea is to simply traverse the array with a loop from \(i\) to \(j\), counting the number of ones in the way.

That would be an acceptable solution if that were the only query to answer, or if the number of queries were very low. However, given that the array is big, and there’s a relatively large number of queries, a complexity of \(O(NQ)\) is too high for our needs.

What we’ll do instead is use a segment tree. This is a very nice data structure where a binary tree (typically a binary heap) is built on top of an array in order to store useful information from the underlying data in groups of increasing size. The leaves of the tree correspond to the individual positions inside the array, while internal nodes represent data that is the result of combining information from its children. The root corresponds to an interval that encloses the whole array.

Let’s try to visualise this with our example:

This graph depicts three things for each node in the tree: its interval (enclosed in a purple box), its index (in red) and its contents (in blue), which in this example corresponds to the number of ones in the corresponding interval. Note the convenient way in which the indices of all nodes are related to each other, as is common in heap–like data structures. In this case, the convention is that for a node \(i\), its two children have indices \(2i\) and \(2i + 1\). As you can see, although this data structure represents a tree, it can be stored in a plain array of size 16 (index zero is left unused).

Now, consider why building something like this is useful. If we receive a query that asks for the number of ones in the whole array, we don’t need to go any further than the root of the tree; in other words, an operation that would have taken us \(N\) steps with a common loop, takes us only a single step now. Similarly, if we’re asked about the range \([0:3]\), we just need to visit two nodes: the root and its left child.

Some queries may involve combining the answer from different paths. For example, if we have a query for the range \([2:6]\) then the following nodes of the tree would have to be visited: 1, 2, 5, 3, 6, 7 and 14. This might seem like a bad trade–off in this small example, but it is a huge gain in general. In fact, it’s easy to see that the complexity for an arbitrary query goes from \(O(N)\) to \(O(\log{N})\).

Updating the Tree

So far so good, but what would happen if we try to update the tree after it has been built? Let’s focus on just the Set operation for now.

For the reasons we have discussed before, we should avoid updating the underlying array and then re–building the whole tree; that would have an excessively high complexity. Instead, we can observe this: since every node is implicitly associated with an interval of the array, it’s easy to find out how many positions it covers, and that way we can easily determine the new contents of each affected node after a Set operation.

Back to our example. Let’s say that we receive a query that asks us to set the range \([1:7]\). This is how it could look like just after the relevant nodes have been updated:

The update process (as any operation performed on a ST) starts with the root. The tree is traversed downwards via recursive calls until a node that is completely contained in the relevant interval is found. Those nodes are then updated first (the nodes with blue background). The changes then propagate upwards, as the recursion stops and the stack is popped back until we’re back at the root again (these changes happen in the nodes with gray background).

In this example we can see how, for example, the path from the root to node 9 seems fine and needs no adjustments. Same thing with the sub-tree at node 5, but only by chance, because the contents of that node didn’t change (the range \([2:3]\) of the array already had two ones). However, notice the resulting situation for node 3. At this point, if we received a query asking for the number of ones in an interval that completely contained the range \([4:7]\), we’d have no trouble to find the answer; the information of the root and node 3 is correct. However, the sub–tree at node 3 is inconsistent. If, for instance, we received a query for the interval \([4:5]\), we’d reach node 6 and find the old value of 1 there, which is not correct.

Lazy Propagation

It has been said —by notoriously bright people— that laziness is one of the three great virtues of programmers. As it turns out, laziness is also a desirable property for algorithms. When we update the tree, we don’t want to always propagate the changes down to the leaves (which would be even worse than just updating the original array of integers in a loop). However, we don’t want to leave the tree in an inconsistent state either.

The solution is to extend the tree with an extra field that indicates whether the relevant sub–tree needs to be updated or not. This way, nodes in the tree are properly updated as needed by future queries, and not a moment before; hence the lazy name.

We will extend our tree, then. Since we have three types of operations that change the tree, we’ll store a flag that stores one of four possible values: S for a set operation, C for a clear operation, F for a flip operation, and N for nothing, meaning that the current node is up–to–date —unless one of its ancestors is not N, but that would be handled in due time. This is how our example would look like after the update, with the extended information (there’s a new state field in green):

This tree, unlike the previous one, has now enough information to maintain a consistent state at all times. Note that now nodes 10, 11, 6 and 7 are marked with S, meaning that the next time they are visited, a Set operation will be propagated (lazily) from them. We could have left nodes 10 and 11 untouched because, as has been mentioned, node 5 didn’t change, but we’ll leave them marked just to illustrate the basic process without special checks.

At this point, let’s say that we received a query asking for the number of ones in the range \([4:5]\). This time node 6 is visited, but since it’s marked S, then first we’d have to propagate the Set operation, which means updating the contents of node 6 itself, and then marking its children so the lazy propagation continues with them if necessary. This continuous propagation of previously marked nodes ensures that the information of the tree is always correct, without updating more nodes than necessary. A very powerful technique.

In order to illustrate the operations we haven’t considered yet, let’s say that we also receive a query to Clear range \([7:7]\), and a query to Flip range \([0:3]\). This is how the tree would look like after all these operations:

Okay, to summarise, this is what we’ve imagined so far in our example:

• Building the tree.
• A Query for range \([0:7]\). The result is 4 and is obtained just by looking at the root.
• Queries for ranges \([0:3]\) and \([2:6]\). They need to visit more nodes of the tree, but the result is still obtained in \(O(\log{N})\).
• A Set operation for the range \([1:7]\). It updates directly nodes 9, 5 and 3, and their ancestors, and marks their children so they are lazily updated in the future.
• A Query for range \([4:5]\). This updates node 6 (because it was marked S), and marks its children for future propagation.
• A Clear operation for range \([7:7]\).
• A Flip operation for range \([0:3]\).

The “array” (which lives now inside our ST) now has a total of four ones, yet this is not clear from looking at the leaves alone. You need to analyse the internal nodes to understand how is it that this array has been modified, and what updates have not been propagated yet.

But wait a minute, did you notice how node 14 has a one now, and its state is N? When did that happen? Then answer is, it happened in the middle of the Clear for \([7:7]\). The sequence of events was like this:

1. A Clear for \([7:7]\) was requested.
2. The tree is traversed from the root, and it goes recursively down to nodes 3 and 7. At this point it finds that node 7 is marked S.
3. It propagates this change, which means changing the contents of node 7 to 2, and marking its children (nodes 14 and 15) with S.
4. Immediately after that, it continues with its original request, but to handle it, it has to visit 7’s children first, so it goes down to nodes 14 and 15.
5. This is when the changes happen. I had not mentioned this before, but the way the tree is traversed, it needs to keep visiting nodes, until either a node is completely inside the relevant interval (like node 15 here), or it’s completely outside the interval (like node 14 here). So, node 14 is visited, and since it’s marked S, it changes its value to 1, resets its state to N and it stops traversing this branch.
6. Node 15 is updated according to the Clear request, and stops there as well.
7. All these changes propagate back upwards, resulting in the tree you see in the last figure.

I hope this overview has helped you in case you haven’t worked with segment trees before.

I want to end this by mentioning a curious detail that applies to this specific problem as a result of the operations it involves. Consider the situation of nodes 5, 10 and 11 in the last figure. Node 5 is marked F and its children are marked S. Now consider what would need to happen if, for example, you receive a query for range \([2:3]\). In other words, think about what happens if a node \(u\) with state \(s(u)\) is visited, and one of \(u\)’s children is node \(v\) with state \(s(v)\). How should state \(s(u)\) be propagated down to \(s(v)\)?

There’s a few alternatives:

• If \(s(u)\) is N, then nothing needs to happen.
• If \(s(u)\) is S or C, those operations are overriding, meaning that the state of \(v\) must be set to \(s(u)\) regardless of the previous contents of \(s(v)\).
• However, if \(s(u)\) is F, then the previous contents of \(s(v)\) are important, and they need to change accordingly:
  • If \(s(v)\) was N, it becomes F.
  • C becomes S.
  • S becomes C.
  • F becomes N.

Kinda cool, isn’t it?

Sample Code

I usually don’t include source code in my posts because I prefer describing the general algorithms, but in this case I’ll attach the basics of my segment tree code for this problem, because I know that finding reference code for this data structure on the web can be a little difficult.

This code con be simplified much further by combining similar code from different methods, but this way you can see how every individual operation is implemented separately, and it also makes it easy to identify the common patterns of manipulating the segment tree.

#define MAXN 1024000
#define MAXH 21  // 1 + ceil(log2(MAXN))

// Flags to identify states. 0 is for "Nothing".
#define UP_SET 1
#define UP_CLR 2
#define UP_FLP 3

struct SegTree {
    vector<int> A;  // original array of integers
    vector<int> T;  // segment tree
    vector<int> U;  // segment tree for lazy propagation (the states)

    int n;  // size of the array

    SegTree(int N=0) : n(N) {
        A.resize(MAXN);
        T.resize(1 << MAXH);
        U.resize(1 << MAXH);
    }

    void init() { tree_init(1, 0, n-1); }
    void tree_init(int x, int a, int b) {
        U[x] = 0;
        if (a == b) { T[x] = A[a]; return; }
        int lt = 2*x, rt = lt + 1, md = (a+b)/2;
        tree_init(lt, a, md);
        tree_init(rt, md + 1, b);
        T[x] = T[lt] + T[rt];
    }

    void set(int i, int j) { tree_set(i, j, 1, 0, n - 1); }
    void tree_set(int i, int j, int x, int a, int b) {
        propagate(x, a, b);
        if (j < a || i > b) return;
        if (a == b) { T[x] = 1; return; }
        int lt = 2*x, rt = lt + 1, md = (a+b)/2;
        if (a >= i && b <= j) {
            T[x] = b - a + 1;
            U[lt] = U[rt] = UP_SET;
            return;
        }
        tree_set(i, j, lt, a, md);
        tree_set(i, j, rt, md + 1, b);
        T[x] = T[lt] + T[rt];
    }

    void clear(int i, int j) { tree_clear(i, j, 1, 0, n - 1); }
    void tree_clear(int i, int j, int x, int a, int b) {
        propagate(x, a, b);
        if (j < a || i > b) return;
        if (a == b) { T[x] = 0; U[x] = 0; return; }
        int lt = 2*x, rt = lt + 1, md = (a+b)/2;
        if (a >= i && b <= j) {
            T[x] = 0;
            U[lt] = U[rt] = UP_CLR;
            return;
        }
        tree_clear(i, j, lt, a, md);
        tree_clear(i, j, rt, md + 1, b);
        T[x] = T[lt] + T[rt];
    }

    void flip(int i, int j) { tree_flip(i, j, 1, 0, n - 1); }
    void tree_flip(int i, int j, int x, int a, int b) {
        propagate(x, a, b);
        if (j < a || i > b) return;
        if (a == b) {
            T[x] = T[x] == 1 ? 0 : 1;
            return;
        }
        int lt = 2*x, rt = lt + 1, md = (a+b)/2;
        if (a >= i && b <= j) {
            T[x] = (b - a + 1) - T[x];
            U[lt] = apply_flip(U[lt]);
            U[rt] = apply_flip(U[rt]);
            return;
        }
        tree_flip(i, j, lt, a, md);
        tree_flip(i, j, rt, md + 1, b);
        T[x] = T[lt] + T[rt];
    }

    int query(int i, int j) { return tree_query(i, j, 1, 0, n-1); }
    int tree_query(int i, int j, int x, int a, int b) {
        if (j < a || i > b) return -1;
        propagate(x, a, b);
        if (a >= i && b <= j) return T[x];
        int lt = 2*x, rt = lt + 1, md = (a+b)/2;
        int q1 = tree_query(i, j, lt, a, md);
        int q2 = tree_query(i, j, rt, md + 1, b);
        if (q1 < 0) return q2;
        if (q2 < 0) return q1;
        return q1 + q2;
    }

    int apply_flip(int v) {
        if (v == UP_SET) return UP_CLR;
        if (v == UP_CLR) return UP_SET;
        if (v == UP_FLP) return 0;
        return UP_FLP;
    }
    void propagate(int x, int a, int b) {
        if (U[x] == 0) return;
        if (U[x] == UP_SET)
            T[x] = b - a + 1;
        else if (U[x] == UP_CLR)
            T[x] = 0;
        else if (U[x] == UP_FLP)
            T[x] = (b - a + 1) - T[x];

        if (a != b) {
            int lt = 2*x, rt = lt + 1;
            if (U[x] == UP_SET || U[x] == UP_CLR)
                U[lt] = U[rt] = U[x];
            else
                U[lt] = apply_flip(U[lt]), U[rt] = apply_flip(U[rt]);
        }
        U[x] = 0;
    }
};

Highest Paid Toll

Problem Name: Highest Paid Toll
UVa ID: 12047
LightOJ ID: 1379 (under the name “Toll Management”)
Keywords: graph theory, single source shortest path, dijkstra

Let me share with you a little story from my childhood. When I was a kid, one of the first books I really enjoyed —and one which remains a cherished piece in my bookshelf to this day— was a mathematics book they made me read in elementary school. It wasn’t your average elementary math book, however. It was written by a professor from a local University, and the book had a very friendly and humorous approach to the concepts it presented (without being patronising), and at the same time it was rich in content and rigorous. It also contained a good deal of material not directly related to mathematics, like philosophy, literature, humanities, puzzles… well, you get the idea. In short, to a small curious kid with a yearning for understanding more about this world, this book was (and still is) simply fantastic. Anyway, one of the lessons I learned from it comes at the beginning of the section devoted to puzzles, where some general ideas for problem–solving are discussed. That chapter contains a list of tips to approach a new problem, and among them is the question “Can you make a drawing?”, and then in a smaller font (the “informal” voice inside the book) there was the complementary statement: “you can always make a drawing, do it!”

The point of this long–winded introduction is simply this: you can indeed always do a drawing… give it a try. This is not a novel idea by any means, of course, it’s just one that was strongly impressed upon my memory from those days, and which I apply constantly ever since. Granted, most of the time I try to do the “drawing” in my mind, whenever I’m able to fit the entire problem in my head, but if I can’t do that I quickly resort to a pen and a sheet of paper and start doodling around. This problem is just an exceptionally good example of an instance where something that was initially confusing, all of a sudden revealed its simplicity and elegance once I just started drawing things. This will all become clear in a moment —at least I hope so, if not, try doing a drawing about this post, a meta–drawing if you will :).

Here’s the summary of the problem. You receive a directed, weighted graph. Two nodes are defined as source (\(s\)) and sink (\(t\)), and you also receive a number \(p\) which denotes a “cost limit”. You have to find the heaviest edge inside any valid path between the source and the sink; a path is valid if its total cost doesn’t exceed \(p\).

Clearly, this is not your standard single–source shortest path problem. However, there is a nice solution based on the SSSP algorithm. As usual, let’s begin with an arbitrary example that helps us tame this puzzle. Consider the following graph:

Try to find the answer for this example. That is, identify all paths from 1 to 9 with a total cost less than or equal to 100, and among those paths, determine the edge with the largest cost. Given that the answer becomes obvious from the following graphs, I might as well tell you now that it is the edge \(2 \rightarrow 4\) with a cost of 53.

What I will ask you now is, forget about this specific example. Generalise things in your mind. The next graph presented below will look familiar, but keep in mind that this is just a simplified representation of the general problem. You can be fairly certain that the real test cases for this problem from the judge will contain all kinds of complicated graphs, with many more nodes, edges, multiple edges between the same pair of nodes, unconnected components, etc. But this representation is just an aid that helps us wrap our minds around the core of this problem.

That being said, imagine now an arbitrary graph for which there is a valid answer. That means that there is one edge that belongs to a valid path from the source to the sink, and that edge has the highest cost possible among all the alternatives. Let’s paint that edge with a distinctive color, like red. That graph might look something like this:

Okay, now… if this edge, let’s call it \(u \rightarrow v\), really exists and is a valid answer, then it implies a number of things:

• There has to be a path \(s \Rightarrow u\).
• Similarly, there exists a path \(v \Rightarrow t\).
• Perhaps the most significant implication of all, the sum of the costs of \(s \Rightarrow u\), \(u \rightarrow v\) and \(v \Rightarrow t\) has to be less than or equal to \(p\).

Let’s put all this information in a new graph that depicts the relevant nodes and paths:

When you think about the green paths, does anything come to mind? For me this was the moment when something “clicked” in my head. I started having no idea how to solve the problem, but when I drew something like this the strategy made itself evident; but let’s keep going.

I hope you can see where this is going. If there is an edge \(u \rightarrow v\) that is our answer, then it would be useful to know the shortest possible paths \(s \Rightarrow u\) and \(v \Rightarrow t\), wouldn’t you agree?

With this in mind, let’s formulate the following algorithm to solve the general problem:

• Start with two graphs: the original graph (let’s call it \(G\)) and a reverse graph (let’s call it \(R\)).
• Find all shortest paths in \(G\) from \(s\).
• Find all shortest paths in \(R\) from \(t\).
• Let \(A\) be the answer. Initially, \(A = -1\).
• For each edge \(u \rightarrow v\) in \(G\) with cost \(w\):
  • Determine the total cost \(C\) of \(w\) plus the shortest paths \(s \Rightarrow u\) in \(G\) and \(t \Rightarrow v\) in \(R\).
  • If \(C \leq p\) and \(w > A\), then set \(A = w\).

That’s it. Running an algorithm like Dijkstra’s two times and then traversing over all the edges is quite enough to reach the solution.

Needless to say, the best part for me was having an Eureka moment right after doing one of my primitive drawings in a piece of paper. This is what intrigues me, though: the drawing I did was not particularly “interesting”; it was just a rather generic graph. Yet somehow, seeing the nodes and edges drawn in a piece of paper, and assigning colors to some edges made all the difference. It’s like it made all the processes inside my brain go faster… Maybe you understand what I’m talking about. If you don’t, can I suggest that you try doing more drawings in the future? Even if they are so trivial that it might seem silly to spend the time drawing something so elementary. The results might surprise you.