rumman_sust's blog

By rumman_sust, 5 years ago, In English,

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

problem link

Thanks in advance. :)

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

»
5 years ago, # |
Rev. 5   Vote: I like it +6 Vote: I do not like it

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   Vote: I like it +6 Vote: I do not like it

    "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, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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, # ^ |
          Vote: I like it +1 Vote: I do not like it

        How this solution can be passed??? Try This input; 1 3 4 1 2 1

        output should be 3 but your code is giving -1

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # |
  Vote: I like it -23 Vote: I do not like it

По русски можно?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you all for your reply. :)

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can anyone check what is wrong with this idea: I am getting WA. code Thanks.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check this test case.

    1

    10 15

    1 4 -1 -2 6 3 -8 14 -1 1 -1

    Answer should be 4 but your code shows 7.

    6+3+(-8)+14 = 15

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, got it and it will become O(n^2) when I run for every possible dq position.

»
5 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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<Long, Integer> tm = new TreeMap<Long, Integer>();
            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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks man your code helped me in implementing the logic

    https://discuss.codechef.com/questions/119992/minsubar-editorial

    but this has a problem. when floorKey is null then we check for if sum[i] is our desired value.

    Consider
    5 9
    1 2 3 1 2

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it
    //C++ code got accepted on live archive
    #include <iostream>
    #include <fstream>
    #include <math.h>
    #include <algorithm>
    #include <vector>
    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]<val)
    			return -1;
    		return l;
    	}
    	if(l==x&&h==y&&A[n]<val){
    		return -1;
    	}
    	int mid = (l+h)/2;
    	if(y<=mid)
    		return findMin(n*2,l,mid,x,y,val);
    	if(x>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<n;i++){
    		fin>>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<n;i++){
    		long long k = (i==0) ? 0 : X[i-1];
    		int pos = findMin(1,0,n-1,i,n-1,x+k);
    		if(pos!=-1 && (ret == -1 || ret > pos-i+1))
    			ret = pos-i+1;
    	}
    
    	cout<<ret<<endl;
    }
    
    int main(){
    	int T;
    	fin>>T;
    	for(int i=0;i<T;i++)
    		process();
    	return 0;
    }
    
»
4 years ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

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, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +5 Vote: I do not like it

Problem is easy to solve in O(n) using modification of deque to find minimum element in it.

Code

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same problem but your code gives wrong answer. I have solved that problem differently using segment tree.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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