CHEFTOWN - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Data Structure, Double Ended Queue

PROBLEM

Given a permutation of numbers from 1 to N, how many segments of length W exist such that

  • Suppose the segment S of length W starts from L and ends at R, where R-L+1 = W
  • We sort the items in S in increasing order
  • Now, S should satisfy S[i] = S[i-1]+1, for i between 2 and K, inclusive (assuming S was 1-based)

QUICK EXPLANATION

It is easy to see that a segment is valid iff
The largest value in the segment - the smallest value in the segment + 1 = W.

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).

EXPLANATION

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

  • push: push an item in the queue
  • pop: pop an item from the queue in FIFO order
  • min: return the minimum value in the queue at this point

Let us implement Q using an internal double ended queue dQ, and an internal simple FIFO queue iQ.

About dQ

  • dQ.size is the number of elements in dQ
  • dQ.head is the first element in dQ
  • dQ.tail is the last element in dQ
  • dQ.push_front pushes the element at the head and changes head to this value
  • dQ.pop_front pops the element at the head and shifts the head forward
  • dQ.push_back pushes the element at the tail and changes the tail to this value
  • dQ.pop_back pops the element at the tail and shifts the tail behind

About iQ

  • iQ.size is the number of elements in iQ
  • iQ.push pushes an element in iQ
  • iQ.pop pops an element from iQ in FIFO order

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

  • iQ has all the elements inside Q
  • dQ has a subset of elements, in Q, in increasing order
    • dQ.head has the smallest element in Q
    • followed by the next smallest element which was inserted after inserting the smallest element
    • so on, till dQ.tail, which has the last element inserted in Q
  • If the current item to pop is the smallest item in Q, then we do a iQ.pop() as well as dQ.pop_front(). This ensures that we have the smallest value after the pop operation
  • If the last item (or last few items) which was inserted are larger than the current item, then their values are not relevant towards finding the minimum value, since
    • They will be popped before popping the currently inserted item (FIFO order)
    • They cannot be the smallest value since the current item’s value is smaller

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[1] = 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

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

7 Likes
2

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. Q.push is the same except we get rid of the line referring to iQ. The overall algorithm is also the same except we don’t call Q.pop (so we don’t define that; this Q only supports push and min).

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 deque of pair<int, int> (in C++).

Note also that we can add a parameter w to min to indicate the window size (in this problem it is the same throughout so we don’t bother), and this structure will work as long as i-w_i >= j-w_j for i >= j (i.e. the left edge of the window never moves backwards)

4 Likes
3

A good reference: http://wcipeg.com/wiki/Sliding_range_minimum_query

7 Likes
4

Anyone There Who got accepted with nlog(w) using java.?

5

I have used Segment Tree to solve this problem.Really loved this(specially flexibility) DS.

6

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.

15 Likes
7

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?

8

Nice. It seems non-trivial to prove this works for W > 2, but it does. Do you have an elegant way to prove it (mine is kind of complicated)?

9

Anyone Who got Accepted with nlog(w) using Java…?

10

I used a binary search tree to store elements from i to w+i-1, find_max, find_min, insert, and delete can be performed in log w time and these operation needs to be performed for (n-w) times thus giving overall complexity of nlog w. Unfortunately and interestingly, there is a O(n) algorithm.

11

I tried, but n*log(w) is too slow :frowning: 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++.

12

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 non-square elements (just for performance maybe).

13

There is written in the material that

…a’s are increasing and the b’s are also increasing (in both cases, not necessarily strictly)

any idea how to order [a,b] couples to perform one O(n) seatch or I have to do x searches for different (b-a) values?

1 Like
14

Can somebody explain this approach :
top most solution of bb_1
http://www.codechef.com/viewsolution/1304921

1 Like
15

A good reference: http://en.wikipedia.org/wiki/Maximum_transmission_unit i think it bater for you if you visit that wikipedia

16

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.

17

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.

4 Likes
18

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.

19

oh… this is what the editorial is saying. :stuck_out_tongue:

20

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

for i in W+1 to N, inclusive
    Q.push(A[i])
    Q.pop()
    Mi[i-W<b>+1</b>] = Q.min()