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?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Umm... pre-compute the partial sums in O(N) and bin-search in
per query?
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.
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).
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)
No, for each i, we use one line of code to check if S[i] ≥ M. The complexity is O(N).
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]
you mean PrefixSum[j]-PrefixSum[i-1]
Thank you, my mistake, fixed
In the OP, you were asking for partial sums. I suggest you read something about them, for example on Wikipedia
Thanks, I got it. Sorry for bad English. (I have already edited my post) Hope you can help me with my homework.
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
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).
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.
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.
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).
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.