S04E23 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Jayesh Shaw
Tester: Nishant Shah, Divyansh Tyagi
Editorialist: Rohan Ray

DIFFICULTY

Easy

PREREQUISITES

None

PROBLEM

Given the coordinates of a point in a 2-D grid and a string of instructions of type:

  • S[i] = ‘0’ : Change the direction of movement, and move 1 unit in either direction
  • S[i] = ‘1’ : Move 1 unit in either direction

You need to determine if it is possible to reach the point from origin after following all the given instructions.

EXPLANATION

Observation 1: Taking the absolute values of our destination point, will not affect our answer.

Proof

To get the answer for the original coordinates, if they are negative, we can just reverse the direction of our movement in that particular axis.

Observation 2: If the difference between the respective coordinates of the destination and our final point is even, then it is always possible to reach the destination otherwise not.

Proof

Let’s say we wanted to reach (P, Q) instead we reached (X, Y) and let’s say for simplicity that the difference between X and P is even and Y=Q. Then, if we reverse the direction of exactly$ (X-P) / 2 $steps along the X-axis, we will reach our destination.

For simplicity, we will first take absolute values of the coordinates of the destination point. Then we will always move in a positive direction in the respective axis while following the instructions.

First we assume that we start by facing the X direction, and follow the instructions. At the end of instructions, we will use the second observation to determine if we can reach our destination point or not.

Then, we repeat the same steps with the assumption that we start by facing the Y direction.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n, p, q;
string s;

bool solve()
{
	    cin>>n>>p>>q;
    cin>>s;
    p = abs(p);
    q = abs(q);

    int x = 0, y= 0;
    int curr = 0;

    rep(s.length()){
    	if(s[i] == '1'){
    	    if(curr == 0) x ++;
    	    else y++;
	    }else{
    	    curr^=1;
    	    if(curr == 0) x ++;
    	    else y++;
	    }
    }




    if(x>=p && y >=q && (x-p)%2 ==0 && (y-q)%2 == 0) return true;


    x = 0;
    y = 0;
    curr = 1;

    rep(s.length()){
	    if(s[i] == '1'){
        	    if(curr == 0) x ++;
    	    else y++;
	    }else{
    	    curr^=1;
    	    if(curr == 0) x ++;
    	    else y++;
	    }
    }

    if(x>=p && y >=q && (x-p)%2 ==0 && (y-q)%2 == 0) return true;

    return false;


}

int32_t main()
{



    sync;
    int t = 1;
    cin>>t;
    while(t--){
	    if(solve()){
    	    cout<<"YES";
	    }
	    else{
    	    cout<<"NO";
	    }
	    cout<<"\n";
    }
    return 0;
}

can someone help me to find my bug ig my code is right

Please elaborate on Observation 2.

4 Likes

yep, once we have executed the instructions, according to the question, we need to check whether he has reached (p,q) or not.
why do we need to check for any possibility of reaching the destination even after the string is traversed?

1 Like

Ugh. Here you are using the word “direction” twice in the same sentence for two very different things. If the problem statement was written this way (thankfully it wasn’t!), then nobody would be able to understand what’s going on and what needs to be done.

Oh, wait … You are actually the author of a different “The One with All the Candy” problem from the same contest. Which turned out to be super confusing. Now this explains everything.

1 Like
/*
Much intiutive solution 
 */

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define endl "\n"
#define ll long long
#define vt vector<ll>
#define vvt vector<vt>
#define vvvt vector<vvt>
#define all(c) (c).begin(), (c).end()
#define rep(i, start, end) for(ll i=start; i<=end; i++)
#define sd(n) scanf("%lld",&n)
#define eps 1e-3
const ll mod=1e9+7;
const ll maxs=1e5+5;
#define c(x) ll x;cin>>x
#define cc(x,y) ll x,y;cin>>x>>y
#define ccc(x,y,z) ll x,y,z; cin>>x>>y>>z
#define bitc  __builtin_popcountll
#define fast cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
typedef unsigned long long ull;
typedef long double lld;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
ll add(ll x,ll y ){ll res=x+y;return (res>=mod?res-mod:res);}
ll sub(ll x,ll y ){ll res=x-y;return (res<=0?res+mod:res);}
ll binpow(long long a, long long b) {a %= mod;long long res = 1;while (b > 0) {if (b & 1)res = res * a % mod;a = a * a % mod;b >>= 1;}return res;}
ll mul(ll x,ll y){ll res=x*y;return(res>=mod?res%mod:res);}
ll inv(ll x){return binpow(x,mod-2);}
template<class T>ll size(T &a){return a.size();}
template<class T>void read(vector<T> &a){for(ll i=0;i<size(a);i++)cin>>a[i];}
ll ceil2(ll a, ll b) { if (a == 0) return 0;return (a +b-1)/b ;}
inline ll maxim(ll a,ll b) {if(a>b) return a; else return b;}
inline ll minim(ll a,ll b) {if(a<b) return a; else return b;}
inline bool equals(double a, double b){ return fabs(a - b) < 1e-9; }
ll gcd(ll a, ll b) { return b==0 ? a : gcd(b, a%b); }
ll 	pow2(int i) 		{ return 1LL << i; }
int topbit(signed t) 	{ return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(ll t) 		{ return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int lowbit(signed a) 	{ return a == 0 ? 32 : __builtin_ctz(a); }
int lowbit(ll a) 		{ return a == 0 ? 64 : __builtin_ctzll(a); }
ll  allbit(ll n) 		{ return (1LL << n) - 1; }
int popcount(signed t) 	{ return __builtin_popcount(t); }
int popcount(ll t) 		{ return __builtin_popcountll(t); }
bool ispow2(int i) 		{ return i && (i & -i) == i; }
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;}
#ifndef SEGMENTTREE_H
#define SEGMENTTREE_H
#define left(i) (2*i + 1)
#define right(i) (2*i + 2)
#define parent(i) ((i-1)/2)
//Use the below if u use unordered map iy increases the time complexity
//mp.reserve(1024);
//mp.max_load_factor(0.25);
template<class T>
class SegmentTree
{
    public:
        //tree constructors.
        SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
        SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
        
        //query the range l to r, 0 based array indexing.
        T query(int l, int r);
        
        //update the element at index idx to val.
        void update(int idx, T val);
        ///TODO lazy propagation
    private:
        //represents the segment tree.
        T *tree;
    
        //builds the segment tree.
        void buildTree(std::vector<T> data);
        
        //size of the segment tree array.
        int segTreeSize;
    
        //extra nodes must be added to array to make its size a power of 2
        //this is the value to be filled for the those nodes.
        T valueForExtraNodes;
    
        //specifies how to combine child node results to form parent node result.
        T (*combine)(T obj1, T obj2);
    
        //used to calculate the size of array needed to store the tree.
        int calculateSize(int n);
    
        //helps to solve a range query.
        T queryHelper(int l,int r, int st, int ed, int node);
};

template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
                                                T value, T (*combine)(T obj1, T obj2))
{
   this->combine = combine;
   valueForExtraNodes = value;
   segTreeSize = calculateSize(data.size());
   buildTree(data);
}

template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
                                            T value, T (*combine)(T obj1, T obj2))
{
   this->combine = combine;
   valueForExtraNodes = value;
   segTreeSize = calculateSize(n);

   std::vector<T> data;
   for(int i = 0; i < n; i++)
         data.push_back(ar[i]);

   buildTree(data);
}


template<class T> int SegmentTree<T>::calculateSize(int n)
{
    int pow2 = 1;
    while( pow2 < n)
    {
        pow2 = pow2 << 1;
    }
    return 2*pow2 - 1;
}

template<class T> T SegmentTree<T>::query(int l, int r)
{
    int st = 0, ed = segTreeSize/2;
    return queryHelper(l, r, st, ed, 0);
}

template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
{
    if( (r < st) || (l > ed) || (l > r) )
        return valueForExtraNodes;
    if(st >= l && ed <= r)
        return tree[node];
    T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
    T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
    return combine(leftVal, rightVal);
}

template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
{
   int n = data.size();
   tree = new T[segTreeSize];
   int extraNodes = (segTreeSize/2 + 1) - n;
   for(int i = segTreeSize - 1; i >= 0; i--)
   {
       if(extraNodes>0)
           {
               tree[i] = valueForExtraNodes;
               extraNodes--;
           }
       else if(n>0)
           {
               tree[i] = data[n-1];
               n--;
           }
       else
           tree[i] = combine(tree[left(i)], tree[right(i)]);
   }
}

template<class T> void SegmentTree<T>::update(int idx, T val)
{
    int segTreeIdx = (segTreeSize/2) + idx;
    tree[segTreeIdx] = val;
    while(parent(segTreeIdx) >= 0)
    {
        segTreeIdx = parent(segTreeIdx);
        if(right(segTreeIdx) < segTreeSize)
          tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
        if(segTreeIdx == 0)
            break;
    }
}

#endif // SEGMENTTREE_H
vt primes(ll n){
  bool prime[n+1];
  vt p;
  fill_n(prime,n+1,true);
    for(int i=2;i*i<=n;i++){
        if(prime[i]==true)
        {
            for(int j=i*i;j<=n;j+=i){
                    prime[j]=false;
            }
        }
    }
    for(int j=2;j<=n;j++){
      if(prime[j])
         p.pb(j);
    }
    return p;
}
const int N=1000007;
int phi[N+1];
void etf(){
 int n = N;
    phi[0] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        phi[i] = i;
    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) {
            for (int j = i; j <= n; j += i)
                phi[j] -= phi[j] / i;
        }
    }
}
vector<vector<int>> f(N);
void factors(){
    for(int i=1;i<N;i++){
       for(int j=i;j<N;j+=i){
          f[j].push_back(i);
       }
    }
}
  
vt prime_factors(ll n){
  vt p;
  for(ll i=2;i*i<=n;i++){
        while(n%i==0){
        p.pb(i);
        n/=i;
        }
    }
     if(n>1){
        p.push_back(n);
     }
  return p;
}

int modInverse(int a, int m)
{
    int m0 = m;
    int y = 0, x = 1; 
    if (m == 1)
      return 0;
    while (a > 1)
    {
        // q is quotient
        int q = a / m;
        int t = m;
        // m is remainder now, process same as
        // Euclid's algo
        m = a % m, a = t;
        t = y;
        // Update y and x
        y = x - q * y;
        x = t;
    }
    // Make x positive
    if (x < 0)
       x += m0;
    return x;
}
ll fact[200010];

void compute_fact(ll modVal) {
  fact[0]=1;
  for(int i=1;i<=200004;i++) {
    fact[i]=(fact[i-1]*i)%modVal;
  }
}

ll ncr_mod(ll n,ll r,ll modVal) {
  if(r==0||n==r) return 1;
  if(n<r) return 0;
  return (((fact[n]*modInverse(fact[r],modVal))%modVal)*modInverse(fact[n-r],modVal))%modVal;
}
//long long modalt(int x,int n,int m){ if (n==0) return 1; if(n%2==0){ long long y=mod(x,n/2,)%m; return (y*y)%m;}else return ((mod(x,n-1,m)%m) *(x%m))%m;}
#define lim 400009
ull findPreviousPowerOf2(ull n)
{
    // drop all set bits from `n` except its last set bit
    if(n<3)
      return 1;
    return 1ULL << (int)log2(n);
}
ll calprod(vt r){
    ll res=1;
   for(auto p:r){
      res*=p;
   }
   return res;
}
int p,q,n;
string s;
bool cheeck(char cd){
    int cpx=0,cpy=0;
    for(int i=0;i<n;i++){
     if(s[i]=='0' and cd=='x'){
          if(q<cpy){
              cpy--;
          }
          else{
              cpy++;
          }
          cd='y';
     }
     else if(s[i]=='0' and cd=='y'){
             if(p<cpx){
              cpx--;
          }
          else{
              cpx++;
          }
          cd='x';
     }
     else if(s[i]=='1'){
         if(cd=='x'){
             if(p<cpx)
              cpx--;
            else
              cpx++;
         }
         else{
             if(q<cpy)
              cpy--;
          else
              cpy++;
         }
     }
  }
  if(cpx==p and cpy==q){
      return true;
  }
  else{
      return false;
  }
}
void solve(){
  cin>>n>>p>>q;
  cin>>s;
  if(cheeck('x') or cheeck('y')){
      cout<<"YES"<<endl;
  }
  else{
          cout<<"NO"<<endl;
  }
}
int main(){
  fast;
  cout<<setprecision(6)<<fixed;
	int t;
	cin>>t;
	while(t--){
		solve();
	}
return 0;
}