×

# Getting WA for Safe Robot asked in March CookOff 17

 0 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 #include #include #include #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;iymax) { p=1; cout << "unsafe" << endl; break; } if(p!=1) { if(k2xmax) { 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.! asked 01 Apr '17, 19:09 171●1●7 accept rate: 5%

 1 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 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. answered 01 Apr '17, 19:34 15.5k●1●20●66 accept rate: 18% 1 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? (01 Apr '17, 19:58) 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. (01 Apr '17, 20:44)
 2 try this test case: 1 5 1 UUDDDDD there's no safe position while your code prints "safe". answered 01 Apr '17, 19:29 30●3 accept rate: 0% Thank you for pointing that out. (01 Apr '17, 19:56)
 1 Yes,there is a problem with some conditions answered 01 Apr '17, 19:41 904●11 accept rate: 9% 1 I was also not able to solve it....at last I saw solution. (01 Apr '17, 19:41) I had to make a thread requesting for help. This was a nice problem in terms of approach and clever thinking. (01 Apr '17, 19:45)
 0 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). answered 01 Apr '17, 19:29 171●1●7 accept rate: 5%
 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:

×1,919
×569
×65
×54
×9

question asked: 01 Apr '17, 19:09

question was seen: 409 times

last updated: 01 Apr '17, 20:47