bursty's blog

By bursty, history, 4 weeks ago, In English

In problem C of Educational Codeforces Round 114 I was using accumulate function to calculate sum of the elements in an array which IDK why messed up my solution and giving the sum of array larger than actual which eventually caused WA and when the sum calculted in o(n) it accepted the submission

here is accepted submission 129428522 here is WA submission 129427890

is there any limit on using accumulate or anything else?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
int sum = accumulate(all(arr), 0);

Here, bro, you did a mistake here. since You put 0 which is an int as the last argument, It will add values to an int and then assign it to sum. And this will cause overflow;

Now instead of this, you should use

long long sum = accumulate(all(arr), 0ll);
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks

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

    shouldn't we store it in long long or long instead of int if its giving integer overflow??

»
4 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Actually you have to understand the implementation of accumulate method in STL in order to know that cause of the mistake.

In short use:

sum=accumulate(v.begin(),v.end(),0LL);

Reason:


sum=accumulate(v.begin(),v.end(),0); is same as int result = 0; for (int x : v) result += x; sum = result;

Even though you declare the vector elements as long long , it is the 0 that is being passed as the parameter to a generic template which computes the sum

As the 0 is of type INT and not LONG LONG hence the sum will remain as INT and hence the overflow .

This is the real mechanism of accumulate method as generic template

template <class InputIterator, class T>
   T accumulate (InputIterator first, InputIterator last, T init)
{
  while (first!=last) {
    init = init + *first;  // or: init=binary_op(init,*first) for the binary_op version
    ++first;
  }
  return init;
}

https://codeforces.com/blog/entry/94302#comments

See this blog which may clear out your doubts.

Upvote the comment if it was of any use.