Constraints in Problems

help
1

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
2

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
3

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 :slight_smile:

4 Likes
4

Nice Question , the answer to it has cleared my doubt’s regarding , how to use them and come up to an answer .

1 Like
5

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.