### Tintin's blog

By Tintin19 months ago, ,

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

 » 19 months ago, # |   +1 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.
•
 » » 19 months ago, # ^ |   0 I don't get it properly.
•
 » » » 19 months ago, # ^ |   0 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 it `s[]`). Then, to calculate, for example, sum from 2 to 4, you just calculate `s[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.
•
 » » » » 19 months ago, # ^ |   0 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
•
 » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 ``````s[0] = 0; for (int i = 0; i < a.size(); i++) s[i + 1] += s[i] + a[i]; for (int i = 0; i <= s.size(); i++) { res += cnt[s[i] % d]; cnt[s[i] % d]++; } ``````
•
 » » » » » » 19 months ago, # ^ |   0 I get it.Thanks to yeputons and ALias both of you