PROBLEM LINK:
Author: Anik Sarker
Tester: Raja Vardhan Reddy
Editorialist: William Lin
DIFFICULTY:
Cakewalk
PREREQUISITES:
Ad-hoc
PROBLEM:
Chef starts at cell (0, 0). There is a string S containing characters ‘L’, ‘R’, ‘U’, ‘D’. The characters correspond to moves that Chef will follow. However, if there are multiple consecutive instructions to move along the same axis (left/right or up/down), he will only perform the first of these moves. Find the final cell that Chef will be on.
QUICK EXPLANATION:
Process the moves starting from the first move. After you perform a move, find the next move which moves along a different axis and skip all moves in between.
EXPLANATION:
Let’s first suppose that Chef doesn’t skip any moves. To find the final cell, we will process the moves in order and keep track of the cell (x, y) that Chef is on. This is pretty straightfoward, and the code is shown below:
int x=0, y=0;
for(int i=0; i<n; ++i) {
if(s[i]=='L')
--x;
if(s[i]=='R')
++x;
if(s[i]=='U')
++y;
if(s[i]=='D')
--y;
}
Now, let’s consider when Chef skips moves which are along the same axis. After we perform a move, the next move we should perform is the first move which is along a different axis than the move we just performed. To find the first such move after the move we just performed, we can use a while loop:
//find first move along different axis
int j=i;
//one of i and j should be left/right and the other should be up/down
while(j<n&&(s[i]=='L'||s[i]=='R')==(s[j]=='L'||s[j]=='R'))
++j;
The while loop stops when we reach the end of the array or when we find a move which is along a different axis. Lastly, we put this part into our main for loop and make some small changes:
int x=0, y=0;
for(int i=0; i<n; ) {
if(s[i]=='L')
--x;
if(s[i]=='R')
++x;
if(s[i]=='U')
++y;
if(s[i]=='D')
--y;
//find first move along different axis
int j=i;
//one of i and j should be left/right and the other should be up/down
while(j<n&&(s[i]=='L'||s[i]=='R')==(s[j]=='L'||s[j]=='R'))
++j;
//skip rest of the moves along same axis
i=j;
}
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int getID(char ch){
if(ch == 'L') return -1;
if(ch == 'R') return 1;
if(ch == 'U') return 2;
if(ch == 'D') return -2;
assert(false);
}
int main(){
int t;
scanf("%d", &t);
for(int cs=1; cs<=t; cs++){
int n;
scanf("%d",&n);
string s;
cin >> s;
int x = 0, y = 0;
for(int i=0; i<s.size(); i++){
if(i && abs(getID(s[i])) == abs(getID(s[i-1]))) continue;
if(s[i] == 'L') x--;
if(s[i] == 'R') x++;
if(s[i] == 'U') y++;
if(s[i] == 'D') y--;
}
printf("%d %d\n", x, y);
}
}
Tester's Solution
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
int x,y;
int move(char c){
if(c=='L'){
x--;
}
if(c=='U'){
y++;
}
if(c=='R'){
x++;
}
if(c=='D'){
y--;
}
}
map<char,int>mapi;
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
mapi['L']=1;
mapi['R']=1;
mapi['D']=2;
mapi['U']=2;
//t=1;
while(t--){
int n,i;
string s;
x=0;
y=0;
cin>>n;
cin>>s;
move(s[0]);
f(i,1,s.length()){
if(mapi[s[i]]!=mapi[s[i-1]]){
move(s[i]);
}
}
cout<<x<<" "<<y<<endl;
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
void solve() {
//input
cin >> n >> s;
//process instructions
int x=0, y=0;
for(int i=0; i<n; ) {
if(s[i]=='L')
--x;
if(s[i]=='R')
++x;
if(s[i]=='U')
++y;
if(s[i]=='D')
--y;
//find first move along different axis
int j=i;
//one of i and j should be left/right and the other should be up/down
while(j<n&&(s[i]=='L'||s[i]=='R')==(s[j]=='L'||s[j]=='R'))
++j;
//skip rest of the moves along same axis
i=j;
}
//output
cout << x << " " << y << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 