Here is a link to the question->
http://www.codechef.com/MARCH15/problems/STRSUB…
I have a doubt that what is the significance of constraints like this …
plzz someone help help me to understand the question more precisely by explaining the imortance of these constraints. !!
Actually you can use this information for predicting whether your solution will pass or not.
Let f(n) denote time your code takes on a given n for a single test case.
Then total time of your code will be f(n_1) + \dots + f(n_T) for all the T test cases.
So constraint "Sum of n over all test cases in one test file does not exceed 10^5" guarantees that n_1 + \dots + n_T is at max 10^5. Using this information, you can predict exactly how much time your code will take.
Assuming f(n) = \mathcal{O}(n):
then You can notice that your code for all the test cases won’t take more than 10^5 operations, because f(n_1) + \dots + f(n_T) = n_1 + \dots + n_T \leq 10^5
Assuming f(n) = \mathcal{O}(n^2):
then You can notice that your code for all the test cases won’t take more than 10^{10} operations, because f(n_1) + \dots + f(n_T) = n_1^2 + \dots + n_T^2. In this case, if there is a single test case with n = 10^5, then your code will take 10^{10} operations in the that test case.
Similarly, you can find desired complexity for any problem in which constraints on sum are given.