I’m re-attempting this problem statement, now that the contest is all over (so it’s not cheating or anything, just want to learn, since the answers are not published, only the correct output for the given test case input files).
There are 10 given test case inputs, for which the associated output files are to be submitted. My original submission was an implementation of a naive nested for loop of (start,end) pairs, answering the query: What is the volatility measure of the substring starting at (0-based) index start, and ending at end (inclusive).
Clearly, for the maximum problem limits of 106, O(N2) is infeasible, so I only got as far as 5/10 test cases correct (the first - and simpler - 5, of course).
As such, I’m writing here to seek the crowd intelligence on how I could go about improving my algorithm, namely I suspect the nested for loops (start,end) is the main bottleneck to optimize (of course!) So far, I’ve gone down the route of trying to formulate this as a dynamic programming (DP) on strings/substrings problem, but without any much success on coming up with the state representation and transition bits so that the DP can be implemented.
For easy reference, and to show that this is not homework, and I have honestly tried, my original submission is available here.
Any help is much appreciated, even links to similar problems for which I can google for tutorial blog posts/sample solutions/post-contest editorial analysis.