Why this is not working?

help
1

problem code : CENS20G
#include
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
string s;
cin>>s;

    long x1,x2,y1,y2,d1,d2,c=0,cx1,cy1;
    cin>>cx1>>cy1;
    
    int q;
    cin>>q;
    while(q--)
    {
        x1=cx1;
        y1=cy1;
       cin>>x2>>y2;
       for(int i=0;i<s.length();i++)
       {
           if(x1<x2&&s[i]=='R')
           {
               x1++;
               c++;
           }
           if(x1>x2&&s[i]=='L')
           {
               x1--;
               c++;
           }
           if(y1<y2&&s[i]=='U')
           {
               y1++;
               c++;
           }
           if(y1>y2&&s[i]=='D')
           {
               y1--;
               c++;
           }
           
       }
       if(x1==x2&&y1==y2)
       cout<<"YES "<<c;
       else
       cout<<"NO";
       cout<<endl;
    }
    
}
return 0;

}

2

  1. This algorithm is O(T*N), where N is the upper bound on the string length. This is something you cannot afford to do.
    The solution is to get a count of the number of ‘R’, ‘L’, ‘U’, ‘D’ and store it. Now, each query can be answered in O(1) time. For example, if (x1,y1)=(0,0) and (x2,y2) = (-3,4), then it is necessary and sufficient to check whether there are at least 3 'L’s and 4 'U’s in the string (for which you can simply check the count instead of iterating over the string).

  2. If it still gives a TLE, then you need to include

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

inside int main().

3

Congrats on the win, btw.

1 Like