You are not logged in. Please login at www.codechef.com to post your questions!

×

KOL16D - Editorial

PROBLEM LINK:

Practice
Contest

Editorialist: Soumik Sarkar

DIFFICULTY:

HARD

PREREQUISITES:

Basic maths

PROBLEM:

There are $n_m$ men and $n_h$ horses. The speed of each man is $v_m$ and speed of each horse is $v_h$. The men must cover a straight distance $d$. The men may utilize the horses. A horse can carry at most one man at a time and can obey instructions even when riderless. No time is needed in mounting or dismounting from a horse or reversing the direction of motion. What is the minimum time the men need to cross the distance?

EXPLANATION:

The difficult thing is to discover the optimal approach. Once the approach is known, a little bit of algebra will give the answer. There also also two trivial cases. When $v_m \ge v_h$, the men will be faster without horses and will take time $d/v_m$. When $n_h \ge n_m$ every man gets a horse and reaches destination in $d/v_h$ time. Now to the main problem

Simpler case with $v_m = 0$

Consider a case where the men cannot move and must rely on the horses. Although such a test case does not exist due to the constraints, solving this will help in finding the general solution. The solution is as follows.

The distance $d$ is divided into $n_h$ ranges. Each horse $h_i$ is given the $i^{th}$ range. First all horses start out carrying a man. Each horse carries his man to the end of his assigned range and drops him off. Then he returns to the beginning of his range and picks one man up. He repeats moving back and forth across his range until he picks up the last man. Then he moves to the destination.

As an example, consider $n_h = 2$ and $n_m = 3$. The time it takes for a horse to move across one range is $t$. Below are the states after every $t$ time.

vm=0

The general case

The previous solution needs to be modified to be applied to the general case. All men now move at $v_m$ forward when they are not on a horse. What difference does that make?

  1. When a horse is on his way back across his range after dropping off a man, he will meet the next man before he reaches the beginning of the range.
  2. If the last horse drops off men at the destination, that's a waste of time since one man will reach before the other. Instead, it is better to drop off the man at some distance from the destination in such a way that in the end all men and horses reach together.

It is extremely helpful to the draw the displacement-time graph of the scenario.

st-graph

The steeper lines are the trails of the horses with slope $v_h$ or $-v_h$, and the gentler lines those of the men with slope $v_m$. The red, yellow, blue and green trails belong to different horses. The black lines indicate where more than one horse travel in parallel. Each horse moves back and forth and carries one man across his range each time. At points where two horses meet they can easily swap their ranges, but the overall effect remains the same.

We do not know beforehand what range should be assigned to each horse, so let it be $x$. Also let the time taken for a horse to move across his range and then partly back until he meets a man be $t$. Then we can calculate $t$ as $$t = \frac{2x}{v_m + v_h}$$

Next consider the first man dropped off at distance $n_hx$ by the last horse. From there he moves at $v_m$ until he reaches $d$. Now the horse goes back and comes with another man again and again, until at the end all $n_h$ horses bring $n_h$ men. Since the total men is $n_m$, the number of times he sees the horse go and come back is $n_m - n_h$. $$ n_hx + v_m (n_m - n_h)t = d$$

We can plug in the expression for $t$, and simplify to get $$x = \frac{d(v_m + v_h)}{2n_mv_m + n_hv_h - n_hv_m}$$

From the graph we can see the total time taken $T$ is $$\begin{align} T &= \frac{n_hx}{v_h} + (n_m-n_h)t \\ &= \frac{n_hx}{v_h} + \frac{d - n_hx}{v_m} \end{align}$$

Complexity is $\mathcal{O}(1)$.
It is convenient to use Python here since it has built-in support for fractions. Using Java or C++ it is necessary to manually implement operations on fractions.

ALTERNATIVE SOLUTION:

If you have an alternate strategy that also takes minimum time, feel free to share it below.

EDITORIALIST'S SOLUTION:

Editorialist's solution can be found here.

asked 30 Oct '17, 17:08

meooow's gravatar image

6★meooow ♦
6.6k617
accept rate: 49%

edited 14 Nov '17, 00:01

admin's gravatar image

0★admin ♦♦
19.0k348495533

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,435
×1,213
×100
×10

question asked: 30 Oct '17, 17:08

question was seen: 248 times

last updated: 14 Nov '17, 00:01