ladpro98's blog

By ladpro98, 11 years ago, In English

Here is the problem statement:

Given an array A[1..n]. Find the sub-array that it's sum is smallest and at least M. (all numbers in the input is 32bit integer)

Till now I cannot find a good solution. Can anyone help me with an O(n) or O(NlogN) algorithm?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Umm... pre-compute the partial sums in O(N) and bin-search in per query?

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you give me more details. I try to sort the SUM array but then I am unable to Bin-Search since the positions has changed.

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

      What? Why would you sort? That'd obviously completely mess up the results. Also, what are "positions"?

      Compute prefix sums (or partial sums as you call it): S[i] = S[i - 1] + A[i], S[0] = 0.

      Ok, I just realized that A[i] can be negative, so bin-search won't work (it requires the sums to be increasing/decreasing). But you can still try all S[i] and pick the one that fits your condition. There are just O(N) of them, so the time complexity is O(N).

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        So, for each i, we use an inner for loop to find the best S[j] such thạt S[j]+M <= S[i] (here partial sum means the sum of elements a[j..i]) I think the complexity is O(N^2)

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

          No, for each i, we use one line of code to check if S[i] ≥ M. The complexity is O(N).

          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            I think you have misunderstood my question, there are O(N^2) sums. I am not asking for prefix sums, but sums of consecutive elements. Sum[i..j] = PrefixSum[j] — PrefixSum[i-1]

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

              you mean PrefixSum[j]-PrefixSum[i-1]

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

                Thank you, my mistake, fixed

            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              In the OP, you were asking for partial sums. I suggest you read something about them, for example on Wikipedia

              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Thanks, I got it. Sorry for bad English. (I have already edited my post) Hope you can help me with my homework.

            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              I think you should store PrefixSums in a map and then look for smallest value in map which is at least PrefixSum[i]-M, but i dont know the complexity of this

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

                I have no idea about Map data structure. The problem is just a weekly homework and I think it can be solved using pure C (raw arrays).

            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              You should have a set which stores prefixSum[0], ..., prefixSum[i-1] at every iteration. Then use something like set.floor(prefixSums[i] — M). It will find the best candidate if the right index is i.

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

                I have just read basic information about Set. Thanks for your idea, it will work. But because I use PASCAL (not C++), implementing Set is such a challenging task.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                  Rev. 3   Vote: I like it +1 Vote: I do not like it

                  I know a solution with Fenwick tree and binary searches, it's Nlog^2N but it's very fast Nlog^2N.

                  You know what elements will be in the set in the end, so you can give them the indices in the increasing order (e.g by sorting pairs (prefixSums[i], i)):

                  Then you should have a Fenwick tree: tree[i] = 1 if the prefix sum with index i is in the set, otherwise it is 0.

                  How to add number in the set? Find its index (by binary search in sorted pairs (prefixSums[i], i)). Set tree[i] = 1.

                  How to process floor(x) operation? Find the index of the largest element in the sorted pairs array which is less or equal than x, let it be i. Then use another binary search, in the Fenwick tree, to find the smallest element j such that sum(0..j) == sum(0..i).

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

                  Your idea seems promising. I hope we can have a private chat to figure out some details. I can only use Fenwick tree with getSum or getMax operations, it will be cool if i can use Fenwick tree for getFloor method.