0

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.

Tapesh
  • 1
  • 1
  • 2
  • 6
    Obligatory: https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h – Passerby Jan 24 '22 at 13:18
  • Could you [edit] show us some simple test cases. – Jabberwocky Jan 24 '22 at 13:26
  • 4
    Do you see the part in the problem statement where it says `Since the answer can be very large, print it modulo $$$10^{9} + 7$$$.`? You should make sure your program does this. In order to avoid the overflow issues, you should use the modulo logic every time the number might get above that value. – Karl Knechtel Jan 24 '22 at 13:27
  • 1
    With your test case the value of `abc` exceeds the capacity even of `long long int`. Add `cout << abc << "\n";` at the end of the for loop and you'll see. – Jabberwocky Jan 24 '22 at 13:33
  • This kind of exercise expects you to be familiar with the modulus identity `(a * b) % m == ((a % m) * (b % m)) % m`. (And, of course, to read all of it.) – molbdnilo Jan 24 '22 at 13:45
  • Thanks, Passerby for the information. I understand! – Tapesh Jan 24 '22 at 13:53
  • I don't know about modulo logic, please explain a little bit more... Karl Knechtel and molbdnilo – Tapesh Jan 24 '22 at 13:54
  • I did not know this, jabberwocky. Well I tried this too but still not getting expected output – Tapesh Jan 24 '22 at 13:57
  • 1
    I got `5250892003678722536788615695`, before modulo `1'000'000'007`. After the modulo, `331264319`. Huzzah! Codeforces is a programming contest, to challenge yourself to solve the problem. It has its own forums. Coming SO for help is like waiting a day to do crossword puzzles so you can use the answer key. – Eljay Jan 24 '22 at 14:12
  • Thanks for answering this question. Can you please tell me, what should I write in my code... As I am a beginner, I have no idea how to use the % operator to avoid these issues. @Eljay – Tapesh Jan 24 '22 at 14:28
  • That's a big ask for a Q&A forum like this. What you really need is a [good C++ book](https://stackoverflow.com/a/388282/4641116). – Eljay Jan 24 '22 at 14:50

2 Answers2

1

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;
}
nielsen
  • 5,641
  • 10
  • 27
0

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)

StandingPad Animations
  • 366
  • 3
  • 8