Problem Statement:
478B - Strip
Solution:
This is a very interesting problem, and the official editorial for the round is already very well written :D So I'll just provide an implementation of the solution using monotonic queue (cool stuff). The DP idea is pretty simple: If f[i] is the minimum number of pieces needed to divide elements in [1..i], and g[i] is the left-most index such that [g[i]..i] is a valid piece, then f[i] is the minimum of f[j] + 1 for all \(j \in \) [g[i] .. (i-L)]. Well implementing this alone will leave us with an at least \(O(N^2)\) solution to compute each f[i], and that is already TLE. So the smart thing to do is to keep track of the maximum and minimum element between two index j and i while updating g[i] and f[i]. This can be done efficiently using monotonic queue / sliding window minimum data structure with \(O(N)\) running time, or can be achieved by simply using a multiset which will give us an \(O(N\lg{N})\) solution in the end. Here I used monotonic queue to solve the problem.
Showing posts with label Monotonic Queue. Show all posts
Showing posts with label Monotonic Queue. Show all posts
Sunday, November 23, 2014
Data Structure: Sliding Window Minimum / Monotonic Queue
Given an array of elements \( a_0, a_1, a_2, \ldots, a_n \), and queries Q(i,i+L) which means "find the minimum element in \(a_i, a_{i+1}, \ldots, a_{i+L}\) ". How can we answer such queries efficiently?
We can have an \(O(n \lg{n})\) complexity by using a minimum priority queue, RB tree, or a binary tree representation of multiset, but there in this setting we can implement a data structure called monotonic queue which only requires \(O(n)\) in construction. The implementation of this data structure requires a dequeue.
Let D be the dequeue which maintain a pair of information (i, \(a_i\)). An important property of D that we will maintain is that element in D will always be in sorted order (invariant). We will first start with an empty D, and will insert \(a_i\) and remove elements from D accordingly as we iterate from the left to the right of array \(a\) (which is from i = 0, 1, 2, ..., n).
Suppose that we are now at index \(i\) and considering to add \(a_i\). Notice that when \(a_i\) is added, all elements in (j, \(a_j\)) in D such that \(a_j\) is bigger than \(a_i\) can never be a minimum value as we go forward, hence they can be removed from D. Furthermore, if the element (i-L-1, \(a_{i-L-1}\)) is in D (which will be located at the top of D if it exists), we remove that element as well. Lastly, we append \(a_i\) at the back of D. Then we will have Q(i-L, i) = the top element in D when we reach index i. Since each element will enter and leave D only once, we have a total of \(O(N)\) operations. :D
We can have an \(O(n \lg{n})\) complexity by using a minimum priority queue, RB tree, or a binary tree representation of multiset, but there in this setting we can implement a data structure called monotonic queue which only requires \(O(n)\) in construction. The implementation of this data structure requires a dequeue.
Let D be the dequeue which maintain a pair of information (i, \(a_i\)). An important property of D that we will maintain is that element in D will always be in sorted order (invariant). We will first start with an empty D, and will insert \(a_i\) and remove elements from D accordingly as we iterate from the left to the right of array \(a\) (which is from i = 0, 1, 2, ..., n).
Suppose that we are now at index \(i\) and considering to add \(a_i\). Notice that when \(a_i\) is added, all elements in (j, \(a_j\)) in D such that \(a_j\) is bigger than \(a_i\) can never be a minimum value as we go forward, hence they can be removed from D. Furthermore, if the element (i-L-1, \(a_{i-L-1}\)) is in D (which will be located at the top of D if it exists), we remove that element as well. Lastly, we append \(a_i\) at the back of D. Then we will have Q(i-L, i) = the top element in D when we reach index i. Since each element will enter and leave D only once, we have a total of \(O(N)\) operations. :D
Subscribe to:
Posts (Atom)