Evan_Shareef's blog

Top Observations

By Evan_Shareef, history, 4 years ago, In English

Sometimes, some problem teaches us how to focus on a problem and think of it differently.. Actually, these kind of observations just make me wondered..

For example : 6x -3 this is equation can be seen as 3(2x-1) which means if we put integer values of x then this equation will give us multiple of 3. So these kind of querys like if it is possible to obtain a value V from this equation putting some integer values of x ; can be observed from this equation.. When I was in high school, I didn’t think over any equations. Just solved them. But observing any equation is much more important. While thinking over such problems i only note down what kind of new observations I got that could help me in future.

I want to know more From you. Hope it will actually help new problem solvers. I also want some observations observed by you that may help others to think over a problem more precisely and accurate way. Which observations made you wondered and pleased and made you think "OMG! this can be viewed like this! Couldn’t think of it "

  • Vote: I like it
  • +30
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it
  • Viewing persistent segment trees as equivalent to querying on a 2d plane with queries sliding along one of the axis.
  • Given a grid with few cities on it and you want to run manhattan distance TSP on it. One of the polynomial time approx solution idea is to chop this big grid into smaller pieces of size sqrt(N)*sqrt(N) each and we move from small box to small box in snake manner and within each small box we solve it naively (i.e visit the cities in that box in any way), the total distance travelled this way is roughly <= Snake length + diagonal length of a small box * number of cities <= N*\sqrt{N} + \sqrt{2*N}*N. This is the very same intuition as Mo's algorithm where a query from L to R can be modelled as a 2d point with coordinate (L, R). The cities become the queries and we want to solve all queries in "cheapest cost".
→ Reply