Google Kickstart Problem C in Round 1B 2020

Can anyone point out the mistake in this code? It passes the test set 1 but gives a WA for test set 2.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <climits>

using namespace std;

const int max_lim = 1e9;

void cal_coord(long long &x, long long &y, char d, long long f){
    if(d == 'N')
        y = (y%max_lim-f%max_lim+max_lim)%max_lim;

    else if(d == 'S')
        y = (y%max_lim+f%max_lim)%max_lim;

    else if(d == 'E')
        x = (x%max_lim+f%max_lim)%max_lim;

    else if (d == 'W')
        x = (x%max_lim-f%max_lim+max_lim)%max_lim;

int main( ){


    int t; cin>>t;
    for(int case_no = 1; case_no <= t; case_no++){      
        string s; cin>>s;

        long long mul = 1;
        long long x = 0, y = 0;
        stack<char> st{};
        s = '('+s+')';
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ')'){
                while( != '('){
                    cal_coord(x, y,, mul);

                if(st.size() && ('0' <= && <= '9')){
                    int m ='0';
                if('0' <= s[i] && s[i] <= '9')
                    mul *= (s[i] - '0');
        cout<<"Case #"<<case_no<<": "<<(x+1)<<" "<<(y+1)<<'\n';

    return 0;

Problem Link

The variable mul will overflow any data type in worst case. You were supposed to take mul % 1000000000

1 Like

Thanks for the reason. But I think that makes the division fail. Since 1e9 is not a prime number, we can’t use Little Fermat’s theorem too. Can you suggest me an approach to overcome that?

Use a vector instead of stack and whenever you need to compute factor, multiply all the numbers in the vector. When multiplying, keep taking mod. In case of addition, push_back in vector and deletion, pop_back. Since query size is just 2000, it will easily fit in the time limit. Since we are computing factor from scratch in every query, we don’t need to divide.

Code for reference eW68YK - Online C++0x Compiler & Debugging Tool -

1 Like

Thank you very much. That worked!!

1 Like