What is use of constraint in problem example
Constraint:
1<=testcases<=10 etc. Do we have to write a condition statement to check this constraint in our code?
1 Like
There is no need to check this constraint…What it means is that there will be a maximum of 10 test cases in each test file against which your code is checked by the online judge…
2 Likes
The constraints whatever they be , provide the base for any coder to write a programme .ie…whether the algorithm which you are following to solve a problem is suitable for the given constraints or not .
Let me explain this with the help of a few examples ->
1<=N<=1000
Suppose for the above constraints we have to solve a problem , say sort a list of given no’s :
So here even if you use an O(n^2) algorithm for sorting say bubble sort , it would work without an problem . The reason being that a computing machine can do upto 10^6/10^7 computations per second .
1<=N<=100000
Now to sort a list with 100000 elements ie… 10^10 computations need to be done for the above n^2 algorithm would obviously time out , thus we use qsort/mergesort O(nlogn) .
Now suppose a problem has very high constraints say :
1<=N<=10^18
So in such a case your mind should come up with solutions with O(logn) complexity , because even O(n) would time out for the reasons mentioned above .
Some Extra things to be kept in mind :
Suppose in a problem , if you think that solution for a problem is O(n^2) / any other polynomial complexity , then here Dynamic programming can help you to optimise the solution .
Crux of The discussion : So what we can conclude is that the constraints always help you to plan which data structure / algorithm is to be followed to solve a computing problem .
Some useful links :
If in case you are not familiar with the big(0) notation , this link will help you get started :–> http://www.codenlearn.com/2011/07/understanding-algorithm-complexity.html
In case of any doubt regarding learning new data structures / dp / anything , the below is the go to page :---->
http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/
And yes I hope the above helps you . Happy coding 
4 Likes
Nice Question , the answer to it has cleared my doubt’s regarding , how to use them and come up to an answer .
1 Like
By seeing the constraints, one can get the worst time algorithm.Also,it helps to come up with a better algorithm which would work under given constraints.
1 Like