Algorithms homework

Question

My alg. teacher assigned 3 problems to my class, but i can't find a solution for the last problem (Algo Run). You are playing Temple Run (but without monkeys following you), on the ground there are $n$ sequences of coins: $S_i$. Each sequence has:

• $s_i$: int, start moment
• $t_i$: int, end moment
• $v_k$: int, value of each coin in the sequence
• $k_i$: int, lane where the sequence belongs

For example, it can't be that a sequence of 5 elements has coins of different value. It's also impossible that coins in a sequence are on different lanes.

The given input is:

• $S$: list of sequences $(s_i, t_i, v_i, k_i)$
• $n$: int, number of sequences
• $k$ int, number of lanes

The goal is to find the max score possible for that istance, the algorithm must have time complexity $O(n \cdot logn)$.

Note that:

• You can jump to any lane you want.
• eache sequence fills a continuos interval between $s_i$ and $t_i$, and $t_i \geq s_i$.
• Two sequences on the same lane, never overlap

An example is provided here: enter image description here

The max score in this example is 42ドル$.

Edit: please, i need an algorithm that does not use DP. It's a topic that has not been discussed in my course until now.

• D.W.: cs.stackexchange.com/tags/dynamic-programming/info
• greybeard: What techniques, what data structures have you been introduced to recently? I think non-DP solutions apply, too.
• ExuberantGuitarist: * Recursion * Sorting, in particular Heap Sorting * Linked data structures and indexed data structures for trees * DFS algorithms * Dictionary, Research binary trees, AVL trees. DP is an argument that will be discussed next semester.
• greybeard: Consider how you yourself would complete the example. As depicted, of course. Which lane do you start with? When do you switch lanes?
• ExuberantGuitarist: I was thinking about using a binary tree. Each node $v_i$ holds a linked list where each entry is a sequence of coins. The whole linked list describes the path that maximizes the coins possible for the sub-tree with root $v_i$. Every leaf holds just a corresponding sequence $S_i,ドル then recursively i join the solutions. I think it's a "cool" solution but it's really hard to code, and i don't think it's complexity would be $O(n log n)$ .

Answer 1

The full solution is based on sorting. Let consider two types of events: "sequence begins" and "sequence ends". Only at this points it is reasonable to change the lane. At all other points nothing changes comparing to the previous moment, so there is no reason to change the lane. So let's sort all such events. Now for each point we need to choose the lane with maximum coin value, multiply this value by time difference between next and this points and add this multiplication to the result. (For the last event that is definitely "sequence end" we don't need to add anything.)

A simple way to describe how to determine the lane with maximum coin value is using multiset. At the beginning of sequence you add coin value to the set, at the end of sequence remove it. The maximum value in the set corresponds to the best coin you can take. If set is empty then no coin could be collected (i. e., coin value is 0ドル$). In case when value of coin may be negative there is one more option to consider: if maximum value is negative, but cardinality of the set is less than $k$, you may avoid all coins (i. e., coin value is 0ドル$). Since there are $n$ insertions, $n$ deletions and 2ドルn$ lookups, cardinality of set is at most $n$ and the total time is $\mathrm O(n \log n)$.

However using heap instead of set is better in two ways. Firstly you definitely know heap already and may be still don't know set. Secondly heap is much faster than set in sense of underlying multiplication constant. You need insert, delete and maximum. Insert and maximum are native operations for heap. But delete is native for maximum only. There are two ways to deal with deletion of an arbitrary element.

• The first method is lazy. Make an array of sequences. Now link each element of heap to an element of this array. So every element of heap contains an additional information that is index in array. For each sequence you know whether it ended or not. For maximum element of heap you know whether its sequence ended or not. If it ended then remove maximum. And repeat as many times as needed. When corresponding sequence of maximum is not finished then this is actual maximum. If heap becomes empty then there are no coins. For the case of negative value coins you may add a counter of non-empty lanes. Increase it at every begin of sequence and decrease at every end of sequence. (Don't forget to initialize with zero!) If maximum is negative and this counter is less then $k$ take 0ドル$ as current coin value. Note that processing an event now takes amortized $\mathrm O(\log n)$, not guaranteed, because maximum may be deleted many times between two events. However it doesn't change the total time of $\mathrm O(n \log n)$, because every sequence brings to the heap one insert and one delete only.

• The second method is instant. Like in the first option make array of sequences and link every element of heap to this array. But let also every element of array contain an additional information that is index of corresponding element in heap (or invalid value if such element doesn't exist). And now every bubble-up in heap updates this additional information in the array too. Then you can delete arbitrary element from heap using bubble-down, swap with the last element, pop back and bubble-up for the previously last element.