GradientDescent | Topcoder Archive

Problem Statement

You are writing the scheduler for a small hardware device with a single input peripheral, and a single output peripheral. Typically, programs that run on the device must make exclusive use of the input for some amount of time, then do a negligible number of calculations and finally make exclusive use of the output for some amount of time. For example, a program might require 4 seconds of input, and then 2 seconds of output. We assume that the output may immediately follow the input (but doesn't have to), without delay, and that no time is required before the input, or after the output. Furthermore, while one program is using the input, no other program may use it, and similarly for the output. However, one program may use the input while a different program uses the output.

You have been trying to come up with a good scheduling alogorithm where the time at which all programs are finished is minimized, but are having no luck. Nothing seems to run fast enough. So far, you have figured out that once you decide on an order that the programs use the inputs, the optimal output ordering for that input ordering is the same as the input ordering. Hence, if program i gets to use the input before program j, it should also get to use the output before program j. However, having made no progress on determining the input order, you decide to try a different approach - gradient descent.

You will pick a schedule at random, and then repeatedly swap pairs of programs in the schedule, provided that the swap will improve the total time. Since you know how to order the outputs, given an ordering on the inputs, you only have to worry about swaps in the input ordering. Hence, your algorithm will roughly follow this pseudocode, where f(P) returns the time taken for all programs to finish when they use the inputs in order P, and use the outputs in some optimal order (given P):

	pick a random ordering, P, for the programs to use the inputs
next:	let T = f(P)
	for each pair of programs p₁ and p₂
		let P' = P with p₁ and p₂ swapped
		let T' = f(P')
		if(T' < T)
			P = P'
			goto next
		end if
	end for
	return P

If there are multiple pairs p₁ and p₂ that could be swapped to improve the total time, you've decided to pick the pair whose later program has the earlier end time in P. In other words, if the two pairs had end times of {6,7} and {3,8}, we would pick the pair with end times {6,7}, since 7 is less than 8. If there is a tie, then we will pick the pair whose earlier end time is earliest. Hence we would pick {3,5} over {4,5}.

You've implemented this algorithm, but you've found that it doesn't always give you the optimal schedule. So, now you want to find out the ratio of the optimal time divided by expected total time from this algorithm for some set of programs. You will be given a int[], A, and a int[], B, representing the times that a number of programs must use the input device and the output device, respectively. Corresponding elements of A and B represent a single program.

Definition

Class:: GradientDescent
Method:: optimality
Parameters:: int[], int[]
Returns:: double
Method signature:: double optimality(int[] A, int[] B)
(be sure your method is public)

Notes

Your return have have an absolute or relative error less than 1e-9.

Constraints

A and B will contain the same number of elements.
A and B will contain between 2 and 9 elements, inclusive.
Each element of A and B will be between 1 and 9, inclusive.

Examples

```
{4,3}
```
```
{3,2}
```
```
Returns: 1.0
```
Clearly, whenever there are only two programs, we will consider letting each one go first, regardless of our original random order. Therefore, whenever there are 2 programs, the probability should be 1.
```
{4,6,8}
```
```
{9,3,7}
```
```
Returns: 1.0
```
There are 6 possible orders that for the programs to use the input: {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}. The following table shows the sequences of swaps for each order, along with the total times after swapping. original order | swaps | total time ---------------+------------------------------------------+------------- {0,1,2} | {0,1,2} -> {0,2,1} | 23 {0,2,1} | {0,2,1} | 23 {1,0,2} | {1,0,2} -> {0,1,2} -> {0,2,1} | 23 {1,2,0} | {1,2,0} -> {2,1,0} -> {0,1,2} -> {0,2,1} | 23 {2,0,1} | {2,0,1} -> {0,2,1} | 23 {2,1,0} | {2,1,0} -> {0,1,2} -> {0,2,1} | 23
```
{4,9,2,1,8}
```
```
{8,3,1,7,6}
```
```
Returns: 0.9860935524652339
```
The optimal order to let the programs use the input is {3,0,4,1,2}. However, if we end up ordering with orders such as {3,2,0,4,1}, then no swap will improve the final time, and we will end up with suboptimal schedules. However, we happen to end up in one of those schedules fairly infrequently, and their total is only one more, so the ratio is almost 1.

{4,4,7,7,1,8,3,1}

{8,1,9,2,3,7,4,2}

Returns: 0.9147745807651084

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.