Блог пользователя bursty

Автор bursty, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
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);
»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

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.me/blog/entry/94302#comments

See this blog which may clear out your doubts.

Upvote the comment if it was of any use.