Solving a Programming Contest Problem, Part 2 of 2 (Think Like a Programmer)

[@vantonspraul]

Glad you like the videos and the book! More videos on the way. Thanks for posting.

[@originalhindmost2999]

So far I've been lost with all the practice problems because they involve math, but I've been picking up the concepts.

[@vantonspraul]

You're right. Good catch.

[@RinatTainov]

Just take ccoordinate system for everything from robber perspective. So door will run him and guard will run with additional speed.

[@MultiSteveB]

You can detect if the robber having passed the door, and if the guard has passed the robber after calculating their new positions by storing their last position, then checking to see if the sign of the difference between their new position & the destination is different from the sign of the difference between their old position and the destination. The tricky-ish part IMO is detecting if in the last iteration where the robber gets to/passed the door, the robber would have caught him, given a smaller time increment.

[@arantebw]

V. Anton Spraul, thank you!

[@nelsonariza4075]

I was wondering why wasn't Pythagorean theorem used for this? By looking at the big triangle for the robber, we can calculate the distance between the robber and the door. Then we can just break down time snap shots, as in how far did the robber move in 1/10th of a second and so on giving a new robber location coordinate. The guards triangle changes every time. So by feeding the robbers new location and the guards current location, we can create a triangle. Using Pythagorean theorem, we move the guard by the same time frame we moved the robber. The triangle for the guard changes every time. Finally we make conditions to check coordinates. If robber reaches (0,0) then he escapes. So we say if x coordinate is more than 0 and y coordinate less than 0, then robber escaped. If guards coordinates equals to robbers coordinates, or (guards x coordinate is less than robbers x coordinate, and guards y coordinate is less than robbers y coordinate ) then guard reaches the robber in time

[@vantonspraul]

Hey, Nelson. Another viewer made essentially the same point, below. The truth is, when I work on these problem examples, I show the actual process of me working towards a solution, without cheating and finding a solution, polishing it up, and then working backwards. So you're seeing my first ideas and I stop when I get one that works, so the program I end up with is usually far from optimal.

[@LazieKat]

Or you could use calculus. The robber's path is linear, and the guard's direction rate of change is the slope of the line from his position to every point on the robber's path, now we have a line and a function. Solve for their intersection, if the result is negative (considering the door is at 0, 0) then the guard won't catch the robber, otherwise, he will. I try to use calculus for iterative problems, it might not always work, but when it does it'll be O(1).

[@armanx2]

So this is how you do collision detection :) by using vertex magnitude and normalization at least in game development ;) Cool videos sir, keep doing the good job

[@HOWDOT]

Love your video man :) .. Thanks for Teaching us some awesome problem solving technic :)

[@DarkZoneGamingMain]

Can anyone tell me what the "&" means in C++ code for example at 4:30 inn the video among the arguments of the method "computeChanges" there is "double & movingX"

[@vantonspraul]

The ampersand, when placed between the type and the parameter name, indicates a reference parameter. That means movingX and movingY are references to the variables passed to the function in the call, and so when these are given new values in the function these are assigned to the variables used as the arguments. Without the ampersand, you would get value parameters, local variables with the same values as the arguments.

[@DarkZoneGamingMain]

Thank you for replying! I wanted to thank you for this series and let you know that I bought your book after watching a lot of this series. It's been extremely helpful to me as a programmer :) I hope you can keep making problem solving or programming-related videos as you're great at explaining this stuff!

[@vantonspraul]

Thanks! I hope you enjoy the book. I'm definitely going to keep making videos, got a couple more in the pipeline already.

[@nitinsehra2760]

Hello sir, I would like to know about few programming contest sites that you recommend for beginners like myself (language C++). Thank you.

[@MrVinay6878]

Nitin Sehra try hackerrank, or hackerearth ...or codechef ... But Try codechef on ur own risk

[@TheArakan94]

why did you use non-standard _copysign? why not copysign from math.h?

[@vantonspraul]

+David Novák No good reason, just happened to code this on an older edition of Visual Studio.

[@illuminatelair8084]

is this supposed to be an introduction to problem solving? it so, this example seems quite advanced and not that intuitive!

[@johnnyLikeVideo]

It never occurred to me space was the thing that was moving.

[@goldfishbrainjohn2462]

I'm too stupid to understand this.

[@nirshalmon1646]

But wouldn't this only have an accuracy of +-0.2ft or less? Most contests require much higher accuracy

[@martingaens2073]

Yep... I totally agree to this. This is a very basic solution to the problem. And not very precise.