Задача A. Метод скользящего среднего

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задан временной ряд {yt}nt=1. Требуется написать программу, вычисляющую сглаженный ряд {hatyt}nm/2t=m/2, где m — ширина интервала сглаживания.

Формат входного файла

Первая строка входных данных содержит два целых числа n и m. Следующая строка содержит n вещественных чисел — уровни ряда yt.

Формат выходного файла

Единственная строка выходного файла должна содержать уровни сглаженного ряда hatyt с точностью не менее трёх знаков после запятой.

Ограничения

1 < n < 105

3 ⩽ m ⩽ 15

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9 3
5 2 5 5 8 5 5 2 5
4 4 6 6 6 4 4

Задача B. Метод скользящего взвешенного среднего

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задан временной ряд {yt}nt=1. Требуется написать программу, вычисляющую сглаженный ряд {hatyt}nm/2t=m/2 с использованием весов {wi}mi=1 для расчёта среднего, где m — ширина интервала сглаживания.

Формат входного файла

Первая строка входных данных содержит два целых числа n и m. Далее следуют m целых чисел — веса wi. Последняя строка содержит n вещественных чисел — уровни ряда yt.

Формат выходного файла

Единственная строка выходного файла должна содержать уровни сглаженного ряда hatyt с точностью не менее трёх знаков после запятой.

Ограничения

1 < n < 105

3 ⩽ m ⩽ 15

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9 3
1 2 1
5 1 5 5 9 5 5 1 5
3 4 6 7 6 4 3

Задача C. Выделение тренда

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Пусть задан временной ряд {yt}nt=1. Требуется написать на языке Python функцию, вычисляющую коэффициенты функции тренда h(t)=mai(t).

def find_fit(x, y, f) # returns array of regression coefficients

Код решения должен содержать только определение и реализацию функции. Он не должен ничего выводить.

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

x, y — одномерные массивы типа np.ndarray. f — функция одного аргумента, возвращающая список значений функций gi, т.е. f(t)≡{gi(t)}mi=1.

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

Функция должна возвращать единственный np.ndarray массив — коэффициенты ai.

Ограничения

1 < n < 103

1 < m ⩽ 5

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

Стандартный вход Стандартный выход
1
x = np.array([1, 2, 3, 4, 5])
y = np.array([2, 3, 5, 7, 11])
find_fit(x, y, lambda x: np.array((1, x)))
        
-1 2.2

Задача D. Автокорреляция

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задан временной ряд Yn1={yt}nt=1. Требуется написать программу, вычисляющую значения коэффициентов автокорреляции Пирсона rl=corr(Ynl1, Ynl), l=1,m.

Формат входного файла

Первая строка входных данных содержит целые числа n и m — длину ряда и максимальное значение задержки. Вторая строка входного файла содержит n вещественных чисел — временной ряд.

Формат выходного файла

Выходной файл должен содержать m вещественных чисел — значения коэффициента автокорреляции с точностью не менее трёх знаков после запятой.

Ограничения

2 ⩽ m < n ⩽ 103

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 2
1 1 2 2 1 1 2 2 1 1
0.1 -1

Задача E. Экспоненциальное сглаживание

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задан временной ряд {yt}nt=1. Требуется написать программу, вычисляющую сглаженный ряд с использованием экспоненциального сглаживания.

Формат входного файла

Первая строка входных данных содержит числа n и α — длину ряда и параметр сглаживания соответственно. Далее следуют n вещественных чисел — уровни ряда yt.

Формат выходного файла

Единственная строка выходного файла должна содержать уровни сглаженного ряда hatyt с точностью не менее трёх знаков после запятой.

Ограничения

1 < n ⩽ 105

0 <α< 1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9 0.5
1 2 2.5 0 2 2.5 0 2 2.5
1 1.5 2 1 1.5 2 1 1.5 2

Задача F. Двойное экспоненциальное сглаживание

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задан временной ряд {yt}nt=1. Требуется написать программу, вычисляющую сглаженный ряд с использованием двойного экспоненциального сглаживания.

Формат входного файла

Первая строка входных данных содержит числа n, α и β — длину ряда, параметры сглаживания данных и тренда соответственно. Далее следуют n вещественных чисел — уровни ряда yt.

Формат выходного файла

Единственная строка выходного файла должна содержать уровни сглаженного ряда hatyt с точностью не менее трёх знаков после запятой.

Ограничения

1 < n ⩽ 105

0 <α,β< 1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9 0.5 0.5
1 3 5 7 9 11 13 15 17
1 3 5 7 9 11 13 15 17

Задача G. Тройное экспоненциальное сглаживание

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задан временной ряд {yt}nt=1. Требуется написать программу, вычисляющую сглаженный ряд с использованием тройного экспоненциального сглаживания (с аддитивной сезонностью).

Формат входного файла

Первая строка входных данных содержит числа n, α, β, γ, L — длину ряда, параметры сглаживания данных, тренда, сезонности и период сезонности соответственно. Далее следуют n вещественных чисел — уровни ряда yt.

Формат выходного файла

Единственная строка выходного файла должна содержать уровни сглаженного ряда hatyt с точностью не менее трех знаков после запятой.

Ограничения

1 < L < n ⩽ 105

0 <α,β,γ< 1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9 0.5 0.5 0.5 3
1 3 5 7 9 11 13 15 17
1.0 2.5 3.955 5.949 8.124 10.032 11.964 14.0139 16.0205

Задача H. Regression residuals bootstrap

Входной файл:Стандартный вход   Ограничение времени:10 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Требуется написать на языке Python функцию, вычисляющую среднее и дисперсию коэффициентов регрессии с использованием бутсрэппинга остатков регрессии (Resampling residuals)

def bootstrap(X : np.ndarray, y : np.ndarray, reg : Model, n : int):
    '''Calculates mean and variance of regression coeffitients using residuals bootstrapping.
    X - explanatory variable values
    y - response variable values
    reg - Model class object
    n - number of bootstrap cycles

    Outputs two np.ndarray values -- mean and variance respectively'''
    pass

Класс Model имеет следующий интерфейс

class Model:
    '''Represents some regression model'''

    params : np.ndarray # Current regression coeffitients
    error : np.ndarray # Current regression residuals
    y : np.ndarray # Fitted values

    def initialize(self, X : np.ndarray, y : np.ndarray):
        '''Initializes regression model. Populates params, error and y attributes.'''
        pass

    def refit(self, new_y : np.ndarray):
        '''Refits model, invalidates params attribute.'''
        pass

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

Функция должна возвращать два np.ndarray массива — среднее и дисперсию коэффициентов регрессии с точностью не менее трёх знаков после запятой.

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

Стандартный вход Стандартный выход
1
X = np.array([[1, 1], [1, 2], [1, 3], [1, 4], [1, 5]])
y = np.array([1, 2, 3, 4, 5])
bootstrap(X, y, LinearRegression(), 10)
        
[0 1], [0 0]

Задача I. ARIMA

Входной файл:input.txt   Ограничение времени:3 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задан временной ряд {yt}nt=1. Требуется написать программу, вычисляющую прогноз этого ряда — значение yn+1 с помощью модели авторегрессии ARIMA(m, k, 0).

Формат входного файла

Первая строка входных данных содержит числа n, m, k — длину ряда, глубину авторегрессии и порядок разностей временного ряда соответственно. Далее следуют n вещественных чисел — уровни ряда yt.

Формат выходного файла

Выходной файл должен содержать единственное число — прогноз hatyn+1 с точностью не менее четырех знаков после запятой.

Ограничения

1 < n ⩽ 105

1 ⩽ m, k ⩽ 5

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9 2 1
2 3 4 6 9 14 22 35 56
90

Задача J. Байесовский классификатор

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задано вещественное пространство Rn. Требуется написать программу, классифицирующую точки с использованием байесовского классификатора B(boldsymbolx)=underseti=0,m1operatornamearg max(πifNk(boldsymbolμi, boldsymbolΣi)(boldsymbolx)m1j=0,i≠ jλi,j), где m — количество классов, πi — априорная вероятность класса, fNk(boldsymbolμi, boldsymbolΣi) — функция плотности многомерного нормального распределения Nk(boldsymbolμi, boldsymbolΣi) со средним boldsymbolμi и матрицей ковариации boldsymbolΣi, λi,j — штраф за ошибочною классификацию класса i в качестве класса j.

Формат входного файла

Первая строка входного файла содержит натуральные числа n, m, k, l — размерность пространства, количество классов, количество элементов обучающей и тестовой выборок соответственно. Далее следуют значения матрицы λm строк по m натуральных чисел. Далее следуют k строк обучающей выборки в формате xi,0, xi,1, …, xi,n1, ci, где xi,j вещественные числа — координаты точки i, ci{0,1,…,n1} — класс точки. Последние l строк содержат по n вещественных чисел — координаты точек тестовой выборки.

Формат выходного файла

Выходной файл должен содержать l целых чисел — предсказанные классы точек тестовой выборки.

Ограничения

n{2, 3}

2 ⩽ m ⩽ 9

2 ⩽ k, l ⩽ 103

1 ⩽ λi,j ⩽ 5

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 2 6 2
0 1
1 0
1 1 0
1 2 0
2 1 0
-1 -1 1
-1 -2 1
-2 -1 1
2 2
-2 -2
0 1

0.621s 0.014s 31