PROBLEM LINK:
Author & Editorialist: Sarthak Shukla
DIFFICULTY:
SIMPLE
PREREQUISITES:
Basic Maths
PROBLEM:
Given a string of operations and starting co-ordinates in the infinite plane. Operations are R-right, L-left, U-up, and D-down. For Q queries, ending coordinates are given. Find whether it is possible to move from starting point to ending point by choosing some subsequence of operations. If "YES" find the smallest possible length of subsequence.
EXPLANATION:
It’s quite clear that we can’t loop through the string for each query.
There is a very simple observation to process queries in O(1) time.
Let’s take an example.
Suppose a given string is “RLUDRLUD” and the starting point is (0,0). Now, we have to find the length of the smallest subsequence of string to move from (0,0) to (2,2). It can be clearly seen that to move from (0,0) to (2,2), we require two R’s and two U’s.
Two ‘R’ require to move right to (2,0), and two ‘U’ requires, to move up to (2,2). Sequence in which characters occur doesn’t matter as it is always possible to move from (0,0) to (2,2) using "RRUU", "RURU", "RUUR", "URUR", "UURR", "URRU".
Now, for smallest subsequence it is already explained above. It can be easily proven that to move from (x_1,y_1) to (x_2,y_2) minimum possible operations required are x_2 - x_1 (requires ‘R’ if positive else ‘L’) and y_2 - y_1 (requires ‘U’ if positive else ‘D’).
And, since we have to find the lengh of smallest possible subsequence it will always be abs(x_2-x_1)+abs(y_2-y_1).
Hence, just preprocess the string to store the count of R, U, L, and D. Answer the queries if the requirement is satisfied by the values of the count.
And, if this requirement is not satisfied by the given string, the answer will be "NO".
TIME COMPLEXITY:
Time: O(|S| + Q)
Space: O(1)
SOLUTIONS:
C++ Code
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int main()
{
fast
int t;
cin>>t;
while(t--) {
string oper;
cin>>oper;
long long x1,y1;
cin>>x1>>y1;
long long countL=0, countR=0, countU=0, countD=0;
for(char ch:oper) {
if(ch == 'L') countL++;
else if(ch == 'R') countR++;
else if(ch == 'U') countU++;
else countD++;
}
long long q;
cin>>q;
while(q--) {
long long x2,y2;
cin>>x2>>y2;
long long reqX = (x2-x1);
long long reqY = (y2-y1);
bool satX=false, satY=false;
if(reqX > 0) {
if(reqX <= countR)
satX = true;
}
else if(reqX < 0) {
if(abs(reqX) <= countL)
satX = true;
}
else
satX=true;
if(reqY > 0) {
if(reqY <= countU)
satY = true;
}
else if(reqY < 0) {
if(abs(reqY) <= countD)
satY = true;
}
else
satY=true;
if(satX && satY) {
cout<<"YES "<<abs(reqX) + abs(reqY)<<"\n";
}
else
cout<<"NO\n";
}
}
}
Python Code
import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
s = input()
ans = []
totl, totr, totu, totd = 0, 0, 0, 0
for x in s:
if x == 'L':
totl += 1
elif x == 'R':
totr += 1
elif x == 'U':
totu += 1
else:
totd += 1
x, y = map(int, sys.stdin.readline().strip().split())
q = int(sys.stdin.readline().strip())
for __ in range(q):
flag = 0
l, r = map(int, sys.stdin.readline().strip().split())
dx = l-x
dy = r-y
if l < x and totl < abs(dx):
flag = 1
if l > x and totr < abs(dx):
flag = 1
if r < y and totd < abs(dy):
flag = 1
if r > y and totu < abs(dy):
flag = 1
if flag == 1:
ans += ["NO"]
else:
ans += ["YES", abs(dx)+abs(dy)]
print(*ans, sep='\n')