# Google Kickstart Round 1B probem C

Guys,how did u solve the problem C?I am unable to understand the editorial.Any kind of help would be appreciated

I wrote my own parser function which solved it using recursion

My code
``````bool isDigit(char a){
return a >= '0' && a <= '9';
}

long long int parseNumber(string &a, int &i){
ll num = 0;
while(isDigit(a[i])){
num = num*10%inf;
num = (num + a[i]-'0')%inf;
i++;
}
return num;
}

pair<ll,ll> parser(string &a, int &i){
pair<ll,ll> change(0,0);
ll j;
while(i < a.size()){
if(isdigit(a[i]))j = parseNumber(a,i);
if(a[i] == '('){
i++;
auto k = parser(a,i);
change.first = (change.first + j*k.first%inf)%inf;
change.second = (change.second + j*k.second%inf)%inf;
debug(i,j,change);
}
else if(a[i] == ')'){
i++;
debug(i,change);
return change;
}
else{
if(a[i] == 'N')
change.second = (change.second-1+inf)%inf;
if(a[i] == 'S')
change.second = (change.second+1)%inf;
if(a[i] == 'E')
change.first = (change.first+1)%inf;
if(a[i] == 'W')
change.first = (change.first-1+inf)%inf;
i++;
}
}
debug(change);
return change;
}

void solve(int test_case){
cout << "Case #" << test_case << ": ";
string a;
cin>> a;
debug(a);
int i = 0;
auto k = parser(a,i);
k.F+=1;
k.S+=1;
cout << k.F << " " << k.S << "\n";
}

``````
1 Like

Here is my approach: Problem C

1 Like

First, you need to just see that no matter the order of the moves finally you will reach the same position even if the order changes so, for each letter you can find out the number of repetitions by creating a stack and as soon as you receive a number the number is put into the stack and for a letter the number of repetition is the product of all the number in the stack modulo 10^9 now if you reach a “)” you remove the topmost element in the stack and so on.
Finally you can calculate the change in the positions.And you receive the answer.
Here is my code

1 Like

I used stack to calculate the number of times each direction was used. (you can solve a similar in spoj CODE:MMASS)

Then simply subtract south-north and east-west (taking mod 10^9) . add 1 to both and print.

1 Like

Thanks man! It was a nice explanation

1 Like

If u need python code ``````import sys
flush = sys.stdout.flush

nums = set([str(_) for _ in range(10)])
N = 10**9

for t in range(1, T+1):

cur = [0, 0]

stack = []

for char in program:
if char == 'N':
cur -= 1
elif char == 'S':
cur += 1
elif char == 'W':
cur -= 1
elif char == 'E':
cur += 1

elif char in nums:
stack.append((cur, cur, int(char)))

elif char == '(':
cur = [0, 0]

elif char == ')':
pop = stack.pop()
cur=pop+pop*cur
cur=pop+pop*cur

final_row = (1+cur)%N
if final_row == 0:
final_row = N

final_column = (1+cur)%N
if final_column == 0:
final_column = N

print("Case #%d: %d %d" % (t, final_column, final_row))``````
1 Like

A similar solution to this Long Challenge’s REBIT. Created a structure that holds value for North, East , West , South moves and defined Add and Multiply operations.

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

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

const ll mod  = 1e9;
const db eps  = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf = LLONG_MAX;

#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl

struct dir
{
ll north, east, west, south;
dir(ll _n , ll _e , ll _w , ll _s) : north(_n), east(_e), west(_w), south(_s) {}
};

dir add (const dir& dir1, const dir& dir2)
{
return dir( (dir1.north+dir2.north)%mod , (dir1.east+dir2.east)%mod , (dir1.west+dir2.west)%mod , (dir1.south+dir2.south)%mod )  ;
}

dir mul (const ll m, const dir& dir2)
{
return dir( (m*dir2.north)%mod , (m*dir2.east)%mod , (m*dir2.west)%mod , (m*dir2.south)%mod )  ;
}

int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
freopen("error.txt","w",stderr);
#endif

ll t;
cin >> t;

for(ll i=1 ; i<=t ; ++i)
{
cout << "Case #" << i << ": ";
string s;
cin >> s;

stack<int> numbers;
stack<char> characters;
stack<dir> directions;

ll north =0 ,west = 0,east = 0,south = 0;

for(ll i=0 ; i<s.size() ; ++i)
{

if( s[i] >= '1' && s[i] <= '9') numbers.push(s[i]-'0');
else if( s[i] == '(') characters.push( s[i] );
else if( s[i] == ')' )
{
char c = characters.top();
characters.pop();

dir ans = dir(0,0,0,0);

while(c!='(')
{
directions.pop();

c = characters.top();
characters.pop();
}

ll multiplier = numbers.top();
numbers.pop();

ans = mul( multiplier , ans );

characters.push('#');
directions.push(ans);

}
else
{
characters.push( '#' );
if(s[i] == 'N') directions.push( dir(1,0,0,0) );
if(s[i] == 'E') directions.push( dir(0,1,0,0) );
if(s[i] == 'W') directions.push( dir(0,0,1,0) );
if(s[i] == 'S') directions.push( dir(0,0,0,1) );
}

}

dir ans = dir(0,0,0,0);
while( !directions.empty() )
{
dir hey = directions.top();
directions.pop();

}

if(ans.east - ans.west >= 0)
cout << 1 + (ans.east-ans.west)%mod << " " ;
else
cout << (ll)1e9 - (ans.west - ans.east - 1)%mod << " " ;

if(ans.south - ans.north >= 0)
cout << 1 + (ans.south-ans.north)%mod << endl ;
else
cout << (ll)1e9 - (ans.north - ans.south - 1)%mod << endl ;

}

return 0;
}
``````
1 Like