Long Jumps

This post is in reference to CodeForces Long Jumps.

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

Ruler = delim{lbrace}{0, D1, D2, D3, D4, L}{rbrace}

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 M_curr we ask the following:

1a. Does M_curr + J1 exist?
1b. Does M_curr + J2 exist?

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

 

2. Iterate again as before, asking the following:

lj2

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

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

 

And finally, the “does it exist” test takes O(log{n}) using binary search. The total time is O(n log{n}).

My solution is in git and below:

Leave a Reply