PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan Jaddouh
Tester: Aleksa Plasvic
Editorialist: Taranpreet Singh
DIFFICULTY:
Cakewalk.
PREREQUISITES:
None.
PROBLEM:
Given a robot and its starting point X and N commands each being either move left or mode right, Find out the number of distinct positions visited by the robot after performing all operations.
QUICK EXPLANATION
- Start position does not affect the final answer since by choosing a different start point only the set of points differ.
- So we can simply simulate all the steps with any start point and maintain a list of visited position, adding a new position every time we enter the new position.
- To avoid negative position, we can simply choose any start point > N as within N steps, Robot cannot go to any negative position.
EXPLANATION
First thing, the start point do not affect the number of points. So, even if we change the start point, to say 0, Answer remains the same.
Now, since the number of operations is quite small, we can just simulate the operations. Let’s choose a start point, say 0. Now, we move one step to the left every time we encounter a Left command and move right every time we encounter the right command. We can just keep a set and add all the positions visited including the start position.
After executing all commands, the size of the set is the number of distinct positions visited.
In case you choose to record visited position using the boolean array, you need to take care of negative index. Taking starting point > N automatically handles that.
This solution has time as well as memory complexity O(N) and is good enough to pass. But we can reduce memory complexity to O(1) by noticing the fact that the positions visited always form a consecutive range from some min value to some max value, thus containing max-min+1 positions in the range. So, during simulation, we can just keep track of the minimum and maximum position reached and print out the number of positions, leading to memory complexity O(1).
Bonus Problems
Given robot, at a start point, X, execute following commands and print the number of distinct positions visited.
The first problem - Move y steps to direction D step by step.
Second problem - Jump y steps to direction D.
Solve both these problems and prove why your solutions are optimal (If they are :P).
Time Complexity
Time complexity is O(N) per test case.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
string s;
int n;
int main(){
//freopen("00.txt","r",stdin);
//freopen("00o.txt","w",stdout);
int x0;
T=readIntLn(1,100);
while(T--){
n=readIntSp(1,100);
x0=readIntLn(-1000000,1000000);
int mn=x0,mx=x0;
s=readStringLn(n,n);
for(int i=0;i<n;i++){
assert(s[i]=='L' || s[i]=='R');
}
for(int i=0;i<n;i++){
if(s[i]=='L'){
x0--;
} else {
x0++;
}
mn=min(mn,x0);
mx=max(mx,x0);
}
cout<<mx-mn+1<<endl;
}
assert(getchar()==-1);
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,x0;
string s;
cin>>n>>x0;
cin>>s;
int mi=0;
int mx=0;
int cur = 0;
for (int i=0;i<n;i++){
if (s[i]=='L') cur--; else
cur++;
mx = max(mx, cur);
mi = min(mi, cur);
}
cout<<mx-mi+1<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
class TSTROBOT{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), x= ni();
int min = x, max = x;
String s = n();
for(int i = 0; i< n; i++){
if(s.charAt(i)=='L')x--;
else x++;
min = Math.min(min, x);
max = Math.max(max, x);
}
pn(max-min+1);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)3e5+2;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
//Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new TSTROBOT().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new TSTROBOT().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 