## Random Search OptimizationProblem #106 |

Many problems for which computers were initially created are of **optimization** nature. And one of the important
ways to solve optimization tasks is a Random Search. It has two main
advantages over other methods:

- it is really simple and could be implemented without great knowledge of math;
- it allows to find solution for mathematically complicated cases - multi-modal, non-differentiable etc.

Popular **Genetic Algorithm** is just one of the **Random Search** family.

Here is our task of optimization - look at the demo above: we want to transport some box (depicted as a violet
rectangle) for `100`

metres by straight line.

We have a kind of transportation machine or prime mover, depicted by green dot. It has infinitely small size and so can share coordinates with the box.

The box and the mover are tied with an elastic spring (yellow line) so when mover goes away from the box, spring tension starts move the box.

When the mover reaches `100m`

mark, it stops, but the box may overshot the position and then it would be pulled back
by spring. It could really oscillate for some time until friction would stop it.

The mover is unmanned so we can control it in a slightly restricted way: we can tell it change the speed after
travelling each `20m`

- so the whole path is divided into `5`

regions and inside each of them mover goes with a
constant speed. At region boundaries the speed is switched instantly. However speed could not change by more than
`3 m/s`

- for the fear of burning electric drives of the mover.

To model the process of transportation use the following pseudocode:

```
x = 0 // initial coordinate of the box
v = 0 // initial speed of the box
xd = 0 // initial coordinate of the mover (or driver)
t = 0 // initial time
dt = 0.2 // time step of simulation
m = 5 // mass of the box
k = 0.5 // coefficient of elasticity of the spring (as in Hooke's Law)
b = -0.5 // coefficient of friction for the box (viscous friction, proportional to speed)
while not_stopped:
force_spring = k * (xd - x)
force_friction = b * v
force_total = force_spring + force_friction
acceleration = force_total / m
x = x + v * dt
v = v + acceleration * dt
t = t + dt
xd = xd + speed_of_prime_mover(xd) * dt
end while;
```

The process of transportation is stopped when three conditions are met:

- the coordinate of mover is equal or greater than
`100`

; - the coordinate of box differs from coordinate of mover for no more than
`0.1`

; - the speed of the box is no more than
`0.1`

by absolute value.

The speed of prime mover is determined by `5`

values (i.e. for part of way between `0`

and `20`

metres, then between
`20`

and `40`

and so on to the last between `80`

and `100`

- after which the mover is stopped).

We choose some initial list of speeds, like `1 2 3 2 1`

and calculate transportation time by simulation.
Then we perform about `100`

steps of the Random Search to improve this time.

At each step we randomly choose one of `5`

values and increase or decrease it by random value. Then we run simulation
again and if the result is better, we remember it as the "current best".

We also need to check whether the new list of speeds satisfy the restrictions:

- none of them should be less or equal to
`0`

; - first of them should not exceed
`3`

; - difference between any two consecutive values should not exceed
`3`

.

So at each step we check two things: whether new list of speed is valid (according to restrictions) and whether it improves the overall time. If so, we remember the newly achieved time as a record.

**Input data** contains the number `N`

of random search attempts at the first line.

The second line contains initial list of speeds - `5`

integer values, like `1 1 2 2 1`

.

Next `N`

lines will contain description of a single optimization attempt each in form of two values - the index of
the speed list element which we try to improve and the amount by which it is changed.

**Answer** should contain resulting list of speeds and then the best overall time achieved (with these speeds).
Values should provide `1e-7`

precision or better.

Example:

```
input data:
16
3 3 3 3 1
3 +1.7 // not valid
4 -1.3 // not valid
3 +0.5 // ok
1 +1.1 // ok
4 -1.3 // not valid
3 +0.1 // ok
4 -0.9 // not valid
1 +1.5 // ok
2 +0.5 // ok
4 -1.5 // not valid
1 -0.8 // no improve
1 +0.7 // not valid
1 -0.3 // no improve
1 +0.9 // not valid
2 -0.7 // no improve
1 -1.9 // no improve
answer:
3 5.6 3.5 3.6 1 102.2
```

*Here we try with the first attempt to increase the 3rd speed in a list (0-based indexing) by 1.7 - this gives
it a value of 4.7 but since the next speed is 1 their difference violates restrictions.*

Next attempt is to decrease the 4th speed by 1.3 which makes it negative (-0.3) it is also invalid.

To help understanding these rules the comments are added to each of the attempts on the right.

You need to login to get test data and submit solution.