Задача L. Lasso ≡

Условие

Пусть имеется задача регрессии $f(x) = a\cdot x + b \approx y$. Требуется найти коэффициенты регрессии $a$, такие, что $\left|\left\{a_i\ |\ a_i\in a,\,a_i=0\right\}\right|=k,\quad 0 < k \leqslant \left|a\right|=m$. При этом должно выполняться условие $R^2=1-\frac{\sum\limits_{i=1}^n\left(y_i-f(X_i)\right)^2}{\sum\limits_{i=1}^n\left(y_i-\overline{y}\right)^2}\geqslant s$. При решении задачи предполагается использование алгоритма Lasso.

Формат входных данных

Данные для обучения содержатся в файле. Качество модели будет рассчитано на скрытом наборе данных

Первая строка входных данных содержит натуральное число $N$ — количество тестов. В следующих $N$ блоках содержится описание тестов. Первая строка блока содержит целые числа $n$ — количество примеров обучающей выборки, $m$ — размерность пространства, $k$ — необходимое количество нулевых коэффициентов, и вещественное число $s$ — минимальное значение метрики $R^2$. Следующие $n$ строк содержат по $m+1$ вещественному числу — координаты точки пространства и значение целевой переменной $y$.

Формат выходных данных

Решение должно представлять собой текстовый файл содержащий $N$ строк — коэффициенты $a$ и $b$ линейной регрессии разделённые символом пробел.

Примеры тестов

1
10 5 1 0.8
-0.5  -0.26 -0.11 -0.66  0.49 -24.89
 0.08 -0.38  0.6   1.29  0.42  62.2
 0.82  0.12  0.54  1.33 -0.82  47.55
-0.36  0.54 -0.6   0.55 -0.01 -15.96
-0.91 -0.71  0.59  1.0   0.43 -11.11
-0.97 -0.78  0.2  -0.93  1.24 -17.04
 0.29  0.77 -0.87 -0.05 -0.71 -38.97
 0.19 -0.16  1.0   0.63  1.79 188.63
 0.22 -2.38  3.0   0.22 -0.53  23.32
 0.36 -0.84  1.05 -1.06 -0.06  15.31

43.69 0.0 10.48 16.86 46.25 6.39