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 gamabunta ♦♦ admin ♦♦ 
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+W1) = Wx+W(W1)/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+W1)^2 = W*x^2 + w(w1)(2w1)/6 + 2xw(w1)/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 nims11 Nice. It seems nontrivial to prove this works for W > 2, but it does. Do you have an elegant way to prove it (mine is kind of complicated)?
(13 Sep '12, 07:33)
Sumudu
What exactly needs a proof? It seems clear to me, that n distinct numbers greater than 0 have unique square sum, probably we do not need sum of nonsquare elements (just for performance maybe).
(17 Sep '12, 12:38)
betlista ♦♦
4
In general we can't recover the sequence knowing just its sum and sum of the squares. For example two different sequences (1, 5, 6) and (2, 3, 7) have equal sums: 1+5+6=2+3+7=12 and equal sums of squares: 1^2+5^2+6^2=1+25+36=62; 2^2+3^2+7^2=4+9+49=62. So the problem is to show that for the sequence (L, L+1, ..., R) it is the only sequence of different integers having the same sum and the sum of squares. In fact, this appears to be true since any other sequence of different integers with the same sum have strictly lower sum of squares.
(13 Oct '12, 22:24)
anton_adm ♦♦

A good reference: http://wcipeg.com/wiki/Sliding_range_minimum_query answered 11 Sep '12, 18:31 MarioYC 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)
betlista ♦♦

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 Sumudu Anyone There Who got accepted with nlog(w) using java.?
(12 Sep '12, 17:29)
solve
I have used Segment Tree to solve this problem.Really loved this(specially flexibility) DS.
(12 Sep '12, 17:30)
solve

Can somebody explain this approach : top most solution of bb_1 http://www.codechef.com/viewsolution/1304921 answered 19 Sep '12, 10:01 ashishnegi001 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)
mmaxio

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 bodmas 
Anyone Who got Accepted with nlog(w) using Java..? answered 13 Sep '12, 10:14 solve I used a binary search tree to store elements from i to w+i1, find_max, find_min, insert, and delete can be performed in log w time and these operation needs to be performed for (nw) times thus giving overall complexity of nlog w. Unfortunately and interestingly, there is a O(n) algorithm.
(15 Sep '12, 21:37)
sudeepdino008
I tried, but n*log(w) is too slow :( for w=40.000 it's 4*log(w)*n (4 because insert, remove, get min and get max operations) and that's more than 80 million operations you have to do in one second... Java is not the problem, I tried also in C++.
(17 Sep '12, 12:35)
betlista ♦♦

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 monish001 oh.. this is what the editorial is saying. :P
(10 Nov '12, 11:48)
monish001

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 katrinalaw 
Is there a bug in last line of the main algo: