Problem LinkSetter: Trung Nguyen Tester: Hasan Jaddouh Editorialist: Bhuvnesh Jain DifficultyEASY-MEDIUM PrerequisitesBinary Search, Prefix Sums, Divide and Conquer ProblemFind the length of the minimum subarray such that the sum of its elements is greater than $D$. ExplanationLet us first maintain a prefix sum of the array. Now the problem reduces to the following: For every index $j$, find the closest index $i$ less than $j$, such that $\text{Prefix[j]} - \text{Prefix[i]}$ ≥ $\text{d}$. The equation can also be written as $\text{Prefix[j]} - \text{d}$ ≥ $\text{Prefix[i]}$. To understand the process, let us consider an example. Let array $\text{A = } \{2, 4, 3, -2, -5, 1\}$. The prefix array would be $\{2, 6, 9, 7, 2, 3\}$. Say, we want to find the answer for index $j = 6$ i.e. we want to find the nearest $i$ such that $(3 - d)$ ≥ $prefix[i]$. We see that if index $3$ satisfies the inequality, so does all the indices with a value less than $9$ and ahead of it, i.e. indices $4$ and $5$ too. Thus, in general, we say that if for index $j$, say index $i$ satisfy the inequality, all such indices ahead of $i$ and having a value less than or equal to it will also satisfy it. Since we would like to find the closest index $i$ for every $j$ (if it exists), the previous indices having the value greater than current prefix value, although may satisfy the inequality but will never lead to an optimal answer, (meaning smallest subarray size). We thus keep an increasing temporary array, (along with indices) based on the prefix sums. Since, this array is increasing (i.e. monotonic), we can apply binary search on it to find the optimal index. Let us complete this through the example array above. The temporary index will look as follows:
To understand, more about this approach see author's or tester's solution below. Editorialist ApproachGenerally, in problems where we need to calculate some function over all subarrays and queries are not involved, divide and conquer seems a good idea assuming merging can be done efficiently. Assume, in the recursive step, we calculate the answer for the left and right halves. To understand the complete solution, we just need to understand the merging part. We compute all the prefix sums on the right-hand side and store them in a map along with the indices. Now we iterate through all the suffix sums on the left-hand side and try to find the first index on the right side which satisfy this inequality. This can be easily done by applying a "lower_bound" on the map build. The time complexity of this approach will be as follows: $T(N) = 2*T(\frac{N}{2}) + O(N*\log{N})$ meaning $T(N) = O(N * {\log}^{2}{N})$. For more details, refer to the editorialist solution. The idea is more or less similar to the author's solution (although less efficient in this case) but can be used in other problems asking us to compute some function over all subarrays. Thus I included this part in the editorial. (Though it is an overkill for the problem). Time Complexity$O(N * \log{N})$, per test case or $O(N * {\log}^{2}{N})$, per test case. Space Complexity$O(N)$ or $O(N * \log{N})$ Solution Links
This question is marked "community wiki".
asked 21 Dec '17, 14:45 
|
|
I did this sum using segment tree and coordinate compression. We calculate the prefix sum array,now lets say for a particular index i, i want to calculate the minimum valid subarray ending at i,so if there exists such subarray (such that the sum is >=d),then for 0<j<i,(pre[i]-pre[j])>=d,or pre[j]<=pre[i]-d,so indirectly we have to find the largest j that satisfy this.We can do this easily using segment tree,lets say at index i,i have a segment tree of prefix sum elements upto i,which store the maximum index.Like if pre[]={3,2,1,3} the segment[3:3]=4,segment[2:2]=2,segment[1:1]=3. so in segment tree i could simply search for range min_val to (pre[i]-d).However the max value could be 10^9. So just map all elements possible to an index by sorting them. My solution:-https://www.codechef.com/viewsolution/16653216 answered 25 Dec '17, 13:15 
|
|
I have a solution that is like the moving window methods that others have been trying to use. We have to be careful though. The moving-window algorithms on geeksforgeeks are for arrays with positive values. That is extremely important because it means that the sum of all previous values is a monotone increasing sequence. That is not the case here. To make such a method work we need to create an auxiliary sequence (the same that is used in the editorial). The trick is that the auxiliary sequence needs to be non decreasing. We can do that by removing terms. Each time we would add a term to this auxiliary list we first remove terms from the end until the last term is smaller than the new term. In that way we ensure that the sequence is always monotone increasing. Since we are deleting terms we will also need to keep track of the index of each value in this list. In total we will add N terms to this auxiliary list. This should give us both time and space complexities of O(N). I have really just eliminated the need for the bisection that was used in the editorial. answered 26 Dec '17, 07:40
|
|
Can you please elaborate on the temporary array in authors approach? I am not able to get it even after checking the author's and tester's solution solution. Like, what exactly are they doing? A pair of prefix and index of elements? Also-
What was your d, and how are you arguing about this? Why can I not apply this argument to case of "(6,2) (9,3)"? Perhaps the doubts might seem trivial to you, apologies for that, but I am geneuinely having difficulty understanding. Thanks! :) answered 25 Dec '17, 01:03 
1
@vijju123, the value of "d" doesn't matter. Let LHS = 3 - d. we want to want LHS >= something. So, if something = 9 satisfies it, so does 7. After this try to see the construction of temp array for example in the editorial. Then things would be clear.
(25 Dec '17, 01:06)
1
Oh...I was taking 9 in LHS instead of taking it in "something". Thanks. I will re-read,re-check and re-analyse tomorrow morning and get back to you :)
(25 Dec '17, 01:11)
|
|
I used SQRT decomposition. First, I calculated the prefix sums and stored the largest one for each block. Then, for each starting subarray index, I checked if there is a good ending index in the same block (pref[j]-pref[i]>=d), if not, I looped through blocks until I found one that had max_bl_pref[bl_j]-pref[i]>=d. If I found one, I had to loop through the individual elements of that block to find the best answer. answered 25 Dec '17, 19:03
|
|
can you please explain the "editorialist approach" a little more. I didn't get it. Why does we are storing prefix of right and suffix of left? answered 26 Dec '17, 09:01
|
|
I tried an algorithm where I move left and right pointers in search of the optimal solution, combining negative numbers with the numbers on the left until positive (or skipping if overall negative). I wrote the solution in Python (https://github.com/bilalakil/challenges/blob/master/codechef/cook89/minsubar.py). Unfortunately this ended up wrong, but I can't figure out why. Could anybody help provide a test case where my algorithm produces an incorrect answer so I can try to learn from my mistakes? Very much enjoyed this question though! Thanks Trung Nguyen. answered 25 Dec '17, 05:28
@bilalakil check this input : 2 5 5 1 2 3 1 -5 6 6 -1 -2 -3 3 3 -5 your output: 2 -1 correct output: 2 2
(25 Dec '17, 07:15)
@beginner_1111 Can you tell why my solution gives WA.It is giving same ans for above input Solution Link : https://www.codechef.com/viewsolution/16654650
(25 Dec '17, 08:26)
Thank you @beginner_1111 :) Much appreciated!
(28 Dec '17, 17:19)
|
|
I tried using Algorithm(geeksforgeeks) with two pointers and solve it for d>0 and for d<=0 I simply iterated over all elements and checked if any elements was>=d, but I got WA. Anyone can find test cases for which it fails or error in my solution? Solution Link answered 25 Dec '17, 12:22
|
|
@anushi , @rj25 , @jagreetdg , here is a test case: Your code gives 5, Correct output is 3 (the last 3 elements).
link
This answer is marked "community wiki".
answered 25 Dec '17, 13:05
|
|
I tried the 1st approach given in the editorial but still getting wrong answer on submission! @likecs @vijju123 @scaly_raptor I have tried all above test cases given in this thread also and getting correct... Link to my solution. Any test case giving wrong ans or fault in my approach is welcome!!! answered 25 Dec '17, 17:05 
1
Your solution gives "-1" for 1 5 4 -1 1 1 1 1 but the right answer is 4.
(26 Dec '17, 04:05)
thanks for test case
(26 Dec '17, 09:10)
|
|
I tried with 2 pointers. not sure why this gives WA. It passes all cases mentioned above. https://www.codechef.com/viewsolution/16665379 answered 26 Dec '17, 05:29
|
|
Basicslly .... the zest of the question is clear task one:->you have to maintain a prefix array. task two:->iterate over prefix array,for each item you have to find an element (>=prefix[i]-d if looking forward) or (<=prefix[i]-d if looking backward) of the item being processed (and closest also)...this can be done using expensive data structures for time optimality like segment trees , priority queues,sqrt decomposition technique,or maintaining maps etc.. task three:->find the optimal answer for more clarity refer : http://codeforces.com/blog/entry/10219 answered 26 Dec '17, 13:02 
|
|
i have a doubt in the first approach given above.. answered 26 Dec '17, 14:00
|
|
Can anyone please tell me what is "dnc" in the editorialist solution? answered 26 Dec '17, 19:53
|
|
@likecs Could you please give the intuition behind building the temporary array. How you thought of building the array in such a way? answered 26 Dec '17, 22:59
@ksmukta, in this problem we can't apply binary or ternary search on the prefix array directly as it doesn't follow the corresponding properties. One way is to do binary search with segment trees which will also pass but it is theoretically slower. Thus, we tried to see if we can deduce something about the array so that if we get an answer for some index, we could try and reduce something about other indices. These type of observations sometimes leads us to building some array (here called the temporary array) and also reduce complexity as well in some cases.
(27 Dec '17, 18:57)
|
|
you can check my code here: https://ideone.com/1cSFwO very easy map implementation answered 26 Dec '17, 23:07
|
|
ksmukta ,temporary array is nothing but a map only in which we are having record of previous prefix array ..they are sorted ..by value and also by index for closeness so as to search for "p[j]" which is <=p[i]-d answered 26 Dec '17, 23:14
|
|
My solution is giving WA. Can somebody help me figure out what is wrong in my code? Link: https://www.codechef.com/viewsolution/16689042 My prefix array is built in such a way that it will be in increasing order of both the prefix sum and indices. answered 28 Dec '17, 16:05 
|
|
Can someone please tell why I am getting WA answered 29 Dec '17, 10:58 
|
|
Anyone who codes in java can implement the solution given in editorial using TreeMap. Refer my code https://www.codechef.com/viewsolution/18603460 answered 19 May '18, 22:56
|
