Isn’t the Shooting on the array- SHTARR question of October Challenge similar to Hill jumping question of
August long.
SHTARR - https://www.codechef.com/OCT17/problems/SHTARR
HILLJUMP- https://www.codechef.com/AUG17/problems/HILLJUMP
However, I’m not getting the ans… it shows TLE… what further optimization is required ?
… Need Karma points to ask questions… please help, if possible.
They are similar problems, but what exactly is your question?
Whether the change is obvious or not, I think it will depend on your perception. The questions are similar, but not same and have some notable differences. Are you able to cope up with those? What errors are you getting?
yup… i realise the differences…I used the same sqrt-decomposition tecnique… but I’m getting TLE…
what further optimization is required.
For long contests, the best recommendation is to check time taken by your code for random large test cases. Is your code taking 5-6 seconds instead of 3? Then small optimizations like changing size of bucket, minimizing use of in built functions like pow (they are expensive) or minor optimizations can help.
But if its something like >10seconds, then perhaps we need to look for a logN approach.
Square rot decomposition is sometimes tricky. For N={10}^{6}, it can take upto {10}^{9} operations easily. If time limit is strict, then its difficult for this approach to pass.