CS344 HW#3

We will have two variables relating with the distance **dist** and **min_d**, which are initialized to 0.

For the first step of Takeshi’s Castle, we will first assign the minimum distance value between the starting points (lets call the points, \(r_0\) and \(b_0\)), to a variable called **dist**. To find the minimum distance, we calculate the three possible distance values that correspond with the three possible travel methods:

The distance between \(r_1\) and \(b_1\) (if both players jump at the same time).

The distance between \(r_1\) and \(b_0\) (if only player one jumps).

The distance between \(r_0\) and \(b_1\) (if only player two jumps).

After finding the 3 possible values, we find the miminimum of the 3, and assign it to the **min_d** variable. Now we will compare the two values **min_d** and **dist**. We already know that we need a rope with length **dist** because that is the initial distance between the two contestants. The question is whether we need a longer rope for the contestants to complete the first jump. If **min_d** is larger than **dist** set **dist** equal to **min_d**. If **min_d** is smaller than **dist** nothing needs to be done because the initial rope length will be long enough to complete the first jump.

Then, we make the contestants do the next iteration of the jump, do the same as above, and find the smallest distance value of the 3 jumps:

The distance between \(r_{i+1}\) and \(b_{k+1}\) (if both players jump at the same time).

The distance between \(r_{i+1}\) and \(b_k\) (if only player one jumps).

The distance between \(r_i\) and \(b_{k+1}\) (if only player two jumps).

Again, once we find the smallest distance value of the 3 jumps (**min_d**), compare it to the **dist** variable, and update \(dist\) if necessary. We do this until both contestants reach the end, and \(dist\)’s value is the smallest the rope can be, for the two contestants to finish the challenge.

In the worst case, we have to analyze \(m+n\) jumps because in the worst case at each jump, only one contestant can jump at a time. Also, there needs to be 3 checks and 3 comparisons for each iteration, to calculate the new value of \(min_d\). So in total, there are \(6*(m+n)\) operations, and the run time is \(O(m+n)\).