Google Kickstart Round: B; Problem Name: Robot Path Decoding

Problem Link: Robot Path Decoding.

I recently was trying to solve the above-mentioned problem and came up with a stack (std :: stack<std :: pair <int, int>>) based solution where I am storing the two information regarding the commands during paring i.e. how many times the last command is going to repeat and what is the start index of the repeating command.

But I am getting TLE on submission, so can anyone help me out on how can I optimise the solution or other alternative ways of solving the problem?

Solution Source-Code In C++

#include <iostream>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <cstdio>

typedef unsigned long long ull_t;
typedef long long ll_t;

#define FAST_IO(value) std :: ios :: sync_with_stdio(value); std :: cin.tie(NULL)
#define MOD 1000000007 // Constant (prime number) used in most competitive programming problems to reduce the answer to a 32-bit integer.
#define PI 3.141592653589793 // Number of digits(15) of Pi which JPL uses for Interplanetary Caculations.
#define GOLDEN_RATIO 1.618033988749895 // Number of digits(15).

static void move_robot(std :: pair <int, int> &, const char);
static void compute_final_location(std :: pair <int, int> &, const std :: string);

int main(void) {
    FAST_IO(0);
    int test;
    std :: cin >> test;
    for(int t = 1; t <= test; ++t) {
        std :: pair <int, int> robot_loc = {1, 1};
        std :: string command;
        std :: cin >> command;
        compute_final_location(robot_loc, command);
        std :: cout << "Case #" << t << ": " << robot_loc.first << " " << robot_loc.second << std :: endl;
    }
    return 0;
}

static void move_robot(std :: pair <int, int> & robot_loc, const char direction) {
    switch(direction) {
        case 'N': {
            robot_loc.second -= 1;
        }
        break;
        case 'S': {
            robot_loc.second += 1;
        }
        break;
        case 'E': {
            robot_loc.first += 1;
        }
        break;
        case 'W': {
            robot_loc.first -= 1;
        }
        break;
    }
    if(robot_loc.first > 1e9) {
        robot_loc.first = 1;
    } else if(robot_loc.first < 1) {
        robot_loc.first = 1e9;
    }
    if(robot_loc.second > 1e9) {
        robot_loc.second = 1;
    } else if(robot_loc.second < 1) {
        robot_loc.second = 1e9;
    }
}

static void compute_final_location(std :: pair <int, int> & robot_loc, const std :: string command) {
    std :: stack <std :: pair <int, int>> repeat_command;
    for(size_t i = 0; i < command.size(); ++i) {
        if(command[i] == '(') {
            continue;
        }
        if(command[i] >= '2' && command[i] <= '9') {
            repeat_command.push(std :: make_pair((command[i] - '0') - 1, i + 1));
            continue;
        }
        if(command[i] == ')') {
            auto & stack_top = repeat_command.top();
            if(stack_top.first) {
                i = stack_top.second;
                stack_top.first -= 1;
            } else {
                repeat_command.pop();
            }
        } else {
            move_robot(robot_loc, command[i]);
        }
    }
}

What you’re doing here is essentially expanding the ‘program’ into a sequence of ‘N’, ‘E’, ‘W’, and ‘S’. It is easy to see how that will blow up into a very large program. Consider the program 9(9(9(N))). This will expand into a program of size 9^3. Following a similar construction, we can write a program of length 3n+1 which expands into a program of length 9^n, for any n.

You can look at the ‘Analysis’ tab on the problem page to see the intended solution.

1 Like

@psaini72 Thanks for the info, I initially suspected it. Anyways I updated my code in order to solve the problem by reading the Analysis section but the solution only passes the test case of 11pts, I am not able to come up with a concrete solution. Can you help me out?

Moreover the idea which I used was to calculate the dx and dy for those instructions which are going to be repeated and stored the values in a stack of the form std :: stack <std :: pair <int, std :: pair <int, int>>> .
Basically I am storing the number of times the instruction is going to repeat as well as dx and dy, but I am not getting why the solution is giving is WA.
dx implies change in x-coordinate value when repeat i.e. X(Y) instruction has run one time.
dy implies change in y-coordinate value when repeat i.e X(Y) instruction has run one time.

Source-Code In C++

#include <iostream>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <cstdio>

typedef unsigned long long ull_t;
typedef long long ll_t;

#define FAST_IO(value) std :: ios :: sync_with_stdio(value); std :: cin.tie(NULL)
#define MOD 1000000007 // Constant (prime number) used in most competitive programming problems to reduce the answer to a 32-bit integer.
#define PI 3.141592653589793 // Number of digits(15) of Pi which JPL uses for Interplanetary Caculations.
#define GOLDEN_RATIO 1.618033988749895 // Number of digits(15).

#define MAX_LIMIT 1000000000

static void move_robot(std :: pair <ll_t, ll_t> &, const char);
static std :: pair <ll_t, ll_t> compute_final_position_robot(const std :: string &);

int main(void) {
    FAST_IO(0);
    int test;
    std :: cin >> test;
    for(int t = 1; t <= test; ++t){
        std :: string command;
        std :: cin >> command;
        std :: pair <ll_t, ll_t> robot_final_pos = compute_final_position_robot(command);
        std :: cout << "Case #" << t << ": " << robot_final_pos.first << " " << robot_final_pos.second << std :: endl;
    }
    return 0;
}

static void move_robot(std :: pair <ll_t, ll_t> & robot_loc, const char direction) {
    switch(direction) {
        case 'N': {
            robot_loc.second -= 1LL;
        }
        break;
        case 'S': {
            robot_loc.second += 1LL;
        }
        break;
        case 'E': {
            robot_loc.first += 1LL;
        }
        break;
        case 'W': {
            robot_loc.first -= 1LL;
        }
    }
}

static std :: pair <ll_t, ll_t> compute_final_position_robot(const std :: string & command) {
    std :: stack <std :: pair <ll_t, std :: pair <ll_t, ll_t>>> repeat_command;
    std :: pair <ll_t, ll_t> pos_change = {0, 0}; // (dx, dy)
    std :: pair <ll_t, ll_t> final_pos = {1, 1};
    for(size_t i = 0; i < command.size(); ++i) {
        if(command[i] == '(') {
            continue;
        }
        if(command[i] >= '2' && command[i] <= '9') {
            repeat_command.push(std :: make_pair(command[i] - '0', pos_change));
            pos_change = {0, 0};
            continue;
        }
        if(command[i] == ')') {
            std :: pair <ll_t, std :: pair <ll_t, ll_t>> & top_data = repeat_command.top();
            pos_change.first *= top_data.first;
            pos_change.second *= top_data.first;
            pos_change.first += (top_data.second.first);
            pos_change.second += (top_data.second.second);
            repeat_command.pop();
            continue;
        }
        move_robot(pos_change, command[i]);
    }
    final_pos.first += pos_change.first;
    final_pos.second += pos_change.second;
    if(final_pos.first > MAX_LIMIT) {
        final_pos.first %= MAX_LIMIT;
    }
    if(final_pos.second > MAX_LIMIT) {
        final_pos.second %= MAX_LIMIT;
    }
    if(final_pos.first < 1) {
        final_pos.first = MAX_LIMIT + final_pos.first;
    }
    if(final_pos.second < 1) {
        final_pos.second = MAX_LIMIT + final_pos.second;
    }
    return final_pos;
}

Hey, could you help me with my solution. I got MLE on second test case.

I am storing the expanded program in the stack. Max length of characters as mentioned in the problem is <=10^4. Is that too big for stack? How can I modify the approach to make it work? Thanks!

Code: ideone

When you are multiplying, you are doing an incorrect calculation. Let’s say MAX_LIMIT was 5. If you were at (1,1) and move 4 steps South twice, you should end up at (1,3). But according to the calculation you have done, you will get (1,4)

The correct calculation for moving s steps in any direction x number of times is

1 +( x(s-1) ) \% \text{MAX\_LIMIT}

This should give you a hint that you should be working modulo MAX_LIMIT, any cell (r,c) should be treated as (r-1,c-1) and multiplying any vector (x,y) by a number k is then simply (kx \mod \text{MAX\_LIMIT} , ky \mod \text{MAX\_LIMIT})

Max number of characters of the given program is <= 10^4 but the max number of characters in the expanded program can be as large as 9^{ \frac{10^4 - 1}{3} } as I demonstrated above. Of course you cannot store that on any computer.

Oh, I thought that the total length of the expanded program is limited to 10^4 but that was only for test case 1. Original constraint says program could be upto 2000 characters hence worst case of expanded program would be 9n .

You can take look Here (its a solution with stack and explanation )

@psaini72 If I were doing incorrect calculation, wouldn’t I get the WA for the first case of 11pts i.e. Test-Set 1 rather program is passing that case but not the case Test-Set-2.

@mcqueen2018 Can you give me some test-cases where my solution would fail because the test-cases which I am generated, my solution is giving right answers on those as I am cross-checking my programs output to a correct solution program output.

@ssjgz Could you help me out on this problem, I am kind of stuck in this problem for hours?

My mistake I thought your modulo part was wrong. It is wrong but for a different reason. Your problem is with modulo and negative numbers. x%a when x is negative evaluates to -(abs(x)%a), if that makes sense. Here is a test case which gives a wrong answer

1
2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(N))))))))))))))))))))))))))))))

Ya, I figured it out that C++ % operator is just the remainder operator, not the modular arithmetic operator.

I am still getting WA on the Test-Set 2 after making code updates which include taking care of -ve numbers when doing %:

Updated Source-Code In C++

#include <iostream>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <cstdio>

typedef unsigned long long ull_t;
typedef long long ll_t;

#define FAST_IO(value) std :: ios :: sync_with_stdio(value); std :: cin.tie(NULL)
#define MOD 1000000007 // Constant (prime number) used in most competitive programming problems to reduce the answer to a 32-bit integer.
#define PI 3.141592653589793 // Number of digits(15) of Pi which JPL uses for Interplanetary Caculations.
#define GOLDEN_RATIO 1.618033988749895 // Number of digits(15).

#define MAX_LIMIT 1000000000LL

static ll_t compute_modulo(const ll_t &, const ll_t &);
static void move_robot(std :: pair <ll_t, ll_t> &, const char);
static std :: pair <ll_t, ll_t> compute_final_position_robot(const std :: string &);

int main(void) {
    FAST_IO(0);
    int test;
    std :: cin >> test;
    for(int t = 1; t <= test; ++t){
        std :: string command;
        std :: cin >> command;
        std :: pair <ll_t, ll_t> robot_final_pos = compute_final_position_robot(command);
        std :: cout << "Case #" << t << ": " << robot_final_pos.first << " " << robot_final_pos.second << std :: endl;
    }
    return 0;
}

static ll_t compute_modulo(const ll_t & dividend, const ll_t & divisor) {
    ll_t remainder = dividend % divisor;
    return remainder < 0 ? remainder + divisor : remainder;
}

static void move_robot(std :: pair <ll_t, ll_t> & robot_loc, const char direction) {
    switch(direction) {
        case 'N': {
            robot_loc.second -= 1LL;
        }
        break;
        case 'S': {
            robot_loc.second += 1LL;
        }
        break;
        case 'E': {
            robot_loc.first += 1LL;
        }
        break;
        case 'W': {
            robot_loc.first -= 1LL;
        }
    }
}

static std :: pair <ll_t, ll_t> compute_final_position_robot(const std :: string & command) {
    std :: stack <std :: pair <ll_t, std :: pair <ll_t, ll_t>>> repeat_command;
    std :: pair <ll_t, ll_t> pos_change = {0, 0}; // (dx, dy)
    for(size_t i = 0; i < command.size(); ++i) {
        if(command[i] == '(') {
            pos_change = {0, 0};
            continue;
        }
        if(command[i] >= '2' && command[i] <= '9') {
            // std :: cout << "dx: " << pos_change.first << " dy: " << pos_change.second << std :: endl;
            repeat_command.push(std :: make_pair(command[i] - '0', pos_change));
            continue;
        }
        if(command[i] == ')') {
            std :: pair <ll_t, std :: pair <ll_t, ll_t>> & top_data = repeat_command.top();
            // std :: cout << "[" << top_data.first << "," << top_data.second.first << "," << top_data.second.second << "]" << std :: endl;
            pos_change.first *= top_data.first;
            pos_change.second *= top_data.first;
            // std :: cout << "pos_change.first: " << pos_change.first << " pos_change.second: " << pos_change.second << std :: endl;
            pos_change.first += (top_data.second.first);
            pos_change.second += (top_data.second.second);
            repeat_command.pop();
            continue;
        }
        move_robot(pos_change, command[i]);
    }
    pos_change.first = compute_modulo(1 + pos_change.first, MAX_LIMIT);
    pos_change.second = compute_modulo(1 + pos_change.second, MAX_LIMIT);
    if(!pos_change.first) {
        pos_change.first = MAX_LIMIT;
    }
    if(!pos_change.second) {
        pos_change.second = MAX_LIMIT;
    }
    // std :: cout << "Pos-Change: (" << pos_change.first << ", " << pos_change.second << ")" << std :: endl;
    return pos_change;
}

The test case which you have mentioned, I am getting correct answer for that and other test cases which I have created:

Test-Case-1:

5
SSSEEE
N
N3(S)N2(E)N
2(3(NW)2(W2(EE)W))
9(9(9(N)))

My Code Output:

Case #1: 4 4
Case #2: 1 1000000000
Case #3: 3 1
Case #4: 3 999999995
Case #5: 1 999999272

Test-Case-2:

5
6(WW)3(W)9(W)7(N)
E7(EWNS)
6(2(SWN)4(W))
W2(SN)NSEW
6(NSEW2(EE)3(EE)5(WE2(EW)))

My Code Output:

Case #1: 999999977 999999994
Case #2: 2 1
Case #3: 999999965 1
Case #4: 1000000000 1
Case #5: 61 1

Test-Case-3:

5
9(N9(N))
9(W9(NS9(NSE9(NSEW))))
5(NSEW)6(NS)7(N9(N))
5(NSEW7(NSEW8(NSEW)))
NSEW9(N9(N)9(N9(N)))

My Code Output:

Case #1: 1 999999911
Case #2: 721 1
Case #3: 1 999999931
Case #4: 1 1
Case #5: 1 999999101

Test-Case-4:

3
9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N))))))))))
9(N9(N9(N9(N9(N9(N9(N9(N9(N)))))))))
9(N9(N9(N9(N9(N9(N9(N9(N))))))))

My Code Output:

Case #1: 1 77367551
Case #2: 1 564151952
Case #3: 1 951572441

Test-Case-5:

5
2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(N))))))))))))))))))))))))))))))
9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N))))))))))2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(N))))))))))))))))))))))))))))))
2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(N))))))))))))))))))))))))))))))9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N)))))))))
9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N)))))))))SSSEEEN3(S)N2(E)N2(3(NW)2(W2(EE)W))
SSSEEENN3(S)N2(E)N2(3(NW)2(W2(EE)W))

My Code Output:

Case #1: 1 926258177
Case #2: 1 3625727
Case #3: 1 564151951
Case #4: 8 564151948
Case #5: 8 999999997

I have cross-checked output given by my code with the accepted solutions for the problem and I am getting the correct output. Still, my code is failing to pass the Test Set 2.

@psaini72 @mcqueen2018 @ssjgz

Finally passed the second test-set. :slight_smile:

The bug was as the size of the program grows exponentially i.e. if I have a program like the following:

9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N)))))))))))))))))))))))

then 9\underbrace{(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N)))))))))))))))))))))))}_{\text{Number of times the program executes = 1107867264956562636990}} which is pretty huge to be stored in an long long int thus introduced a bug in the program.

Anyway if anyone is solving the problem and not passing the Test-Set-2, try run your program on the following test-cases:

5
9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N))))))))))
9(N9(N9(N9(N9(N9(N9(N9(N9(N)))))))))
9(N9(N9(N9(N9(N9(N9(N9(N))))))))
9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N)))))))))))))))))))))))
9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N)))))))))))))))))))))))9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N))))))))))2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(N))))))))))))))))))))))))))))))2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(N))))))))))))))))))))))))))))))9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N)))))))))9(N9(N9(N9(N9(N9(N9(N9(N9(N9(N)))))))))SSSEEEN3(S)N2(E)N2(3(NW)2(W2(EE)W))SSSEEENN3(S)N2(E)N2(3(NW)2(W2(EE)W))2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(2(N))))))))))))))))))))))))))))))

Correct Output

Case #1: 1 77367551
Case #2: 1 564151952
Case #3: 1 951572441
Case #4: 1 936267082
Case #5: 15 490410120

Source-Code: Complete Source Code In C++.

2 Likes

Great ! You have given lots of work. congrats

1 Like

Thanks Man :slight_smile:

1 Like

I solved this question by counting the moves it is making to each direction and adding those moves to (1,1) ,Test Set 2 is getting Wrong Answer.

My code:

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

string s;
long long w,h,j;
unordered_map<char,long long> umap;
stack st;

void testcase()
{
cin>>s;
umap[‘N’]=0;
umap[‘S’]=0;
umap[‘E’]=0;
umap[‘W’]=0;
for(j=0;j<s.size();j++)
{
if(s[j]==‘N’ || s[j]==‘S’|| s[j]==‘W’ ||s[j]==‘E’)
{
if(!st.empty())
{
umap[s[j]]+=st.top();
}
else
{
umap[s[j]]+=1;
}
umap[s[j]]=(long long)umap[s[j]]%1000000000;
}
else if(s[j]>=‘2’ && s[j]<=‘9’)
{
if(!st.empty())
{
st.push(st.top()*(s[j]-‘0’));
}
else
{
st.push(s[j]-‘0’);
}
}
else if(s[j]==’)’)
{
st.pop();
}
}
w=umap[‘E’]-umap[‘W’]+1;
h=umap[‘S’]-umap[‘N’]+1;
if(w<=0)
{
w+=1e9;
}
if(h<=0)
{
h+=1e9;
}
if(w>1e9)
{
w-=1e9;
}
if(h>1e9)
{
h-=1e9;
}
return;
}

Your case#5 output is wrong , its Case #5: 1135 666737885. Btw ,thanks for explaining…

my CODE →

#include
#include<bits/stdc++.h>
using namespace std;
long long int pos[1][2];
long long int ans = 0;
map <char,long long int> m;

int dfs(string s,int a,long long int count)
{
           for(int i =a;i<s.length();i++)
    {
            
            if(s[i] == ')')
            return i;
        
            if(s[i] >=50 && s[i] <=57)
                i = dfs(s,i+2,(count*(s[i]-'0'))%1000000000);
                
                
            else
            m[s[i]] = (m[s[i]]+count)%1000000000;
}
}

int main()
{
long long int test;
long long int n;
cin>>test;
string s;
long long act = test;

while(test--)
{   
    memset(pos, 0, sizeof pos);
    m.clear();
    cin>>s;
    long long int count = 1;
    
    
    for(int i =0;i<s.length();i++)
    {
            if(s[i] >=50 && s[i] <=57)
                i = dfs(s,i+2,(count*(s[i]-'0'))%1000000000);
                
            else
            m[s[i]] = (m[s[i]]+count)%1000000000;
        }
        
    pos[0][0] = ((m['S']-m['N'])+1000000000)%1000000000;
    pos[0][1] = ((m['E']-m['W'])+1000000000)%1000000000; 
    


 cout<<"Case #"<<act-test<<": "<<pos[0][1]+1<<" "<<pos[0][0]+1<<endl;
}


return 0;

}

static int fastio = {
#define endl ‘\n’
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(0);
return 0;
}();