ROBOTG - Editorial

lg5293 · March 19, 2017, 8:09pm

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

vivek96 · March 20, 2017, 1:51am

please explain the logic with code

bvkprasad · March 20, 2017, 2:49am

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

lg5293 · March 20, 2017, 3:26am

If you’d like test cases, you can find them here:
input:
http://pastebin.com/YVyGVLj1
output:
http://pastebin.com/Am4cJnwp

amartya_k · March 20, 2017, 6:44am

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;

}

includebits · March 20, 2017, 10:24am

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

vijju123 · March 20, 2017, 10:37am

So nice of you dear!!

arish_10 · March 20, 2017, 1:18pm

#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 ?

neilit1992 · March 20, 2017, 2:10pm

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

atntdev · March 21, 2017, 8:07pm

Thanks a lot for sharing the test case.

sanketsaxena · March 24, 2017, 1:21pm

#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;

}

shmabulock · June 16, 2017, 5:08pm

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-