Yes, I know. I described it in editorial, however, some other implementations (which used more expensive computations, or didnt optimize) failed as well.
1 Like
Well that should not have happened. Why there is always some problem in codechef contest with weak test cases?
I wil @code_man , but first check the answer by @l_returns on it. I think it satisfies what you want.
@akash_321 - I disagree there. I feel since setter and tester’s solution themselves are O({N}^{2}), they shouldnt have even tried to stop the O(26*{N}^{2}) ones. When 2 solutions are asymtotically similar, then even constant and random optimizations matter.
1 Like
Your solution is O({N}^{2} LogN) in my opinion, which is worse than O(26*{N}^{2}). Map data structure has a LogN factor involved.
i used unordered map…so it should be O(1) for insertion in my opinion…and for checking the second condition, I was iterating through this unordered map, which shall be less than 26 for many cases… @vijju123
The setter and tester did not intend that either, but they cannot indefinitely raise constraints or reduce TL, else some correct solutions will not pass. Ultimately they decided that, for second easiest problem of ltime, its ok if a few brute forces (optimized ones) pass. The tester himself made us aware by making such a solution. Its not that they were unaware of this, but its just that no correct solution should get TLE
link or didnt happen…xD
Hmm, true, but only provided that the test cases arent anti hash 
. Still, I read somewhere that the constant for unordered map is a little high. The TL for problem is tight, so try to solve it without unordered map.
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.
1 Like
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.