Ans2 - The reasoning is not correct. I can use the same reasoning to claim that “For sorting the numbers, we know that there are N! permutations. We need to try each and every one of them to see if that permutation is sorted or not. Hence, sorting takes O(N!) time.”
Ans 3- Yes, but 2*{10}^{4} isnt a very good estimate for TL of 1 second, as depending on implementations, it can take 0.4 - 4 seconds.
for(int i = 0; i < l; ++i) {
for(int j = i + k - 1; j < l; ++j) {
int count_t[26] = {0}, pr = 0;
O(26*{N}^{2}) with expensive operations. Remember that accessing elements of 2-D array is slower than that of 1-D array. Everything matters when constraints are too tight. Refer to code under point 1. in my corner.
The constraints were too tight. It seems Python needed more than 3x multiplier. But in general, we expect user to know which language is best to tackle a particular problem.
Invalid link. Cant see your solution.
@vijju123 , Atleast there should be 2 question in LunchTime or Cookoff which does not depends upon programming Language .
Generally , for faster submission , user use python for it .
we get more confused when there are tle in easy problem and start thinking less complexity solution
True, I understand. I had discussions with them regarding this as well.
You can give that feedback at the contest announcement thread for them to see.
Ans2 - I mean we have to check every substring if it is interesting or not. There are O(n^2) substrings, so checking every substring will take at least O(n^2) time.
Is there any better way to do this in less than O(n^2)?
Ans3 - In what situation string size 2∗10^4 will take 4 seconds?
For Ans2- No, you may not need to check all substrings. Perhaps its possible from data of sub-strings processed till now that you can say for sure that “We dont need to check next K sub-strings as as they can-never-be/will-always–be a part of answer”. Like, read about centroid decomposition. It answers queries in O(NLogN), and not O({N}^{2}) as it does not have to check all paths.
Ans3- If operations involved are very cheap (eg-bitwise operations), then {10}^{9}\approx 1sec. Other end is, if very expensive operations are used very frequently. 4sec is a loose upper-bound.