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

WA in a task due to accumulate function of c++
Автор bursty, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
← 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);
→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    → Ответить
»
3 года назад, # |
← 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.com/blog/entry/94302#comments

See this blog which may clear out your doubts.

Upvote the comment if it was of any use.

→ Ответить