WebCrawler | Topcoder Archive

Problem Statement

Web Indexer is a search engine widely used in Byteland. Like other search engines, it uses crawlers to fetch the content of websites that need to be indexed. For Web Indexer, it uses a simple two-thread crawler to browse the remote site. You are hired to analyze the performance of the crawler.

To simply this problem, a connection can be regarded as two events: SendRequest and RecvResponse. The time between these two events is called "WaitingResponse". In particular, for the i-th connection, the length of the WaitingResponse period is a random value uniformly distributed between minResponseTime[i] seconds and maxResponseTime[i] seconds.

The crawler uses two threads to fetch webpages in the order specified in the input (except that two fetches can be started at the same time if each is processed by a different thread). The fetching is ordered by the time of each SendRequest event, so the RecvResponse events can be out of order. For each thread of the crawler, it can establish another connection instantly after the RecvResponse event of the previous connection (that is, at any time, there are at most two connections in their "WaitingResponse" period).

Given two int[]s minResponseTime and maxResponseTime, write a class with a method named getExpectedTime which takes these two parameters and returns a double that represents the expected time required to fetch these pages if the crawler uses an optimal strategy. The time used to finish all tasks is the time between first SendRequest event and last RecvResponse event.

Definition

Class:: WebCrawler
Method:: getExpectedTime
Parameters:: int[], int[]
Returns:: double
Method signature:: double getExpectedTime(int[] minResponseTime, int[] maxResponseTime)
(be sure your method is public)

Notes

Your answer must have relative or absolute error less than 1e-9.
The ResponseTime of a connection is not necessarily an integer.

Constraints

The number of elements in minResponseTime will be between 1 and 30, inclusive.
maxResponseTime will contain the same number of elements as minResponseTime.
Each element of minResponseTime will be an integer between 1 and 60, inclusive.
Each element of maxResponseTime will be an integer between 1 and 60, inclusive.
Each element of minResponseTime will be less than or equal to the corresponding element of maxResponseTime.

Examples

```
{3, 1, 1}
```
```
{3, 1, 1}
```
```
Returns: 3.0
```
There are three webpages to fetch. The length of "WaitingResponse" for each webpage is determined. Here is a possible way to assign these three tasks to two threads. 0 1 2 3 +---+---+---+ A | 3 | +---+---+---+ 0 1 2 +---+---+ B | 1 | 1 | +---+---+
```
{1, 1, 3}
```
```
{1, 1, 3}
```
```
Returns: 4.0
```
There are three webpages to fetch. The length of "WaitingResponse" for each webpage is determined. Here are two possible ways to assign these three tasks to two threads. 0 1 2 3 4 +---+---+---+---+ A | 1 | 3 | +---+---+---+---+ +---+ B | 1 | +---+ and 0 1 2 3 4 +---+---+---+---+ A | 1 | 3 | +---+---+---+---+ +---+ B | 1 | +---+
```
{40, 1, 1, 1}
```
```
{50, 10, 10, 10}
```
```
Returns: 45.00000000000001
```
The sum of the lengths for the second, third and fourth tasks can't exceed the first task in any case. +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+ A | 45.0 (Expected) | +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+ +~~~~~~~~~+~~~~~~~~~+~~~~~~~~~+ B | | | | +~~~~~~~~~+~~~~~~~~~+~~~~~~~~~+
```
{1, 1, 1, 40}
```
```
{1, 1, 1, 50}
```
```
Returns: 46.00000000000001
```
The times for three of these four tasks are determined. +---+---+ A | 1 | 1 | +---+---+ +---+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+ B + 1 | 45.0 (Expected) | +---+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
```
{1, 1}
```
```
{10, 10}
```
```
Returns: 7.0
```

{1, 1, 1, 1, 1, 1}

{60, 60, 60, 60, 60, 60}

Returns: 101.50273202871468

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.