BanazadehAria's blog

By BanazadehAria, history, 5 years ago, In English

Hi,

Problem ==> http://codeforces.com/problemset/problem/1084/C

My solution gets WA in test case 10 and I think it because overflow but I can't see any overflow problem.

#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9+7;

int MOD(int x){
    return ((x%INF)+INF)%INF;
}

int main()
{
    string n;cin >> n;
    string s;
    for(int i=0;i<n.size();++i){
        if(n[i]=='a' || n[i]=='b') s+=n[i];
    }
    //Get number of all of the contigiuos 'a's
    vector<int> ans;
    int cnt = 0;
    for(int i=0;i<s.size();++i){
        if(s[i]=='a') ++cnt;
        else{
            ans.push_back(cnt);cnt=0;
        }
    }ans.push_back(cnt);
    //Calculate the answer
    long long res=1;
    for(auto &i : ans){
        res = MOD(MOD(res) * MOD(i+1));
    }cout << res-1;
}
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Overflow in line

res = MOD(MOD(res) * MOD(i+1));

$$$MOD(res) * MOD(i+1)$$$ might not fit in int limit (Can be of order (10 ^ 9) * (10 ^ 5))

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How i can make it correct? I used unsigned long long it doesnt work.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Change the MOD function to accept ull instead of int

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your AC code.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you can you tell me how 1ll work?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          That's not needed since we kept long long int as datatype of res. If that is not the case multiplying by 1ll promotes the type of integer to long long int (according to normal rules of type promotion (casting) thereby helping us avoid overflows in this case)

          Edit : Ok it will be needed since you return int in the MOD function.