Connection Status:
Competition Arena > EllysRivers

EllysRivers

SRM 543 · 2011-11-22 · by espr1t

SRM 543 · 2011-11-22 · by espr1t · Dynamic Programming, Search
Class Name: EllysRivers
Return Type: double
Method Name: getMin
Arg Types: (int, int, vector<int>, vector<int>)
Problem Statement

Problem Statement

Shopping is by no means an easy task. Yes, sure, if you want to buy shoes or some clothes that's no problem at all. But what happens if you would like an extremely rare poison, found only in the mists of Amazonia? Now you see, Elly's life is not as easy as you would think. She has almost reached her final destination, but unfortunately she can only use boats and travel by foot for the final part.

There are N+1 really long, but narrow parallel islands, going from South to North, numbered from 0 to N, inclusive. There are also N rivers between the islands, numbered from 0 to N-1, inclusive. River i is width[i] kilometers wide and flows between islands i and i+1. The speed of the current in each river is negligible. For river i, the maximum speed at which Elly can sail is speed[i] kilometers per hour, regardless of the direction in which she sails.

All islands are length kilometers long. Starting from the southmost point, each one has boat docks one kilometer apart throughout its entire coastline. Thus, there are length + 1 docks on each island (at kilometer 0, 1, …, length). The islands are so narrow, that you can assume the same dock serves the boats on both sides of the island, and that walking horizontally from one side of the island to the other takes no time.

For simplicity we can represent the islands as parallel vertical line segments, and the docks as points on the plane. Island 0 goes from point (0, 0) to (0, length), island 1 from (width[0], 0) to (width[0], length), island 2 from (width[0] + width[1], 0) to (width[0] + width[1], length), and so on, where width[i] gives the width of the i-th river. The docks on island 0 are with coordinates (0, 0), (0, 1), … (0, length); the ones on island 1 are with coordinates (width[0], 0), (width[0], 1), …, (width[0], length); these on island 2 are with coordinates (width[0] + width[1], 0), (width[0] + width[1], 1), …, (width[0] + width[1], length) and so on.

Elly can only take boats from dock to dock (i.e. she can neither depart from nor arrive at non-integer coordinates). She can also walk (vertically) along any island with a constant speed of walk kilometers per hour. The girl is currently on the southmost point of the westmost island and wants to reach the northmost point of the eastmost island. Elly wonders what is the minimal time required to travel to her destination. Help her by writing a method that calculates this for her.

You are given the length of the islands in the int length and the walking speed in the int walk. The widths of the rivers will be given in the int[] width and the maximal sailing speeds in the int[] speed. Return a double giving the shortest time in which she can reach her destination.

Notes

  • Your return value must have a relative or an absolute error of less than 1e-9.

Constraints

  • length will be between 1 and 100,000, inclusive.
  • walk will be between 1 and 1,000,000, inclusive.
  • width will contain between 1 and 50 elements, inclusive.
  • speed will contain between 1 and 50 elements, inclusive.
  • width and speed will contain the same number of elements.
  • Each element of width will be between 1 and 1,000,000, inclusive.
  • Each element of speed will be between 1 and 1,000,000, inclusive.
Examples
0)
10
3
{5, 2, 3}
{5, 2, 7}
Returns: 3.231651964071508

Elly will not walk on any of the islands. She will sail four kilometers to the north in the first river, reaching the second island at point (5, 4). Then she sails another one kilometer to the north in the second river, going to (7, 5) on the third island. In the end she will sail to her destination at (10, 10). The required times for her journey are as follows: (0, 0) -> (5, 4) = 6.403124237433 / 5 = 1.280624847487 hours (5, 4) -> (7, 5) = 2.236067977499 / 2 = 1.118033988749 hours (7, 5) -> (10, 10) = 5.830951894845 / 7 = 0.832993127835 hours

1)
10000
211
{911}
{207}
Returns: 48.24623664712219

Don't forget that Elly can walk on the islands.

2)
1337
2
{100, 200, 300, 400}
{11, 12, 13, 14}
Returns: 128.57830549575695
3)
77
119
{11, 12, 13, 14}
{100, 200, 300, 400}
Returns: 0.3842077071089629
4)
7134
1525
{11567, 19763, 11026, 10444, 24588, 22263, 17709, 11181, 15292, 28895, 15039, 18744, 19985, 13795, 26697, 18812, 25655, 13620, 28926, 12393}
{1620, 1477, 2837, 2590, 1692, 2270, 1655, 1078, 2683, 1475, 1383, 1153, 1862, 1770, 1671, 2318, 2197, 1768, 1979, 1057}
Returns: 214.6509731258811

A large random example.

Submissions are judged against all 119 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EllysRivers with a public method double getMin(int length, int walk, vector<int> width, vector<int> speed) · 119 test cases · 2 s / 256 MB per case

Submitting as anonymous