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-
This is because for every inequality which 9 satisfy, 7 will also satisfy and it being closer will lead to optimal answer. So, value 9 was discarded.
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.
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 (challenges/minsubar.py at master · bilalakil/challenges · GitHub).
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.
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
Can’t this question be solved using the sliding window algorithm, i.e. maintaining left and right pointers and maintaining the sum between the two.
Consider my solution to be a variation of this.
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.
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!!!
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.
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.
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…
the final array of pairs on which binary search has to be applied ends up being:
({-5,5})(as per your approach)
this automatically diminishes the chances of getting any sub string ending with 1, 2, 3 or 4 as its ending
index while in the given test case answer should be 3. please help.
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
