Invalid link. Cant see your solution.
Any cues on optimising it further in Python?
It would be of great help if someone could share their working code in Python.
Here is my implementation (Stuck at 40 points!) –
https://www.codechef.com/viewsolution/18676662
@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.
For those asking, I solved this with Python (PYPY) for 100 points: https://www.codechef.com/viewsolution/18662068
Code could have been much more elegant (& more optimised) but a contest is always speed-coding.
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.