You are not logged in. Please login at www.codechef.com to post your questions!

×

getting TLE

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.

asked 04 Apr '17, 23:55

sudeepdino008's gravatar image

3★sudeepdino008
10416
accept rate: 0%


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

link

answered 05 Apr '17, 00:39

only4's gravatar image

4★only4
1.5k212
accept rate: 17%

edited 05 Apr '17, 01:02

1

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

(05 Apr '17, 11:21) sudeepdino0083★
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.

link

answered 05 Apr '17, 10:37

akshaym_96's gravatar image

3★akshaym_96
1506
accept rate: 13%

edited 05 Apr '17, 10:37

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

(05 Apr '17, 10:40) akshaym_963★

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.

link

answered 05 Apr '17, 14:41

bansal1232's gravatar image

5★bansal1232
2.8k1419
accept rate: 16%

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

link

answered 05 Apr '17, 00:48

naksh9619's gravatar image

4★naksh9619
6196
accept rate: 12%

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)

link

answered 05 Apr '17, 11:52

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 05 Apr '17, 12:09

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,911
×720
×169
×61
×39

question asked: 04 Apr '17, 23:55

question was seen: 803 times

last updated: 05 Apr '17, 14:41