I am solving a problem of code forces. Here is the problem link -> Problem Link My code passes 9 test cases out of 10 and the 10th case is this

100

??b?a?a???aca?c?a?ca??????ac?b???aabb?c?ac??cbca???a?b????baa?ca??b???cbc??c??ab?ac???c?bcbb?c??abac

and the error I got is this

wrong answer expected '331264319', found '-2013109745'

Diagnostics detected issues [cpp.clang -diagnose]: p71.cpp:14:20: runtime error: signed integer overflow: 3 * 965628297 cannot be represented in type 'int' SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:14:20 in

Other test cases

6 ac?b?c output - 24

7 ??????? output - 2835

9 cccbbbaaa output - 0

100 accbaccabccbbbbabacabaaccacbcbcababbbcbcbcccabcbbc?caaabcabcaaccbccabaaaaccacabbaabcbbccbbababaac output - 14634

This all test cases gives the right answer except the 1st on

and my code which I was submitted is this

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

int main(){
    int n; cin>>n;  
    string s; cin>>s;
    
    int e=1, a=0, ab=0, abc=0;
    for(int i=0; i<n; i  ){
        if(s[i] == 'a') a =e;
        else if(s[i]=='b') ab =a;
        else if(s[i]=='c') abc =ab;
        else if(s[i]=='?') {
            abc = 3*abc ab;
            ab = 3*ab a;
            a = 3*a e;
            e = 3*e;
        }
    }  
    cout<<abc<<endl;
    return 0;
}

I have tried these things -> Change int to long long int.

Here the output changes but is still wrong and negative. Output -> -1959750440526388721.

Then I tried using unsigned while declaring variables. This also gives me wrong and but not negative. Output -> 2281857551.

CodePudding user response：

Since you need the result "modulo 10^9 7", you can reduce the result of all additions and multiplications "modulo 10^9 7" (i.e. find the remainder after division by 10^9 7 - this is what the % operator does).

In the code, you can either do this in each calculation or at the end of the loop. Applying the first option (and a few good habits) looks like this:

#include <iostream>
#include <string>

// Avoid using namespace std;

int main() {
    unsigned n; std::cin >> n;  
    std::string s; std::cin >> s;
    
    unsigned e = 1, a = 0, ab = 0, abc = 0;  // We do not need negative numbers
    unsigned m = 1000000007;   // Calculate result modulo 10^9 7
    for(unsigned i = 0; i < n; i  ) {
        if(s[i] == 'a') a = (a   e) % m;
        else if(s[i]=='b') ab = (ab   a) % m;
        else if(s[i]=='c') abc = (abc   ab) % m;
        else if(s[i]=='?') {
            abc = (3 * abc   ab) % m;
            ab = (3 * ab   a) % m;
            a = (3 * a   e) % m;
            e = (3 * e) % m;
        }
    }  
    std::cout << abc << std::endl;
    return 0;
}

CodePudding user response：

Basically, not every integer is created equal. They have a max size in memory.

The issue is that there's not enough memory to represent such a large number, so the computer doesn't have enough space to represent your number.

EDIT: A better solution would be to use the % operator to avoid these issues. According to the exercise, that's what's recommended

Old solution:

A solution would be to use a different type of int like a int64_t (or if exact width isn't needed then long long would work too)