I have been thinking of an algorithm which could find the Sum Of Maximum's of all contigous sub-arrays of length k of a given Array. for each k from 1 to n , seperatly. n is the length of the array. I am able to figure out an O(N^2) solution. But could not reduce the complexity further. It would be helpful if someone could tell a sub-quadratic approach.(Possibly O(n) ). This is in reference to this problem. Any help is appreciated. NOTE : the answer for each k has to be printed seperately. Thanks :)
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | jiangly | 3578 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | tourist | 3565 |
| 8 | maroonrk | 3531 |
| 9 | Radewoosh | 3521 |
| 10 | Um_nik | 3482 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 28.04.2024 21:47:09 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by akshit.lite (previous revision, new revision, compare).
Auto comment: topic has been updated by akshit.lite (previous revision, new revision, compare).
Sorry, misunderstood the problem statement.
Can't figure out how have you reduced this to RMQ ?
Lets focus on each element of the array. For a fixed element, we wonder how many times it will be added to our total sum. Clearly, for every subarray that includes this element as the maximum, we will add it. Let our fixed element be A[x]. Then if i is the last index on the left of x such that A[i] < A[x], and j is the last index on the right of x such that A[j] < A[x], then A[x] will be added exactly (x-i+1)(j-x+1) times(you can use combinatorics to prove this). Note that if we have A[i]=A[x] or A[j]=A[x], we can count this subarray as well, but will have to subtract out some numbers at the end because we overcounted(you can use a map to store counts of each number, then do some combinatorics).
Now the only question is, how do we calculate i and j? Let's generate j first. Iterate through the array from left to right and keep track of a multiset of elements we have seen so far. When we encounter an element, let's remove all smaller elements possible from the multiset and set their j values to be this index. Then add this element to the multiset and move on. We can do a similar thing traversing the array right to left to compute the i values.
Since we iterate and use multiset for deletion, our complexity ends up being O(N log N).
We need to find the answer of k=1,k=2 .. k=n seperately. As far as I have understood you are finding sum of all the answers for each k.
If some element is being used for a subarray of size k, then it will be for sure be also used for subarray of size k-1, k-2, k-3 ... 2, 1. You could add that information through passing values backwards, kind of dp.
This problem is similar to https://www.codechef.com/FEB16/problems/MTMXSUM/, my solution using similar approach described by trashfirstsearch: https://www.codechef.com/viewsolution/9392031 (O(n) complexity since i am using a stack to find the i and j)
I solved this problem using fenwick tree. If r[n] is the result, you can figure out for each number in input array which indexes of r it affects. Each number in input array will form a pattern which can be easily processed and queried by fenwick tree.
What exactly are you storing in fenwick tree and on which parameter are you processing and querying it ? Can you please elaborate ? (facing problem since I have used only segTree most of the times)
Each number in the input array will add to some indexes of r[] in a certain way. You can see that from given example in the question or generate input of your own to see. There is nothing more to the problem than that. After that you can use any interval query/process data structure.
Won't the worst case complexity of your program be 0(n*n*log(n)) as you have to update the number of times the xth element a[x] be added into r[1] , r[2] , r[3] ... r[k] , where k is the maximum size of the segment where a[x] is maximum. ? It would'nt be a constant value for all k's of a paritcular a[x], right ?
No. What you are describing is of-course of the order O(n^2*(log(n)), But the essence of finding the pattern to be added to the result (by result i don't mean any particular r[i] but the whole result array), is that you can update array r for any a[x] in log(n) time.
Thanks for the help :)
can it can be solved in nlogn by binary search by first taking cumilative sum??
It can be solved in O(n):
http://pastebin.com/xeUpgjTe
For each i = 1, 2, ..., n we can find maximal p < i and minimal q > i such that a[p] >= a[i], a[q] > a[i] or p = 0 or q = n+1 (on left we have >= and on right > to not count twice the same interval). Then, if we fixed i we can observe that, for intervals of length 1, 2, 3, ... min(i-p, q-i)-1 we add to result a[i]*interval_length, for intervals of length min(i-p, q-i), ..., max(i-p, q-i)-1 we add min(i-p, q-i)*a[i] and for intervals of length max(i-p, q-i), ..., q-p-1 we add (q-p-interval_length)*a[i]. We want to have O(n) complexity, so in first case (when intervals have length < min(i-p, q-i)) we can add a[i] to some variable (in my code ,,sum"), and add a[i] to tab[min(i-p, q-i)], then when we will count answer for intervals of length i we will subtract tab[i] from sum and next add to result sum*i. Similar things we can do in second and third case.