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

×

how many approx loops are allowed in 2.5 sec time limit

How many approx loops can be traversed in 2.5 sec? And what should be best complexity to traverse 10^6?

asked 12 Aug '18, 18:57

ezio27's gravatar image

2★ezio27
316
accept rate: 0%

edited 03 Oct '18, 23:54


This question has already been asked multiple times at Codechef(page1, page2) and Codeforces(page1) blogs where a beautiful chart is available where you can refer. For the current codechef judge, with 10^6 limit, expect the complexity would be O(n), O(nlogn), or $\theta(nlogn)$. . .

But again, you have to consider what exactly are you trying to do inside the loops. For example, if you simply run two for loops where each loop runs for 10^9 times, so overall 10^18 times, you will be amazed how fast the codechef judge completes this loops, which is almost in no time. This is because you are doing nothing inside the loop and the compiler has actually removed those loops from the code path. However, obviously, why will you have empty loops at Codechef, which is why the above-suggested links would give rough estimates.

Best Regards,

link

answered 12 Aug '18, 19:55

utkalsinha's gravatar image

6★utkalsinha
851118
accept rate: 13%

Thanks this is helpful.

(13 Aug '18, 02:21) ezio272★

On most online judges, the number of operations is 10^8 per second. This limit is for C++. For other languages, it may be slower. In 2.5 seconds, an n^2 solution with n = 10000 might just pass, if the number of computations inside the loops isn't too much.

link

answered 12 Aug '18, 19:56

prakhar17252's gravatar image

4★prakhar17252
24618
accept rate: 5%

Considering that the CPU does approximately 10^9 operations per second, a complexity of n^2 would be more than the time bound.

I would assume the solution to be either O(n) or O(n log n) to fit within the time bound. It can be even lesser.

The number of loops is a tricky question, depending on on what elements it is traversing. But if the total operations in all loops you have used is closer to 10^8, you should be good. All the best!

link

answered 12 Aug '18, 19:05

ruddradev's gravatar image

3★ruddradev
1245
accept rate: 7%

Thanks you so much. Would you please tell me if i am using n^2 worst case complexity what will be max i can traverse in 2.5 sec?

(12 Aug '18, 19:10) ezio272★

I would say somewhere around 10^4 elements.

(12 Aug '18, 20:18) ruddradev3★

as already said 10^8 number of operations per second(not 10^8 times the loop) is the limit for online judge

as an example if your loops run say 10^7 times but you are perfoming 15 operations per loop then effectively you are doing 1.5*10^8 operations which may be a TLE

so what I want to say is that 10^8 operations are allowed not 10^8 times the loop

hope u get a clear thought : )

link

answered 04 Oct '18, 01:25

rajput1999's gravatar image

4★rajput1999
3596
accept rate: 0%

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:

×678
×263
×204
×141

question asked: 12 Aug '18, 18:57

question was seen: 1,248 times

last updated: 04 Oct '18, 01:25