ROBOTG - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Lewin Gan
Testers: Kamil Dębowski
Editorialist: Lewin Gan

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Given a robot, a grid, and a command string, find out if you can place the robot somewhere on the grid such that it follows the command string and always stays on the grid.

QUICK EXPLANATION:

The bounds are small enough for an O(nm|s|) solution.

EXPLANATION:

We can try all starting squares and simulate the movement of the robot. If the robot goes out of bounds, we can know that starting square is bad. Please look at the tester’s solution for more details.

In addition, there is an O(|s|) time solution that considers the maximum distance the robot travels up, down, right, and left from the original point. This avoids simulating from every starting grid square, since we know that the simulation will look very similar for those starting squares. Please look at the setter’s solution for more details.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

1 Like
2

please explain the logic with code

3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int testCases = Integer.parseInt(br.readLine());
	for(int i = 0; i < testCases; i++){
		int r = 0;
		int u = 0;
		String[] number = br.readLine().split(" ");
		int row = Integer.parseInt(number[0]);
		int col = Integer.parseInt(number[1]);
		
		String cmd = br.readLine();
		boolean safe = true;
		for(int j=0;j < cmd.length(); j++){
			if(cmd.charAt(j) == 'R'){
				r++;
			}else if(cmd.charAt(j) == 'L'){
				r--;
			}else if(cmd.charAt(j) == 'U'){
				u++;
			}else if(cmd.charAt(j) == 'D'){
				u--;
			}
			if(!(col - Math.abs(r) > 0 || row - Math.abs(u) > 0)){
				safe = false;
			}
		}
		if(safe){
			System.out.println("safe");
		}else{
			System.out.println("unsafe");
		}
	}
}
}

May I know whats wrong with this code. In which case it fails. It is not a correct answer. This is a sincere request. I joined codechef recently. Dont know where to find test cases. I checked with the example inputs of ROBOTG. Its working fine with them. Please help me

4

If you’d like test cases, you can find them here:
input:

output:

3 Likes
5

Please tell me what’s wrong in my code.
#include <stdio.h>
//Compiler version g++ 4.9

int main(void)
{
char str[50];
int i,j,k=0,p,q,r,c,f=0,t;
scanf("%d",&t);
while(t!=0)
{
f=0;
scanf("%d %d",&r,&c);
scanf("%s",str);
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
k=0;
p=i;
q=j;
while(str[k]!=’\0’)
{
if(str[k]==‘R’)
q+=1;
else if(str[k]==‘L’)
q-=1;
else if(str[k]==‘U’)
p+=1;
else
p-=1;
k++;

		}
		if(p<r && q<c && p>0 &&q>0)
		{
			f=1;
			break;
		}
		
	}
}
if(f==1)
printf("safe\n");
else
printf("unsafe\n");

t--;
}
return 0;

}

6

Can anyone tell me why I was getting WA on this code.
I think I’d applied the second logic given in the editorial but still I was getting WA.

Is there anyone else facing the same problem??


[1]


  [1]: http://ideone.com/go8wpx
7

#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int n,m,l=0,r=0,u=0,d=0,flag=1;
cin>>n>>m;
string s;
cin>>s;
int le=s.length();
for (int i = 0; i<le; ++i){
if(s[i]==‘L’)
l++;
else if(s[i]==‘R’)
r++;
else if(s[i]==‘U’)
u++;
else if(s[i]==‘D’)
d++;

		int col=abs(l-r);
		int row=abs(u-d);
		if(row>(n-1) || col>(m-1)){
			cout<<"unsafe"<<endl;
			flag=0;
			break;
		}
	}
	if(flag)
	cout<<"safe"<<endl;
}

}

Can anyone explain what’s wrong in this code ?

8

Thanks a lot for sharing the test case.

9

#include
#include
using namespace std;

int main()
{
int t; cin>>t; int n,m; string s;

while(t--)
{
	cin>>n>>m; cin>>s; int tr=0;
	
	int count1=0,count2=0;
	
	for(int j=0;j<=s.length();j++)
	{
	if(s[j]=='U') count1++;
	if(s[j]=='D') count1--;
	if(s[j]=='L') count2++;
	if(s[j]=='R') count2--;
		
	if(count1==n||count1==-n)
	{
		tr=1; break;
	}	
		
		if(count2==m||count2==-m)
	{
		tr=1; break;
	}	
		
	}
	
	
	if(tr==1)
	cout<<"unsafe"<<endl;
	else
	cout<<"safe"<<endl;
	
	
	
}



return 0;

}

10

To those who are getting wrong answer by calculating the extreme x and y position:
Your approach only checks for extreme x and y position, ie. the maximum displacement from a block rather one should consider the range or the distance that the robot travels.
Consider this test case for example-
2 4
RRLLLL

According to your code, by finding abs(x max) it is 2, so it should be safe, but actually it isn’t-

Let me try and draw a picture here-
1 | 2 | 3 | 4 |

Now, if lets start at each position and see, whether the robot can be safe or not-
Block 1, the left limit runs out of bounds.
Block 2, the left limit runs out of bounds.
Block 3, the right limit runs out of bounds.
Block 4, the right limit runs out of bounds.

So, the answer should be “unsafe” but by calculating it your way, ie. calculating the extreme right and left limits is the wrong approach here.
Here what you are doing is, you are considering yourself to be in the middle, of a 2x grid, ie. with m columns on both right and left.
Even for this command, your code gives “safe”- RRRLLLLLL, but we all know that’s wrong.

Editorial-

In addition, there is an O(|s|) time solution that considers the maximum distance the robot travels up, down, right, and left from the original point. This avoids simulating from every starting grid square, since we know that the simulation will look very similar for those starting squares. Please look at the setter’s solution for more details.

See, it mentions maximum distance and not displacement, which you are calculating. Physics.

EDIT: What you are doing is calculating displacement and checking it for two different blocks, for right displacement, you are taking into consideration block 1 and for left displacement you are talking into consideration block 4, and merging the answers. This approach is write if a specific block is given, since we know what lies to it’s left and what lies to it’s right, but not here.

1 Like
11

So nice of you dear!!

12

You’re code checks for only one possible position ie x=0,y=0
You need to check for all pos from x>=0 to x=0 to y<m

13

What is original position of robot???

14 
#include <bits/stdc++.h>
#define ll long long int
#define N 1000000
#define M 1000000007
#define f(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define po pop_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define cot cout.tie(0)//solved by abhijay mitra in time O(nms)
using namespace std;int v[N];
#define watch(x) cout << (#x) << " is " << (x) << endl
int main()
{
    ibs,cti;
    int t;cin>>t;ll n,m;string s;ll x=0,y=0;bool chekc=0;
    while(t--){
        cin>>n>>m>>s;ll up=0,down=0,left=0,right=0;
            for (int j = 0; j < n; ++j)
            {
                for (int k = 0; k < m; ++k)
                {
                    y=j;x=k;chekc=0;
                    for (int i = 0; i < s.length(); ++i){
                        if (s[i]=='L')
                            x--;
                        if (s[i]=='R')
                            x++;
                        if (s[i]=='U')
                            y--;
                        if (s[i]=='D')
                            y++;
                        if (x==m or y==n or x+1==0 or y+1==0)
                            break;
                    }
                    if (x<m and y<n and x+1>0 and y+1>0)
                    {
                        chekc=1; cout<<"safe\n";break;
                    }
                }
                if (chekc==1)
                {
                    break;
                }
            }
            if (chekc==0)
            {
                cout<<"unsafe\n";
            }
            
    }
    return 0;
}

AC in c++