Kickstart 2020 Round B WA in Test set 2 | Problem C

Hi, I am unable to understand why I’m getting a WA for test-set 2. The idea I’ve implemented it to count how many times a symbol would contribute to the final answer. I think I’m making some mistake in doing modulo with 1e9 but not able to understand where. Can you help me figure this out?

Link to the problem

Here’s my code:

    #include <bits/stdc++.h>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define lli long long int
    #define ulli unsigned long long int
    #define for0(i,n) for(long long int i=0;i<(long long int)n;i++)
    #define for1(i,n) for(long long int i=1;i<(long long int)n;i++)
    #pragma GCC target ("sse4.2")
    #include <algorithm>

    int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    	int t;
    	cin>>t;
    	int cl=1;
    	const ulli bound = 1000000000;
    	while(t--){
    	    string s;
    	    cin>>s;
    	    ulli curr=1, latest=1;
    	    stack<lli> st;
    	    st.push(1);
    	    lli ea=0, we=0, no=0, so=0;
    	    for0(i,s.size()){
    	        if(s[i]>='0' && s[i]<='9'){
    	            lli x = s[i]-'0';
    	            st.push(x);
    	            curr*=x;
    	        } else if(s[i]!=')'){
    	            switch(s[i]){
    	                case 'E': ea=(ea+(curr%bound));
    	                break;
    	                case 'W': we=(we+(curr%bound));
    	                break;
    	                case 'N': no=(no+(curr%bound));
    	                break;
    	                case 'S': so=(so+(curr%bound));
    	                break;
    	            }
    	        } else {
    	            if(!st.empty()){
    	                curr/=st.top();
    	                st.pop();
    	            }
    	        }
    	    }
    	    lli ver = (so-no);
    	    lli hor = (ea-we);
    	    cout<<"Case #"<<cl<<": ";
    	   if(bound+hor+1<0){
    	       cout<<bound-(abs(hor)%bound)+1<<" ";
    	   } else
    	        (hor<0) ? cout<<bound+hor+1<<" " : cout<<(hor%bound)+1<<" ";
    	    if(bound+ver+1<0){
    	       cout<<bound-(abs(ver)%bound)+1<<" ";
    	   } else
    	    (ver<0) ? cout<<bound+ver+1<<"\n" : cout<<(ver%bound)+1<<"\n";
    	    ++cl;
    	}
    	return 0;
    }

it is overflowing the size of long long int, curr could go to more tha 1e18

But I’ve used unsigned long long int for curr and adding curr%1e9

but when u r pushing it in stack curr can go off limit when the case is something like this
9(S9(S9(S9(S…))))

i did a similar mistake, my suggestion would be when you are multiplying then also use modulo
Instead of
curr*=x; use
curr=(curr * x) % bound;

Thanks,
I changed to this but it still gives the same verdict.

I guess won’t that be the case if I’m pushing curr to the stack, I’m pushing just the number I read into the stack.

with your code variable curr can go upto 9^500 something and u can store it in ulli

i used the same approach but i saved the numbers as string

Ohh I think I got it. Thanks.
Can you share the part handled the overflow with a string?

 stack<char>st;
string cur = "1";
string n = "0", so = "0", e = "0", w = "0";
forr(i, len) {
  if (s[i] == '(')
    continue;
  if (s[i] >= '2' && s[i] <= '9') {
    cur = multiply(cur, s[i]);
    //cur *= (s[i] - '0');

    st.push(s[i]);
  }
  else if (s[i] == ')') {
    cur = longDivision(cur, st.top() - '0');
    st.pop();
  }
  else {
    if ((s[i] == 'N'))
      n = findSum(n, cur)   ;
    if ((s[i] == 'E'))
      e = findSum(e, cur)   ;
    if ((s[i] == 'W'))
      w = findSum(w, cur)   ;
    if ((s[i] == 'S'))
      so = findSum(so, cur)   ;
  }
}
int w2, e2, n2, so2;
w2 = mod(w, MOD);
e2 = mod(e, MOD);
n2  = mod(n, MOD);
so2 = mod(so, MOD);