### rumman_sust's blog

By rumman_sust, 5 years ago, ,

I am trying to solve this problem so many times but I can't figure out how to solve this within 2.00 second(Time limit). I really need help cause I am being frustrated about this problem.

Problem summary : Given an array find the smallest sub-array whose summation is greater or equal than X and output the length of the smallest sub-array.

1 <= Array size <= 500000, -10^9 <= A[i] <= 10^9 and -10^9 <= X <= 10^9.

Can any one give me some hints about how to solve this type of problem less than O(n^2) complexity and within 2.00 second(Time limit).

•
• +2
•

 » 5 years ago, # | ← Rev. 5 →   +6 we build the array S with S[i] = sum(A[1], A[2], .. A[i]) then we have S[i] — S[j] = sum(A[j + 1], .., A[i])then with each S[i], we find the maximum number j such as S[i] — S[j] >= x (j must be maximal so that the sequence length can be minimal)S[i] — S[j] >= x <-> S[i] — x >= S[j]here we have the left side can be calculated in O(1), the rest is to find j, O(n ^ 2) is the most simple way but it'd get TLE so u must use some data-structure like fenwick tree, segment tree, etc to do the job :p
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 "then with each S[i], we find the maximum number j such as S[i] — S[j] >= x (j must be maximal so that the sequence length can be minimal)"I guess since A[i] can be negative this step is wrong.
•  » » » 5 years ago, # ^ |   +1 You just need to find some j such that S[j] <= S[i] — X.One way of doing this is using a segment tree (where each node keeps the minimum value of the interval), initially with all nodes equal to INF, and when you are at position i: if value at root is bigger than S[i] — X, then you know that there's no segment (j + 1)..i whose sum is >= X. otherwise you go to the rightmost node where the value of the node is <= S[i] — X, and there you find j.After processing which position i, you update that position in the segment tree.If you want, you can check my solution: http://pastebin.com/95uZG0se
•  » » » » 4 years ago, # ^ |   +1 How this solution can be passed??? Try This input; 1 3 4 1 2 1output should be 3 but your code is giving -1
•  » » » » » 4 years ago, # ^ |   0 Apparently the testcases were weak and didn't test some corner cases. To correct that bug just need to add the code below checking if ans == INF :  int px = n - 1, tt = a[n]; while(px >= 1 && tt < x) tt += a[px--]; if(tt >= x) ans = min(ans, n - px); 
 » 5 years ago, # |   -23 По русски можно?
 » 5 years ago, # |   0 Thank you all for your reply. :)
 » 5 years ago, # |   +1 can anyone check what is wrong with this idea: I am getting WA. code Thanks.
•  » » 5 years ago, # ^ |   0 Check this test case.110 151 4 -1 -2 6 3 -8 14 -1 1 -1Answer should be 4 but your code shows 7.6+3+(-8)+14 = 15
•  » » » 5 years ago, # ^ |   0 Thanks, got it and it will become O(n^2) when I run for every possible dq position.
 » 5 years ago, # | ← Rev. 2 →   +6 Use a priority queue on accumulative sums. First let's build an accumulative array ACC where ACC[i] = ACC[i-1] + arr[i]. Now we want to know for each position i, what's the closest position to it's right j such that ACC[j] — ACC[i] >= X, this can be done with a priority queue.For a hint on how to implement this you can check my AC solution here http://ideone.com/ELweLn
•  » » 5 years ago, # ^ |   +1 nice, a very simple solution ^^
 » 5 years ago, # | ← Rev. 3 →   +1 Simple implementation using java TreeMap  int T = in.nextInt(); while (T-- > 0) { int n = in.nextInt(); long x = in.nextInt(); long[] sum = new long[n]; sum[0] = in.nextInt(); for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + (long) in.nextInt(); int min = n + 3; TreeMap tm = new TreeMap(); tm.put(0L, -1); for (int i = 0; i < n; i++) { long w = sum[i] - x; if (tm.floorKey(w) != null) min = Math.min(min, i - tm.get(tm.floorKey(w))); while (!tm.isEmpty() && tm.lastKey() >= sum[i]) tm.remove(tm.lastKey()); tm.put(sum[i], i); } if (min > n) out.println(-1); else out.println(min);} 
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 KNIGHT0X300, could you please explain what is the purpose of removing keys in the TreeMap greater than sum[i] as done by the above code. Ideally as 'put' method replaces previous value and floorKey returns maximum key <= sum[i], i couldn't make out the reason behind this. Other than that the code seems pretty awesome to me :)
•  » » 3 months ago, # ^ |   0 thanks man your code helped me in implementing the logichttps://discuss.codechef.com/questions/119992/minsubar-editorialbut this has a problem. when floorKey is null then we check for if sum[i] is our desired value.Consider5 91 2 3 1 2
•  » » » 9 days ago, # ^ |   0 Remember we artificially do tm.put(0L, -1); at the beginning. So this will take care of the case you are talking about. If the sum[i] is the desired value (sum[i] — x) = 0, and -1 will show up as the floorKey. Hence the answer would be current 0 based index -(-1), which is (index + 1).
 » 5 years ago, # | ← Rev. 2 →   0 Just asking couldn't it be solved by just 4 variables in O(n) time using a continuously increasing variable keeping the index of latest added element in the sum and another keeping the index of the first element in it and increasing it every time the sum of the elements between them get bigger or equal than X or negative , keeping the minimum lenght found sofar.(similar to the optimal algorithm of the Maximum sub-array problem)
 » 4 years ago, # |   0 I think we can use the segment tree approach to solve this problem in O(NlogN) time. Just iterate on each element in the array at index i (N times), and find the closest element at index j (this takes logN). Total complexity is O(NlogN)
•  » » 4 years ago, # ^ | ← Rev. 5 →   0 //C++ code got accepted on live archive #include #include #include #include #include using namespace std; #define INF 1000000000 ifstream fin("in.txt"); long long P[500000]; long long X[500000]; long long A[1000000]; void initialize(int n,int l,int h){ if(l==h){ A[n] = X[l]; return; } int mid = (l+h)/2; initialize(n*2,l,mid); initialize(n*2+1,mid+1,h); A[n] = max(A[n*2], A[n*2+1]); } int findMin(int n,int l,int h,int x,int y,long long val){ if(l==h){ if(A[n]mid) return findMin(n*2+1,mid+1,h,x,y,val); int pos = findMin(n*2,l,mid,x,mid,val); if(pos==-1) pos = findMin(n*2+1,mid+1,h,mid+1,y,val); return pos; } void process(){ int n; long long x; fin>>n>>x; for(int i=0;i>P[i]; if(i==0) X[i] = P[i]; else X[i] = X[i-1] + P[i]; } initialize(1,0,n-1); int ret = -1; for(int i=0;i pos-i+1)) ret = pos-i+1; } cout<>T; for(int i=0;i
 » 4 years ago, # | ← Rev. 2 →   -16 I believe there is a simple and intuitive solution using binary search that solves in O(N lg N) time.To answer to query "Does there exist a sub-array of length k which sums to at least X" takes O(N) time with accumulative/prefix sums.Thus, we can binary search for the smallest value of k, which will take O(lg N) time.This leads to a total complexity of O(N lg N).EDIT: Oops.
•  » » 4 years ago, # ^ |   +16 Are you sure that we can use binary search here? Because function is not monotonous. Array -1 1 -1 has subarray of size 1 with sum >=1, but none of it subarrays of size 2 or 3 have sum >=1.
•  » » 4 years ago, # ^ |   0 this is only true if the array elements are non-negative. but OP says  - 109 ≤ Ai ≤ 109 and  - 109 ≤ X ≤ 109. PS: LeBron has provided a case which breaks your idea.
•  » » 4 years ago, # ^ |   0 Correct, this is RMQ (range minimum query) issue. That's why we should use other expensive data structure like segment tree to do the query
 » 4 years ago, # |   +5 Problem is easy to solve in O(n) using modification of deque to find minimum element in it.Code
•  » » 8 months ago, # ^ |   0 same problem but your code gives wrong answer. I have solved that problem differently using segment tree.
•  » » 3 months ago, # ^ |   0 adamant, I think your solution got AC because of weak tests on UVa, because your same code got WA on the same problem on codechef MINSUBAR
 » 8 months ago, # |   0 Can someone explain why I am getting WA for this solution My approach is dropping the previous sum if it is less than or equal to 0