Матч 226, Анализ Эксперимента (ExperimentalAnalyzer)

Дивизион 2, Уровень 2

Проводятся эксперименты, зависящие от нескольких параметров. Результатом эксперимента является значение 0 или 1. Параметр является независимым, если существует такое пороговое значение t, для которого все значения с результатом 0 лежат больше (меньше) него, а с результатом 1 меньше (больше) него.

Имеется массив строк, содержащих результаты экспериментов. Первым числом в каждой строке является результат эксперимента (0 или 1). Далее следуют значения параметров. Необходимо установить, какие параметры в эксперименте являются независимыми.

Класс: ExperimentalAnalyzer

Метод: vector<int> getPredictors(vector<string> data)

Ограничения: data[i] содержит от 3 до 50 символов, data[i] содержит результат эксперимента (0 или 1) и значения параметров (от 0 до 2147483647 включительно), все элементы data[i] содержат одинаковое количество чисел.

Вход. Массив строк data.

Выход. Массив, содержащий индексы независимых параметров. Индексы параметров нумеруются с единицы.

Пример входа

data

{"0 10 20 20 0", "1 20 30 17 98765", "0 10 30 29 1234567", "1 20 40 10 42"}

{"1 220 212 247 764 928 956 946 66 640 983 125 994",

"0 816 835 98 81 783 267 946 584 309 757 876 670"}

Пример выхода

{1, 3}

{}

РЕШЕНИЕ

обработка массива

Для каждого параметра и для каждого исхода (0 или 1) найдем наибольшее и наименьшее его значение. Таким образом, для каждого параметра получим интервалы, в которых находятся его значения для исхода 0 и для исхода 1. Если эти интервалы не пересекаются, то параметр считается независимым. Если в эксперименте в качестве результата присутствует только 0 (или 1), то все параметры считаются зависимыми.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <sstream>

#include <vector>

using namespace std;

class ExperimentalAnalyzer

{

public:

vector<int> getPredictors(vector<string> data)

{

vector<int> res;

int i, j, min[2][51], max[2][51], outcome, value;

for(i = 0; i < 51; i++) min[0][i] = min[1][i] = 2147483647;

memset(max,0,sizeof(max));

for(i = 0; i < data.size(); i++)

{

stringstream in(data[i]);

in >> outcome; j = 0;

while (in >> value)

{

if (value < min[outcome][j]) min[outcome][j] = value;

if (value > max[outcome][j]) max[outcome][j] = value;

j++;

}

}

for(i = 0; i < j; i++)

{

if ((min[0][i] == 2147483647) || (min[1][i] == 2147483647)) continue;

if (!((max[0][i] >= min[1][i]) && (min[0][i] <= max[1][i])))

res.push_back(i+1);

}

return res;

}

};