Data Structure, Double Ended Queue
Given a permutation of numbers from 1 to N, how many segments of length W exist such that
It is easy to see that a segment is valid iff
Now, we can find the largest and the smallest value in amortised O(1) time for all the N-W+1 segments and then in one parse, find the number of valid segments. The overall complexity of this algorithm is O(N).
We have to find the smallest value in all N-W+1 segments of size W. To do so, we want to build a Queue with getMax capability.
We wish to use a queue to mimic the sliding window behaviour of considering segments, one after the other. And if the queue can efficiently tell us the minimum number inside the queue at any time, we are done. Thus our queue Q should have the following methods
Let us implement Q using an internal double ended queue dQ, and an internal simple FIFO queue iQ.
Q.push is implemented as
function Q.push(item) while dQ.size && dQ.tail > item dQ.pop_back() dQ.push_back(item) iQ.push(item)
Q.pop is implemented as
function Q.pop() retVal = iQ.pop() if retVal == dQ.head then dQ.pop_front() return retVal
Q.min is implemented as
function Q.min() return dQ.head
Now, we make the following observations about Q
You can work out several examples to see that this data structure works and returns the smallest value in Q at all times.
It remains to show that this is fast enough for this problem.
We will find the smallest values for each segment and store in an array Mi, by using Q as follows
Given: A[N] Let Mi be an array of N-W+1 values for i in 1 to W, inclusive Q.push(A[i]) Mi = Q.min() for i in W+1 to N, inclusive Q.push(A[i]) Q.pop() Mi[i-W] = Q.min()
We see that Q.push is being called in a loop, and Q.push iterates over the length of dQ inside. But, if Q.push makes more than 1 comparison over dQ, it also pops items from dQ. Since each item inserted in dQ can only be popped once, there can be at most N pops through all the iterations.
That means that the sum of the number of comparisons made inside Q.push while it is being called in the loop from W+1 to N, will not be more than 2*N. The overall complexity of the algorithm to find the minimum value in each segment remains O(N).
Using the same ideas as above, you can build Ma[N], an array of the maximum values in each segment.
Following this, the result can be calculated as
result = 0 for i in 1 to N-W+1, inclusive if Ma[i] - Mi[i] + 1 == W then result = result + 1 print result
Can be found here
Can be found here
This question is marked "community wiki".
A simple approach which got me AC
An interesting segment will contain shuffled consecutive numbers. thus, their sum would be, x + (x+1) + (x+2) +...+(x+W-1) = Wx+W(W-1)/2
If an integral value of 'x' exists, we will proceed to confirm the result, as 2+3+4+5=1+3+4+6
Calculating the sum of squares of the term,
x^2 + (x+1)^2 +...+ (x+W-1)^2 = W*x^2 + w(w-1)(2w-1)/6 + 2xw(w-1)/2
Using the previously calculated value of x, we will check for equality and thus conclude if it is an interesting segment or not. the sum and sum of squares for a particular segment can be calculated in O(1) time using previous values.
answered 12 Sep '12, 23:13
A good reference: http://wcipeg.com/wiki/Sliding_range_minimum_query
answered 11 Sep '12, 18:31
A slightly different approach is to implement Q without the auxiliary queue iQ. To do this we have to store both values and indices in dQ, and modify the min operation to repeatedly throw away entries that are too far to the left (by comparing their index to the current index) before returning.
In principle we really only need to store indices in dQ since we can refer to the values in A as needed, but in practice it is easier to just make dQ a
Note also that we can add a parameter
answered 11 Sep '12, 15:37
That was the exact approach I used but didn't get AC. On first try I maintained two queues, a min queue and a max queue, then just as explained above, I subtracted the min from the max and incremented the counter if the difference was w-1. I got WA, then I changed my approach to what nims11 just described above. If an interesting segment existed in w, then the min in that segment must be (sum-w(w-1)/2)/w. So I maintained a just one min queue to check this and incremented the count once the condition is true, yet I still got WA. These were my two submissions http://www.codechef.com/viewsolution/1340617 and http://www.codechef.com/viewsolution/1336619. @admin, Can you provide an input where these program fails?
answered 13 Sep '12, 06:22
Anyone Who got Accepted with nlog(w) using Java..?
answered 13 Sep '12, 10:14
You can also use min and max instead of using sum and sum of squares. As the numbers have to be unique, if max-min+1 == W, it is only possible when all integers in range [min, max] are present.
answered 09 Nov '12, 22:42
A good reference: http://en.wikipedia.org/wiki/Maximum_transmission_unit i think it bater for you if you visit that wikipedia
answered 19 Sep '12, 11:10