PROBLEM LINK:DIFFICULTYEASY PREREQUISITESData Structure, Double Ended Queue PROBLEMGiven a permutation of numbers from 1 to N, how many segments of length W exist such that
QUICK EXPLANATIONIt 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 NW+1 segments and then in one parse, find the number of valid segments. The overall complexity of this algorithm is O(N). EXPLANATIONWe have to find the smallest value in all NW+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. About dQ
About 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 NW+1 values for i in 1 to W, inclusive Q.push(A[i]) Mi[1] = Q.min() for i in W+1 to N, inclusive Q.push(A[i]) Q.pop() Mi[iW] = 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 NW+1, inclusive if Ma[i]  Mi[i] + 1 == W then result = result + 1 print result SETTERS SOLUTIONCan be found here TESTERS SOLUTIONCan be found here
This question is marked "community wiki".
asked 11 Sep '12, 15:21

A good reference: http://wcipeg.com/wiki/Sliding_range_minimum_query answered 11 Sep '12, 18:31
1
There is written in the material that
any idea how to order [a,b] couples to perform one O(n) seatch or I have to do x searches for different (ba) values?
(17 Sep '12, 12:41)

Can somebody explain this approach : top most solution of bb_1 http://www.codechef.com/viewsolution/1304921 answered 19 Sep '12, 10:01
It works as follows: for each segment of numbers a[i], a[i + 1], ..., a[i + w  1] we calculate the number of pairs (x, x + 1) such that they both are present in this segment. Then, our segment is valid iff this number is w  1.
(09 Oct '12, 18:01)

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 w1. 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 (sumw(w1)/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

You can also use min and max instead of using sum and sum of squares. As the numbers have to be unique, if maxmin+1 == W, it is only possible when all integers in range [min, max] are present. answered 09 Nov '12, 22:42

I am using an (n+w)logn algorithm still it is showing time limit exceeded. please help. Thanks in advance answered 26 Sep, 09:33

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

Is there a bug in last line of the main algo: