This post is in reference to CodeForces

Long Jumps.

You have a ruler of length with various distances marked off. Any distances between two markings/endpoints can be measured exactly.

You are given two lengths J1 and J2: can they be measured by the ruler exactly? If not, can we get there by adding a single marking?

To solve:

1. Iteration is done over each marking. With each marking we ask the following:

1a. Does exist?

1b. Does exist?

If both 1a and 1b check out, it’s solved: no additional markings required.

2. Iterate again as before, asking the following:

2a (Stacking): Does exist? If so, it is solved: we make our additional marking at (or ).

2b (Subtracting): Making sure > , does exist? If so, it might be solved: we make our additional marking at or if that exists on the ruler. (However it might fall off one or both ends.)

And finally, the “does it exist” test takes using binary search. The total time is .

My solution is in git and below:

*Related*