Recently I came across a problem RACETIME on SPOJ. After trying hard for the problem when I couldn't make a progress I searched internet for a solution.
Discussions on various forums talked about the technique of Square Root Decomposition.
So I studied about this technique from here.
But after going through all of them my question is
What thinking process does one undergo before coming up to the conclusion that a particular problem can be solved using Square Root Decomposition?
Sometimes they even divide the queries into sqrt N buckets and then solve them?How does that one even think that.
I have searched a lot over the internet but couldn't get anything useful except their implementation.
So it'd be really very useful if someone could explain me about how to approach such problems possiblly with some example So that whole programming community can get benefit from it.