Getting WA for Safe Robot asked in March CookOff 17

general
, , , ,
1

Problem Link:- https://www.codechef.com/problems/ROBOTG

I am using a different approach then the one mentioned in the editorial.

Approach used:-
If I see x and y axis separately then we can calculate the minimum and maximum values that the robot can have along x and y axis. Then see if at any point the robot’s position exceeds the maximum value or gets lower than the minimum value along any axis. If it does then output unsafe otherwise safe.

Code:-

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main()
{
 int test;
cin >> test;
while(test--)
{
  int a,b;
  cin >> a >> b;
  string str;
  cin >> str;
  int xmin = 1-b;
  int xmax = b-1;
  int ymin = 1-a;
  int ymax = a-1;
  int k1 = 0,k2 = 0,p=0,q=0;
  for(int i=0;i<str.length();i++)
  {
    if(str[i]=='U')
      k1+=1;
    if(str[i]=='D')
      k1-=1;
    if(str[i]=='L')
      k2-=1;
    if(str[i]=='R')
    k2+=1;
    if(k1<ymin || k1>ymax)
    {
      p=1;
      cout << "unsafe" << endl;
      break;
    }
    if(p!=1)
    {
      if(k2<xmin || k2>xmax)
      {
        q=1;
        cout << "unsafe" << endl;
      }
    }
    if(q==1)
      break;
  }
  if (p==0 && q==0)
    cout << "safe" << endl;
}

return 0;
}

However I am getting a WA. Is there any corner case that I am not able to see. The code is passing all sample test cases.!

2

I saw all the test cases of the problem given in the editorial.

The problem with the test case
7 4
RRRLLLU (Test Case 911)

The answer given by the judge is unsafe whereas it should be safe(given correctly by my code).

3

try this test case:

1

5 1

UUDDDDD

there’s no safe position while your code prints “safe”.

2 Likes
4

This is the corner case, which gave nightmares to me too-

Input
1
3 3
LLDDRRUR
Output
safe
Expected Output
unsafe

If you see closely, we first have to move 2Lefts. Possible only if we start at the rightmost column. Then we go 2 times down. Then we go 2 times right, back to the rightmost column. Then after one Up, we go right again and fall.

This test case fails due to erroneous calculation of maximums/minimums or wrong approach to the problem.

To overcome it, don’t check at point to point if robot is safe or not. Focus on finding the maximum distance it travels in vertical and horizontal direction, and then compare them with given matrix length to find if robot falls anywhere or not.

My code

Another nice code by @meooow.

The editorial, if I interpreted it correctly, wanted us to generate all possible locations/points at which robot can be placed and then check for each and every one of them, that “if the robot is placed at this point, is it safe or not?”. Then if all points prove to be unsafe, print unsafe, else safe.

1 Like
5

Yes,there is a problem with some conditions

1 Like
6

I was also not able to solve it…at last I saw solution.

1 Like
7

I had to make a thread requesting for help. This was a nice problem in terms of approach and clever thinking.

8

Thank you for pointing that out.

9

Thank you for taking out the time to write such a detailed explanation. The problem was easy but at the same time it was more easier to mess up the logic.

But I still think that test case 911 is wrongly given unsafe in the test cases link provided in the editorial. Could you please check that out?

1 Like
10

Before I start at it, just confirming, is it

7 4
RRRLLLLU

(Cause there are many test cases there, its easy to accidently pick a wrong one. :))

If that’s the testcase, then its actually unsafe. There are 4 columns and 7 rows. Robot will start at one of the cells, so it can go at max 3 right/left and 6 up/down. But there is a segment of “LLLL” which wants it to go left 4 times a row, and this would make it fall. Make a 7x4 matrix, and start from corner cell to check it out.