×

# ROBOTG - Editorial

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

Easy

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:

This question is marked "community wiki".

7★lg5293
511213
accept rate: 10%

15.2k347484504

 3 If you'd like test cases, you can find them here: input: http://pastebin.com/YVyGVLj1 output: http://pastebin.com/Am4cJnwp answered 20 Mar, 03:26 7★lg5293 511●2●13 accept rate: 10% So nice of you dear!! (20 Mar, 10:37) vijju1234★
 0 please explain the logic with code answered 20 Mar, 01:51 2★vivek96 517●1●7 accept rate: 7%
 0 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 answered 20 Mar, 02:49 1 accept rate: 0%

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;


}

1
accept rate: 0%

 0 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?? code answered 20 Mar, 10:24 16●1 accept rate: 33% 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

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

2★arish_10
1
accept rate: 0%

 0 Thanks a lot for sharing the test case. answered 21 Mar, 20:07 0★atntdev 1 accept rate: 0%

# include <string>

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;


}

1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×10,708
×2,509
×361
×65
×54
×8