I think the announcement with the correction screwed the statement up, and that it should actually be 1 \leq X \leq C and 1 \leq Y \leq R.
https://www.codechef.com/viewsolution/38265742
can you help me with this solution, giving wrong answer only on 1st subtask, which i think should be correct
Too badā¦It is still a very nice problem. Kudos to the author.
Same thing happened with me. It looks like for the first subtask r and c are swapped.
My AC submission Link where I swapped r and c for first subtask
you cannot uniquely determine this way, if obstacle is at (1,3) or (2,2) final position would be same
though it worked but whats the need , without it also its coming(as per my dry run)!
thanks anyway
Also possible to solve this in O(rc)
There is a way of finding the correct answer with circular traverseā¦ just a small iteration in the path during the turnsā¦
you have to take turns like I have shown in the complete processā¦ 1st four are shown in the image and the rest should be similar to them. This will ensure that whenever you encounter the obstacle in the course these turns will ensure you will always be stuck on it and the final position will always be next to the obstacle. I will hardly take around 500 moves for the given constrains. Try it on a testcase and you will see by yourself how it works.
My solution link using same method : https://www.codechef.com/viewsolution/38214091
(please ignore the extra functions and variables I forgot to remove in solution)
firstly I am not getting how will it be stuck , second how were you able to think this in such short time ???!!! Amazing
That makes sense. Thanks for sharing!
My Solution was āRā + 20*āUā
Can you please mention the time the announcement was made or when the changes in the problem took place, as I guess for Sub task 1, my solution should give AC.
Thanks in advance.
Great approach !!! Thankyou for sharing. Can you please elaborate a little, itās hard to understand.
Very cool solution, love it
Sme here, i worked upon the solution for few hours , but when i switched r,c it got AC. lol
Something is seriously wrong with the announcement. For subtask 1, the answer whould be āRā + 20*āUā, post announcement and āUā + 20*āRā pre announcement (i learnt this from the discussion so far). So i tried swapping r and c and voila!! it passed all test cases. A wonderful problem completely spoiled by the admin (or whoever that is responsible for the announcement).
Beautiful
one doubtā¦
what if the obstacle is present in ( 1 , 1 ) ? in that case the robot is not stucking.
I think the starting will be like ( 0 , 0 ) --> ( 0 , 1 ) --> ( 1 , 1 ).
Or, am I understanding it wrong ?
Ok got it , this will also give us a unique ending point
That also perfectly fineā¦ We donāt need to minimize the sequence.
I understood approach Mani Tyagi explained in the youtube video of solving problem, but just one doubt since we want smallest possible answer string and after first iteration(i.e. after all Uās and Dās when we figured out row of the obstacle) why can we move up to that row (i.e. (R+1)* U) and then perform Lās and Rās move in that row itself(coz that is the obstacle row) to get column also.
In this way our string length will be reduced.
My ans for the approach is -
for i in C{
for j in R: move up
for j in R :move down
move right
}
//move up to the obstacle row
for i in R+1:
move up
// Just move left and right in the obstacle row only to get column
for i in C:
move left
for i in C:
move right
Please review this pseudo code.