Problem Link
Ramandeep Robot
Setter: Ayush Kumar
Tester: Ramandeep Singh
Editorialist: Ayush Kumar
Difficulty
Easy
Problem
Ramandeep being a robotics enthusiast, came up with the following description of a robot and developed it:
The robot is on a 2D plane and starts at origin (0,0) and follows instructions given to it in the form of a string. The instructions consist only of L (Left), R (Right), U (Up), D (Down), and A (Again) are given in the form of a string S.
Let it’s coordinate by (x, y) at some moment. Then the instruction L (left) would change coordinates to (x − 1, y), R (right) would change coordinates to (x + 1, y), U (up) would change coordinates to (x, y + 1), and D (down) would change coordinates to (x, y − 1).
Before executing instructions, the robot makes some replacements. In one replacement, it replaces the leftmost A with the prefix string up to that A. Formally, if the current string is S and Si = A and Sj ≠ A for all j < i, the robot replaces Si with S1, S2, …Si − 1.
It performs replacements as long as there is at least one A left in the string.
For example, let the instruction be RUAA. Then,
RUAA → RURUA (First A replaced) → RURURURU (Second A replaced) would be final string.
To verify whether his robot was working correctly or not, he wanted to find the final coordinates of the robot after executing all the instructions. Help Ramandeep in accomplishing this task.
In the above case, the final coordinate would be (4,4).
Assume that plane extends infinitely in all directions.
Explanation
Let’s x and y represent the changes made till now in x and y direction respectively. While Traversing the input string, for characters U, D, L and R, it’s quite simple. You simply need to either add 1 or subtract 1 from x or y depending upon the direction. For case when you encounter A, you need to repeat what you have done before. Naïve approach can be to simply recur from start and calculate again till the current index. But if you closely observe, you will notice that you need to repeat what you have done till now. So instead of going back to start you can simply multiply x and y with 2 because basically x and y are storing the changes in x and y direction happened till now and you need to simply double the changes.
Time Complexity
O(n) per testcase
Solution
// c++
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
ll x=0,y=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='A')
{
x += x;
y += y;
}
else if(s[i]=='L'){
x-=1;
}
else if(s[i]=='R'){
x+=1;
}
else if(s[i]=='U'){
y+=1;
}
else if(s[i]=='D'){
y-=1;
}
}
cout<<x<<" "<<y<<"\n";
}
int main()
{
int t;
cin>>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}