A problem is solvable in various approaches. However, some solutions tend to be more feasible than the rest. The reasons may include better time complexity, less memory requirement or ease of implementation.
Why do Competitive Programming problems mention Constraints?
In a competitive setup, we must be aware of our program’s efficiency to solve a problem. This is where constraints comes to play.
Constraints in easy terms are the requirements that our solution must fulfill. The programs that we submit for a particular problem needs to be tested for correctness. These may be tested on some large datasets which we manually cannot verify using pen and paper.
These datasets also known as test cases, are strictly described as per the constraints. Our program must give correct results for all these test cases and terminate in stipulated amount of time to get the Correct Answer verdict.
Constraints direct us to think of a feasible solution. We must keep the constraints in our mind before framing the algorithm for a problem. Analyzing the constraints can give us crucial information, like the possible edge cases and the expected time complexity of the solution. In some problems, it even makes our choice of data structures easy.
Consider this classical problem.
Given an array A of n numbers, our task is to calculate the maximum sub array sum, i.e., the largest possible sum of a sequence of consecutive values in the array. The array may include negative numbers. This problem is solvable through various approaches having different time complexities.
O(n3) - This naive approach includes considering all the sub arrays and finding their sum.
O(n2) - This approach includes considering all the sub arrays and finding their sum in constant time using prefix sums. O(nlogn) - This approach makes use of divide and conquer paradigm.
O(n) - This approach makes use of dynamic programming. (Kadane’s Algorithm)
If the given array is,
[-3, -2, 6, -5, 8, 5, -12, 11]
The maximum sub array sum is 14 as given below
[6, -5, 8, 5]
Now suppose the constraints for the problem are as follows:
1<=n<=105
|Ai| <= 109, 1<=i<=n
The size of the sub array must be greater than zero
Considering the time limit to be 1 second, and the fact that most of the coding websites allow 10^8 operations per second, it is clear that only O(n) and O(nlogn) solutions will pass the time constraint. O(n2) and O(n3) are bound to give time limit exceeded (TLE) verdict.
An O(n2) solution for this problem will take time in minutes to terminate. Suppose, if the constraints do not mention the fact that, “The size of the sub array must be greater than zero”, we might have to deal with an edge cases.
What if all the array elements are negative?
[-8, -6, -2, -7, -1, -3]
In the above array, all the sub arrays will have negative sum. Therefore, the answer will be zero, which is the sum of an empty sub array.
Thus, constraints form a very important part of a well-designed problem, as they guide us through our journey to code correct solution.