TLE problem with O(1) time complexity solution

general
, ,
1

This is my solution -


[1] for the problem [TR][2] of contest Encoding Feb'19
the solution is giving  TLE verdict for O(1) complexity and O(T) total complexity.
can anyone tell me the reason?
Thank you!


  [1]: https://www.codechef.com/viewsolution/23273030
  [2]: https://www.codechef.com/ENFE2019/problems/TR
1 Like
2

The range of test cases is from 1 to 10^9! It’s almost impossible to scan that much and give output in 1 second.

But in this case you just have use fast i/o to take the input. This worked in my case.

3

You could use this simple fast i/o template using cin and cout. See my code for an example https://www.codechef.com/viewsolution/23279921

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
1 Like
4

what is faster than scanf and prinf in c, c++?

5

cin cout after adding few lines of code

1 Like
6

Thnks, xD btw post is two month old and now i know about FAST I/O.

2 Likes
7

Or use O(1/N) algorithm :slight_smile: :stuck_out_tongue:

2 Likes
8

Waiting for a day , when i will find the problem with constraints 100^10000 and looking at your O(1/N) algorithm on that :stuck_out_tongue_winking_eye:

and at that time we all are begging from authors to increase constraints. XD

2 Likes
9

Weird!! Java is supposed to twice slower than c++ but for this ques
my java soln passed in 0.46 sec
whereas c++ took 0.80 sec

Both uses probably fastest io available for them and have exactly same structure
C++ CodeChef: Practical coding for everyone
Java CodeChef: Practical coding for everyone

10

@ganesh92
Here is little optimized solution
CodeChef: Practical coding for everyone (0.62 secs)
I think there is one more fast i/o in c++…
CodeChef: Practical coding for everyone (0.13)
So now Java solution takes more than 3.5 times time :smiley:

1 Like
11

what is this? :no_mouth::no_mouth: please eloborate what you have done.

12

Just implemented own input output functions…
Actually I am not the one who own this code… it’s copied from somewhere :wink:

13

i know that … but i am asking how and why this I/O working so fast.
if feeling lazy :sleepy: . You can also share the link of your resource …

14

Idk the exact reason… I can try finding it out though… Will ping here if I get the reason…
I have copied it from here :
https://www.codechef.com/viewsolution/1553773

2 Likes
15

Nice one @l_returns
actually 3.5 times is still normal . Java is actually notorious for having slow IO.
Unfortunately this problem is pushing IO operations to its limit
It happened to me many times that my c++ solutions passes whereas java does not
But i guess we both agree that we had used esoteric implementations to achieve these results :stuck_out_tongue_closed_eyes:

2 Likes
16

wanted to make it normal only :slight_smile:
Agree :smiley: