PROBLEM LINK: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. The general caseThe 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?
It is extremely helpful to the draw the displacementtime graph of the scenario. 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_mn_h)t \\ &= \frac{n_hx}{v_h} + \frac{d  n_hx}{v_m} \end{align}$$ Complexity is $\mathcal{O}(1)$. 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
