Problem E
Gradient Descent
The goal is to minimize a function $f(x)$ by changing $x$, where $x$ is usually a scalar or a vector. In machine learning, $x$ often represents the parameters of the learning model, and $f$ represents the error function (such as squared error).
The gradient descent method uses $f’$ (the first derivative of $f$). If $x$ is a vector, then $f’$ is a vector of partial derivatives, so that
\[ f’_ i(x) = \frac{\partial f}{\partial x_ i}. \]With an initial guess $x_0$, gradient descent repeatedly applies the following rule:
\[ x_{t+1} \leftarrow x_ t  \alpha f’(x_ t) \]for a userchosen parameter $\alpha $, called the step size. In this manner, each initial $x_0$ will eventually lead to a (local) minimum of the function.
For this problem, implement gradient descent in an interactive setting. Your submission queries the grader by proposing different values of $x$, and for each $x$ proposed it receives back two pieces of information: the values $f(x)$ and $f’(x)$.
Input
Your submission is run interactively, meaning that it determines when to quit (within the time limit). Initially your submission reads three lines:

an integer $d$ ($1 \le d \le 10$) representing the dimension of the parameter space,

a list $L$ of $d$ real numbers representing the least values of the parameter space, and

a list $G$ of $d$ real numbers representing the greatest values of the parameter space.
The values of $L$ and $G$ are all in the range $[1\, 000, 1\, 000]$. After this, for every query $x$ your submission produces, the grader responds with two lines:

a single real number representing $f(x)$, and

a list of $d$ real numbers representing $f’(x)$.
Additionally, the following guarantees hold:

All real numbers in the input have at most $6$ digits after the decimal point.

Every value of $f(x)$ is in the range $[1, 10^6]$.

The function $f$ is continuous and differentiable in the ranges given.
Output
The output of your submission must be one line per query $x$, each line containing $d$ real numbers. The real numbers must be in the bounds given ($L$ and $G$) or the submission is considered incorrect. Your submission may make up to $10\, 000$ queries per test case. Since this is an interactive problem, your submission should flush its output buffer with every query (e.g. cout << flush in C++, or sys.stdout.flush() in Python).
Scoring
For each test case, the interactive validator keeps track of the lowest value $f(x)$ observed for any query $x$ your submission produces. Let this value be called $p$, and let the judge’s minimum value of $f$ be called $j$. The score your submission receives is
\[ s = 100 \left(1  \frac{p  j}{j}\right) \]and is clamped to the range $[0, 100]$. If your submission makes too many queries, no queries, or an incorrect query, then the submission is judged as incorrect.
The total score your submission gets is the average of all $s$ over all hidden test cases.