THE_THUNDERSTORM_BEGINS's blog

By THE_THUNDERSTORM_BEGINS, history, 3 months ago, In English

in this blog i wanna demonstrate a stratigy that i came up with recently

Its usefull to calculate number of arrays with a sum of K in O(nlog(n)) complexity

If we had an array a with n elements

We loop through the indices At each index we consider all subarrays  ending with the current element

As we are interested in subarray sum We make a map to calculate how many times does a sum occer

at each index do the following

-add subarray with sum 0

-add the value a[i] to all subarrays in the map

The thing is The second one will take up to O(n) How to solve this

Simply we use the WINK WINK ;) stratigy Like this Add a[i] to all past sums WINK WINK ;)

Make a variable sh (initially 0) That represents the added value to all the subarrays imagine us having  sums  1 2 3 If we add to them 2

We add to sh 2

and if we wanna find how many times does 5 occer we search for 3 (5-2)

In particular add a[i] to sh

And from now on if we wanna find how many times does the sum S occur

We search for map[k-sh]

so if we wanna count how many times does a sum K occur We add map[k-sh]  at each index

A simple implementation is like this

int main()
{
    map<int, int> mp;
    int n, sh = 0, res = 0, k;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        mp[-sh]++;
        sh += a[i];
        res += mp[k-sh];
    }
    cout << res;
}

this takes up to O(nlog(n)) time because of map complexity

Here are some problems that we can use the WINK WINK ;) stratigy in:

Good subarrays : https://codeforces.com/problemset/problem/1398/Cv

Subarray with Maximum Product?: https://codeforces.com/problemset/problem/1398/C

Singhal and Multiplication: https://codeforces.com/gym/102767

if you have usefull problems please comment them so i can add them to this blog. Goodbye and have fun coding ;)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by THE_THUNDERSTORM_BEGINS (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by THE_THUNDERSTORM_BEGINS (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it +22 Vote: I do not like it

how did you get to Expert without knowing this before...

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Training and solving harder problems is all i needed. a lot of algorithms help like segmenttree or binary search I had a problem with subarrays and felt good after discovering this Posted so that it helps other to understand this .

  • »
    »
    3 months ago, # ^ |
    Rev. 4   Vote: I like it +17 Vote: I do not like it

    because he has a mind (pure IQ) no knowledge