You are not logged in. Please login at www.codechef.com to post your questions!

×

ROBOTG - Editorial

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

This question is marked "community wiki".

asked 19 Mar, 20:09

lg5293's gravatar image

7★lg5293
511212
accept rate: 10%

edited 20 Mar, 00:23

admin's gravatar image

0★admin ♦♦
14.6k347483502


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

link

answered 20 Mar, 03:26

lg5293's gravatar image

7★lg5293
511212
accept rate: 10%

So nice of you dear!!

(20 Mar, 10:37) vijju1233★

please explain the logic with code

link

answered 20 Mar, 01:51

vivek96's gravatar image

2★vivek96
3797
accept rate: 9%

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

link

answered 20 Mar, 02:49

bvkprasad's gravatar image

0★bvkprasad
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;

}

link

answered 20 Mar, 06:44

amartya_k's gravatar image

2★amartya_k
1
accept rate: 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

link

answered 20 Mar, 10:24

includebits's gravatar image

2★includebits
161
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<n and="" y="">=0 to y<m

(20 Mar, 14:10) neilit19923★

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 ?

link

answered 20 Mar, 13:18

arish_10's gravatar image

2★arish_10
1
accept rate: 0%

Thanks a lot for sharing the test case.

link

answered 21 Mar, 20:07

atntdev's gravatar image

0★atntdev
1
accept rate: 0%

include <iostream>

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;

}

link

answered 24 Mar, 13:21

sanketsaxena's gravatar image

3★sanketsaxena
1
accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

Tags:

×10,054
×2,191
×328
×63
×54
×8

Asked: 19 Mar, 20:09

Seen: 945 times

Last updated: 24 Mar, 13:21