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

×

What should be the worst case time complexity of code to pass in 3 sec on Codechef?

I am trying to solve a question whose overall time limit is 3 sec. It has three subtasks. Time limit for each sub tasks in not mentioned, only overall time limit is given. So my first question is Does different subtasks have different time limit?

If the answer to the above question is NO then What should be the worst case time complexity of code to pass in 3 sec on Codechef including test cases?

Like 10^6, 10^7, 10^8 or 10^9?

asked 08 Dec '16, 14:37

ishpreet's gravatar image

4★ishpreet
9916
accept rate: 0%


@ishpreet At codechef, usually time limit for each subtasks is same and is equal to the overall time limit of question and approximately you can perform 10$^8$ to 10$^9$ computations per second, which means for a question having time limit 3s, you can perform approximately $3*10^8$ to $3*10^9$computations.

link

answered 08 Dec '16, 14:49

srd091's gravatar image

5★srd091
1.5k111
accept rate: 42%

edited 08 Dec '16, 19:32

Thanks @srd091. But my code complexity is 6*10^8. I got TLE. Don't Know Why?

(09 Dec '16, 00:19) ishpreet4★

Actually, it depends on problem setter, and its most likely, each sub-task has got different time limit and the last sub-task with original constraint has TL of 3 sec.

Runtime Analysis

link

answered 08 Dec '16, 19:19

neilit1992's gravatar image

3★neilit1992
1.1k11
accept rate: 20%

@ishpreet if you got your answer then please help me too. I am also stuck, all test cases where n<10^6 are accepted but for N>=10^6 I am getting TLE.

link

answered 09 Dec '16, 09:50

vpriyanshu40's gravatar image

2★vpriyanshu40
794
accept rate: 12%

edited 09 Dec '16, 09:51

@vpriyanshu40 What's the time complexity of your code and What's the time limit?

(09 Dec '16, 22:56) ishpreet4★
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:

×214
×108

question asked: 08 Dec '16, 14:37

question was seen: 722 times

last updated: 09 Dec '16, 22:56