We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
That's what I understand this theory.
We can try to understand this logic like we imagine Supermario walking on a N width horiz line. a and b is the
point on the line, k is the mushroom Mario like to eat.
When Mario go to the point at a,he eat the k size mushroom and become taller,after he have walked through point b,
his height reverse to the origin height before he eat the mushroom.
eg.
1. When Mario is walking to a, he eat a k size mushroom, and become k bigger
2. Then Mario is walking to a', he eat a k' size mush, and become k' bigger, now Mario's height is (k + k')
3. If Mario have walked to b, so he pooped out the mushroom and become k smaller, the only way that he can
become larger is to meet a new (a,b) point and eat a new k size mushroom
4. The rest can be done in the same manner.
What we need to do is tracing the Mario's biggest height when walking through that muliple query's a and b point.
awesome explanation..
btw i wanted to ask if this is what we call segment tree..and if we can use this method to solve questions with the segment tree tags..
P.S. : I have a very little knowledge about the segment trees.
Most of the peope solved this problem but time complexity of solution is O(n*m) (due to two nested for loops)which can not be used to solve this problem for given time constraint, so you need better approach which beats O(n*m)
I have created a video tutorial for you and uploaded the same on youtube with complete explanation along with code complexity analysis.
Here is the video tutorial for my solution O(n+m) complexity passed all test cases.
Array Manipulation
You are viewing a single comment's thread. Return to all comments →
The solution works, but how did you came to this theory ?
That's what I understand this theory. We can try to understand this logic like we imagine Supermario walking on a N width horiz line. a and b is the point on the line, k is the mushroom Mario like to eat. When Mario go to the point at a,he eat the k size mushroom and become taller,after he have walked through point b, his height reverse to the origin height before he eat the mushroom. eg. 1. When Mario is walking to a, he eat a k size mushroom, and become k bigger 2. Then Mario is walking to a', he eat a k' size mush, and become k' bigger, now Mario's height is (k + k') 3. If Mario have walked to b, so he pooped out the mushroom and become k smaller, the only way that he can become larger is to meet a new (a,b) point and eat a new k size mushroom 4. The rest can be done in the same manner.
awesome explanation.. btw i wanted to ask if this is what we call segment tree..and if we can use this method to solve questions with the segment tree tags.. P.S. : I have a very little knowledge about the segment trees.
Thanks in advance.
you can refer top coder or either gog to understand the concept of segment tree. ;)
acha bhai :D
haha.. ;)
This is literally the only reason I actually was able to understand the logic of the code. Thank you for that, seriously.
Very nice explanation. The explanation in the question does misleading on how to implement the solution.
Thanks a lot for your explanation, it really simplified the problem. :)
ahaha great explanation, thanks so much!
The only explanation I understood
Hi,
Most of the peope solved this problem but time complexity of solution is O(n*m) (due to two nested for loops)which can not be used to solve this problem for given time constraint, so you need better approach which beats O(n*m)
I have created a video tutorial for you and uploaded the same on youtube with complete explanation along with code complexity analysis.
Here is the video tutorial for my solution O(n+m) complexity passed all test cases.
https://youtu.be/hDhf04AJIRs
Would really appreciate your feedback like, dislike , comment etc. on my video.