getting TLE

general
, , , ,
1

Was trying https://www.codechef.com/problems/ROBOTG

sbumitted the following code and got TLE:

//#define DEBUG       //comment when you have to disable all debug macros.
//#define LOCAL     //uncomment for testing from local file
#define NDEBUG    //comment when all assert statements have to be enabled.
#include <iostream>
#include <cstring>
#include <sstream>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <climits>
#include <ctime>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <sys/time.h>
#include <iomanip>
#include <cstdarg>
#include <utility> //std::pair
#include <cassert>
 
#define fd(i,a) for(i=1;i<=a;i++)
#define fa(i,a,b) for(i=a;i<=b;i++)
#define fs(i,a,b,c) for(i=a;i<=b;i+=c)
#define tr(c,i) for(typeof(c.begin()) i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define all(x) x.begin(), x.end()
#define clr(x,y) memset(x,y,sizeof x)
#define log2(x) (log(x)/log(2))
#define ARRAY_SIZE(arr) (1[&arr]-arr)      
#define INDEX(arr,elem)        (lower_bound(all(arr),elem)-arr.begin())
#define equals(a,b) (a.compareTo(b)==0)    //for strings only
template<class P, class Q> inline void smin(P &a, Q b) { if (b < a) a = b; }
template<class P, class Q> inline void smax(P &a, Q b) { if (a < b) a = b; }
 
#define pb push_back
#define mp make_pair
#define lld long long int
#define MOD 1000000007
#define gcd __gcd
 
using namespace std;
 
#ifdef DEBUG
#define debug(args...)            {dbg,args; cerr<<endl;}
#else
#define debug(args...)              // Just strip off all debug tokens
#endif
 
struct debugger
{
  template<typename T> debugger& operator , (const T& v)
  {    
    cerr<<v<<" ";    
    return *this;    
  }
 
}dbg;
 
template<class T>
inline void inputInt(T &n )
{
  n=0;
 
  T ch=getchar_unlocked();
  /*int sign=1;
    while(( ch < '0' || ch > '9') && ch!='-')
    ch=getchar_unlocked();
    if(ch=='-')
    {
    sign=-1;
    ch=getchar_unlocked();
    }
    while(  ch >= '0' && ch <= '9' )
    n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
    n*=sign;*/
  while( ch < '0' || ch > '9')
    ch=getchar_unlocked();
  while(  ch >= '0' && ch <= '9' )
    n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
}

inline void inputStr(string &str){
  str="";
  char ch = getchar_unlocked();
  debug(ch);
  int i=0;
  while(ch<33){ch=getchar_unlocked();}
  while(ch!='\n'){str+=ch;ch=getchar_unlocked();}
}


int main()
{
#ifdef LOCAL
  freopen("input.in","r",stdin);
#endif
  int T,n,m;
  string s;
  inputInt(T);
  while(T--){
    inputInt(n);
    inputInt(m);
    inputStr(s);
    int len = s.length(), L,U,R,D, h=0, v=0;
    debug("yo",s);
    bool safe=true;
    L=U=R=D=0;
    for(int i=0;i<len;i++){
      if(s[i]=='L')h--;
      else if(s[i]=='R')h++;
      else if(s[i]=='U')v++;
      else v--;
      if(h<0 && abs(h)>L)L=abs(h);
      else if(h>0 && abs(h)>R)R=abs(h);
      if(v<0 && abs(v)>D)D=abs(v);
      else if(v>0 && abs(v)>U)U=abs(v);
      debug(h,v,L,R,U,D,m,n);
      if(L+R>=m || U+D>=n){
        safe=false;
        break;
      }
    }
    printf("%s\n",safe?"safe":"unsafe");
  }
}

when i accepted input from cin, it worked fine. Why is it getting stuck.

1 Like
2

I changed your

inputInt(n);
inputInt(m);
inputStr(s);

to

 cin>>n>>m>>s;

and it’s running.

And I got AC: solution

It’s also compiling on ideone.com here’s the link: http://ideone.com/Tzu9d8

1 Like
3

The problem is in the function where you are reading a string.When I changed that to cin,it worked.So there is a problem in the function that reads the string.Here is your AC code after changing that string reading function.Here

4

enter code here
#define gc getchar_unlocked
int read_int() {
char c = gc();
while(c<‘0’ || c>‘9’) c = gc();
int ret = 0;
while(c>=‘0’ && c<=‘9’) {
ret = 10 * ret + c - 48;
c = gc();
}
return ret;
}
This would work. And please refer to link and this link.
This will help you. Thanks.

1 Like
5

n = (n<<3)+(n<<1) + ch-‘0’, ch=getchar_unlocked(); This line has an error according to me. Semicolon is missing between two statements before the assignment of ch

6

that’s exactly what i said :stuck_out_tongue: I want to know what’s the problem with the readInt functions

1 Like
7

Wait a minute, did you actually create YOUR OWN input output functions to take input output?

WHY?

The TLE is not hard to guess actually.

There are 1000 test cases. Each test case has 2 integers with 1-2 digits, and a string with 1-10 characters which you are reading one by one.

In worst case it is-

1000 x 4 x 10 = 4 x 10^5 operations, just for input. And that’s a crude number because I assumed inputInt as a single instruction, while it easily has more than 10 operations. And if similar holds for input str as well, then I feel you consumed ~10^7 instructions out of M x 10^8 JUST for input.

And after that the main program starts. Each test case, a loop upto 10 characters of string, maintaining 4 variables etc. You can say that your input eats up a LOT of time.

Its actually no surprise that it gets a TLE. Try to check other fast input-output methods if you are looking for that optimisation.

Links-

Geek for geek- Fast I/O

Codechef discussion (I think this one should answer some of your follow-up Q)

8

The problem is in the function of inputStr(). It’s formatted wrongly that leads to TLE for big test cases. Therefore i just modified only this inputStr() function and after that it give AC in 0.0 sec. See this modified code.

1 Like