MonotoneSEMin | Topcoder Archive

Problem Statement

Given a sequence of bits (0's and 1's), we want to find an arbitrary monotonically increasing curve that best fits the bits. That is, the i^th bit is b(i), and we want to find some curve, f, such that for x<y, f(x) <= f(y), and the sum over i of (f(i)-b(i))² (the squared error) is minimized.

Given the sequence of bits as a String[] where you concatenate all the elements together, return the minimum possible squared error.

Definition

Class:: MonotoneSEMin
Method:: min
Parameters:: String[]
Returns:: double
Method signature:: double min(String[] bits)
(be sure your method is public)

Notes

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

Constraints

bits will contain between 1 and 50 elements, inclusive.
Each element of bits will contain between 1 and 50 bits ('0' or '1'), inclusive.

Examples

```
{"10001110"}
```
```
Returns: 1.5
```
The flat curve f(x) = 0.5 would give a squared error of 0.52*8 = 2. Naturally, we can do better than this though, and it turns out that the best we can do is a squared error of 1.5.
```
{"00"}
```
```
Returns: 0.0
```
```
{"11"}
```
```
Returns: 0.0
```

{"1010100101010101001010101001",
 "0101010100100010010001010101",
 "1110110101001011010111011011",
 "1010111101110110111000111100"}

Returns: 26.244842801985662

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.