Constraints and Time Limits

We are discussing the Aguinaldo sample problem. This is Part 3 of a series of posts which started here.

$latex 1 \le T \le 100$

 

Subtask 1 (40 points each):
$latex 1 \le N, P \le 2000$

Subtask 2 (60 points each):
$latex 1 \le N, P \le 3\cdot 10^9$

We look at the constraints section of the problem. There are two subtasks, each with different constraints for $latex N$ and $latex P$. For now, we say that the judges run your program once for each subtask. The first subtask asks that your program give the correct answer for all possible values of $latex N$ and $latex P$ that are most 2000. And the second asks that your program gives the correct answers for all values at most 3000000000.

Time Limit

Competitions have time limits for the programs to ensure that not only is the submitted solution correct, but that it also finds the answer efficiently. Most programs will find the correct answer… eventually. To illustrate, we know that there are only a finite number of possible passwords. But guessing each possible password of length at most 20 characters will take millions of years. The program the hacker uses is correct in the sense that it will find the answer. However, our time in the universe is finite and so running a program like that is not worth it. This is why contestants are encouraged to find efficient and optimal algorithms to solve problems.

Here are the regular time limits we apply for each programming language:

  • C / C++ : 2 seconds
  • Java: 4 seconds
  • Python: 10 seconds

This means that your program must finish processing the subtask within that amount of time. Note that since other programming languages run slower, they have more lax time limits. But the intended (optimal) solution for each subtask should be the ones which will pass.

For example, suppose your solution involves going inside a for loop $latex N$ times, and every time it adds two integers. Then, for each test case, it will enter the loop at most 2000 times. Thus, for each subtask, it will enter the loop at most 2000 · 100 times. This will reasonably pass the time limit. However, the same solution might not work for subtask 2 because we can see that the program is destined to enter the loop 3000000000 · 100 times. That’s probably not going to finish within the time limit.

We therefore conclude that you will need a more efficient solution than that.