What does a range in time limit mean? eg - time limit : 1-10 sec

Some questions specify a range as the acceptable time limit for the problem, I do not understand what exactly does it signify?

It just signifies that your solution should take time between 1 to 10 (inclusive), if it takes so then will be considered as correct.

Your program must read, process, and output the result for an input file within the specified time limit. The input file will be of the format mentioned in the problem.

This means, if the input contains multiple test cases, your code must complete ALL of these within that time limit. If the time limit is 2 seconds, and there may be 1000 test cases, your program shouldn’t be taking 1 second per test case - it needs to run all 1000 in under 2 seconds. Refer this. How can your code take time less than the lower bound? Did you mean, less than the given time limit? If yes, then your ACed solution will show you the time taken by your solution.

I’m not problem setter, just some thoughts… In general, there are more test cases. So this is probably that for small test cases the limit is 1 second, for huge input file it is 10 seconds. Especially for partially graded questions that makes sense… Are you talking about particular problem, if so, and it is partially grades look into details, maybe you will see what that means…

2 Likes

@betlista
No, for problems that are not even partially graded a range of time limit is specified. Example

So, we can’t really say that the lower bound of the range is probably for small inputs. We can’t be sure about that atleast.

You must already know, that each problem is tested on multiple test cases and test files.

So, if you see an input format of the type, “the first line contains T, the number of test cases…” then, it means, there is a single file containing input specified in that format; and there are more than one such file.

So, time limit is specified individually for each such file. If the specified time limit is the same for all files, then you will see a single number in the time limit section. However, if you specified different time limits for different input files (usually, because some files contains very large input and might need more processing time, compared to other files,) then the time limit shows up as a range – the lowest of time limits specified, to the highest of all time limits specified.

For example, if you have input files with time limits 3s, 0.5 s, 1.2s, 2.015s, 6s, 1.2s, and 1.2s, then the time limit will show up as 0.5s - 6s (all the time limits belong to this range, both inclusive.)

So, your program must finish running in under 3s, 0.5 s, 1.2s, 2.015s, 6s, 1.2s, and 1.2s, respectively for each of those input files.

PS: I have set a couple of problems for an old contest hosted on codechef.

2 Likes

What if it takes lesser time than the lower bound?

Yeah, I meant if it took time lesser than the lower bound of the range of time limit given.

External contests are completely different story, so it can be very different for those contests…

y best guess is, that problem setter tries his solution with few inputs and specified something like - it is 0.2 s for this input, 0.3 for that one and 0.5 for the last and you won’t know more…

Thanks, good idea.

What is the purpose of this? Why not just put each case in a different file? Otherwise, put the same number of tests in each file and set a fixed time limit.

It is very irritating to judge how fast your program needs to be if the time limit is not fixed.

Okay! I got it now. Thanks. It is indeed tricky.

@superty May be, the number of tests in each file is the same. But, the actual values/numbers of a particular case is different from others, and might need more time.

One thing that the setter can do here is, to set the time limit of every file to be equal to the largest of the time limits. Since, only better algorithms are supposed to pass the time limit for even the files containing large tests cases, that should be okay for other test files as well. But, if that is a better algorithm, then it would sure pass under the smaller time limit for smaller files. :slight_smile:

@sakshichauhan Not really tricky. It is just that, you don’t know what is the time limit for a particular input file. But, that should not be a problem. You can be assured that the largest of the possible test files should pass in the the higher time limit. Usually, if you can get to that, the other tests would pass as well.

Actually, a solution I expected to pass failed on the last subtask in the past lunchtime because of this. I am pretty sure it would’ve passed in 2 secs. (the stated limit is 1-2 secs)

http://www.codechef.com/viewsolution/5988907
(I know this isn’t the expected algorithm. I figured it out during the contest and resubmitted to get 100)

Yes, that subtask (with just one test file) was timed at 1 second.

And, congrats for making it to 100 points. :slight_smile:

My point was that I was confused for a while because I assumed that 1-2 seconds meant that 2 seconds was acceptable on all.

Thanks.

Ah, okay. Got it. Yeah, it is a bit confusing, if you don’t know what is happening. I only know this, because, I have set a couple of problems, and saw that this is how the time limit appears.

1 Like