Your text to link here... My dp solution is O(n^2) but here n=50000 and time is 1 sec. Is there any mathematical formula which reduces time within 1 sec. Any hints...Thanks
Your text to link here... My dp solution is O(n^2) but here n=50000 and time is 1 sec. Is there any mathematical formula which reduces time within 1 sec. Any hints...Thanks
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 162 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | pajenegod | 145 |
9 | SecondThread | 145 |
Name |
---|
Try this idea: calculate sums in all prefixes (from empty to the whole sequence) and then sum of elements in a some substring is difference of two numbers. Hope this helps. If not, I can give you detailed solution.
I don't get it properly.
Look: you have an array:
1 2 3 4 5
. It has the following prefixes: "", "1", "1 2", and so on. You calculate sum of numbers in each such prefix and get 0, 1, 1+2=3, 1+2+3=6, 10 and 15 (let's call its[]
). Then, to calculate, for example, sum from 2 to 4, you just calculates[4] - s[1]=9
. Elements before 2 were reduced.This idea can help you solving this problem: you run down left border of a substring and then you can calc amount of required substrings in O(1) for each left border.
I get your first ideal and I use it in my code.But still don't get your second idea. here is my code:http://pastebin.com/abRxS9kg
I get it.Thanks to yeputons and ALias both of you