CENS20G - Editorial

PROBLEM LINK:

Practice
Contest

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') 
4 Likes

@saurabhshadow i had done the same thing but i got WA
https://www.codechef.com/viewsolution/36980667
can you help me to figure out what i am missing here?

Sorry brother there was just a small mistake, you printed “No” whereas “NO” was expected.

10 Likes

:disappointed_relieved: :disappointed_relieved: :disappointed_relieved:
i was wondering what’s wrong with the logic and i had not seen this typo.
thanks for mentoning @sarthak_eddy

1 Like

I did exactly same then Why I got tle???
https://www.codechef.com/viewsolution/36993429

https://www.codechef.com/viewsolution/36999823
Why this code is getting TLE?


Read this

No problem.

1 Like

i used same logic but get TLE any one help for for debug code is running on O(n) https://www.codechef.com/viewsolution/36987837

just couldn’t calculate length of substring correctly:/

yeah I used this
"ios_base::sync_with_stdio(false);
cin.tie(NULL); "

It is recommended to use cout << “\n”; instead of cout << endl;. endl is slower because it forces a flushing stream, which is usually unnecessary

3 Likes

Fast IO required.

Ohhh !!! I forget about the endl ; :cold_sweat:

Someone please help me in this why I am getting WA
https://www.codechef.com/viewsolution/36998125

Thanks for the link, i was stuck at the same issue.

It seems like the only thing that mattered was using “\n” instead of endl. I tried using

ios_base::sync_with_stdio(false);
cin.tie(NULL);

but it didn’t work until I changed endl to “\n”. Then I tried removing
ios_base::sync_with_stdio(false);
cin.tie(NULL);

and it still worked. So basically using “\n” was the only thing needed.

Also, initially I had tried submitting in Python using sys library and “\n” and that was not working either. I’m definitely not a fan of this question.

2 Likes

using scanf instead of cin will remove tle

https://www.codechef.com/viewsolution/36992280
I have done exactly the same way but i am getting WA can someone pls help…

during the contest, I visited the same page and used cin.tie… fast IO but still got TLE . now , I just replaced endl by \n and it works . wish I knew before :frowning: