For this problem, you are given N days of upvote count data, and a fixed window

Question

For this problem, you are given N days of upvote count data, and a fixed window size K. For each window of K days, from left to right, find the number of non-decreasing subranges within the window minus the number of non-increasing subranges within the window.

A window of days is defined as contiguous range of days. Thus, there are exactly NK+1 windows where this metric needs to be computed. A non-decreasing subrange is defined as a contiguous range of indices [a,b], a<b, where each element is at least as large as the previous element. A non-increasing subrange is similarly defined, except each element is at least as large as the next. There are up to K(K1)/2 of these respective subranges within a window, so the metric is bounded by [K(K1)/2,K(K1)/2].

Constraints

1N100,000 days

1KN days

Input Format
Line 1: Two integers, N and K

Line 2: N positive integers of upvote counts, each integer less than or equal to 109.

Output Format
Line 1..: NK+1 integers, one integer for each window's result on each line

Sample Input

5 3 1 2 3 1 1

Sample Output

3 0 -2

Explanation
For the first window of [1, 2, 3], there are 3 non-decreasing subranges and 0
non-increasing, so the answer is 3. For the second window of [2, 3, 1], there is 1 non-decreasing subrange and 1 non-increasing, so the answer is 0. For the third window of [3, 1, 1], there is 1 non-decreasing subrange and 3 non-increasing, so the answer is -2.

Explanation / Answer

#!/usr/bin/env python """For this problem, you are given N days of upvote count data, and a fixed window size K. For each window of K days, from left to right, find the number of non-decreasing subranges within the window minus the number of non-increasing subranges within the window. """ (ndays, window_size) = map(int, raw_input().split()) upvotes = map(int, raw_input().split()) def diff_subranges(window): """By keeping track of the number of consecutive decreasing/increasing values and adding nconsec to the number of increasing/decreasing subranges, it's possible to loop through window only once. Returns ndec - ninc """ ninc = 0 ndec = 0 ninc_consec = 0 ndec_consec = 0 for idx, curr in enumerate(window): if idx == 0: continue prev = window[idx-1] if curr > prev: if ndec_consec == 0: ndec_consec = 1 else: ndec_consec += 1 ninc_consec = 0 ndec += ndec_consec elif curr

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---