ExperimentalAnalyzer

SRM 226 · 2005-01-05 · by the_one_smiley

SRM 226 · 2005-01-05 · by the_one_smiley · Simple Math, String Parsing

Show categories

Class Name: ExperimentalAnalyzer

Return Type: int[]

Method Name: getPredictors

Arg Types: (vector<string>)

Problem Statement

You have collected data from a research study. Each experiment in this study has its own set of values for the relevant variables and an outcome of either 0 or 1. You wish to analyze the data to determine which variables can independently predict the outcome using a simple threshold. In this problem, a variable v is an independent predictor if there exists a threshold t such that every experiment with v less than or equal to t has the same outcome, every experiment with v greater than t has the other outcome, and both outcomes are each attained by at least one experiment (otherwise, the research study should probably be redesigned).

Write a class ExperimentalAnalyzer with a method getPredictors that takes a String[] data containing the outcome and variable values for each experiment and returns a int[] containing the one-based indices of all the independent predictors, sorted in increasing order. Each element of data corresponds to one experiment and will contain its outcome (either 0 or 1) followed by its list of variable values (which are non-negative integers). The value list for each experiment will be arranged in the same order, with the value for the first variable immediately following the outcome.

Notes

If all the experiments have identical outcomes, there can be no independent predictors.

Constraints

data will contain between 2 and 50 elements, inclusive.
Each element of data will contain between 3 and 50 characters, inclusive.
Each element of data will contain an outcome (0 or 1) followed by one or more variable values (integers between 0 and 2147483647 inclusive, with no extra leading zeroes), all separated by single spaces.
Each element of data will contain the same number of variable values.

Examples

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

There are two experiments with outcome 0 and two with outcome 1. Variable 1 (the first column after the outcome) is an independent predictor because the experiments with outcome 0 have values of 10 or less, while experiments with outcome 1 have values greater than 10. Variable 2 is not an independent predictor because two experiments with the same value have different outcomes. Variable 3 is an independent predictor, but unlike Variable 1, the experiments with outcome 1 have the smaller values. Variable 4 is not an independent predictor since there is no threshold that can separate the values for the different outcomes.

{
"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"}
Returns: { 1,  2,  3,  4,  5,  6,  8,  9,  10,  11,  12 }

With only two experiments with distinct outcomes, a variable will be an independent predictor unless it has the same value in both experiments.

{"1 8 5 1 6 1 8 5 1 4 9 3 4 5 4 9 2 8","0 9 8 4 1 5 1 8 6 9 1 6 4 1 0 3 7 6","1 5 7 0 5 3 9 1 3 4 2 1 6 5 8 1 1 2","0 9 5 3 0 9 7 9 7 2 5 9 7 5 0 4 9 0","0 9 5 4 2 6 1 6 7 1 4 8 2 1 1 5 7 0","0 9 6 3 4 9 0 9 9 1 6 0 4 9 1 7 5 2","0 9 7 7 0 8 6 7 6 1 4 9 2 8 0 9 7 8","1 8 6 7 9 3 9 0 3 2 1 4 0 6 7 9 4 4","1 0 2 2 5 1 8 2 2 0 3 1 8 7 5 9 1 6","1 3 7 0 7 3 9 3 7 2 2 7 7 7 5 4 0 3","1 3 9 8 8 4 9 4 0 0 9 1 2 5 6 1 2 8","1 7 3 7 9 2 8 3 2 5 8 2 9 3 5 0 4 2","0 9 7 3 2 9 5 8 9 1 5 7 6 6 2 0 7 3","0 9 9 5 4 8 4 9 9 1 3 4 5 4 3 9 5 2","1 8 1 2 8 0 8 4 1 3 8 8 0 8 8 9 1 7","1 0 4 6 5 0 8 0 3 5 8 5 3 7 7 3 1 1","0 9 4 0 1 5 4 7 2 3 8 0 8 3 1 0 7 0","0 9 1 0 3 5 2 8 3 6 1 5 6 5 3 0 7 4","1 5 3 1 9 2 9 3 1 1 2 6 6 9 4 3 3 9","0 9 2 6 1 5 1 9 7 6 9 4 1 8 2 3 6 0","1 8 2 3 9 2 8 2 2 8 0 9 6 6 9 1 4 2","0 9 2 3 3 6 0 7 3 5 9 8 0 0 3 7 6 8"}
Returns: { 1,  4,  5,  6,  7,  14,  16 }

{"1 8 2 0 3 1 1 7 0 0 7 3 6 3 7 9 1 0 6 4 2 7 0 1 8","1 4 3 2 5 2 3 2 1 7 6 1 5 7 8 1 7 0 3 3 1 9 2 1 6","0 0 6 1 9 9 6 2 1 2 1 7 1 2 3 4 5 1 0 5 9 9 1 7 0","1 9 3 7 5 4 3 6 7 5 9 1 3 7 4 5 2 0 7 2 2 9 4 0 8","1 8 1 5 0 3 0 8 1 3 1 1 3 8 4 7 2 0 5 7 0 3 2 7 6","1 3 9 4 3 3 2 2 1 9 5 2 8 6 8 8 8 0 2 3 1 1 4 9 4","0 1 6 3 8 5 4 8 9 6 6 8 2 7 1 6 6 2 0 7 9 6 0 0 0","1 6 3 9 0 4 3 3 4 9 8 2 4 5 6 3 2 0 3 3 5 6 9 7 6","0 1 0 1 7 9 4 2 3 7 8 8 1 0 3 3 9 8 9 4 9 5 5 3 1","1 5 3 8 2 0 0 4 5 6 0 0 9 0 6 1 3 0 8 7 2 1 1 6 2","0 1 5 4 9 6 6 0 1 6 5 8 0 8 0 8 9 2 8 3 9 5 1 4 0","0 1 4 7 8 6 6 0 9 1 1 9 1 2 3 1 6 7 5 2 8 7 9 4 0","0 1 2 6 9 5 4 1 0 3 8 8 2 4 3 9 5 3 1 3 8 1 3 8 1","1 6 8 1 6 4 3 9 3 7 3 4 3 7 4 4 8 0 3 7 0 2 1 0 9","1 2 5 2 2 3 2 5 6 5 5 0 6 5 4 6 3 0 5 0 0 7 3 5 2","0 1 1 3 7 8 4 0 0 4 6 9 0 2 1 1 9 5 6 2 8 2 5 7 0","0 1 7 4 9 6 5 4 8 3 9 8 0 7 0 7 0 8 4 6 9 7 9 7 1","1 3 2 9 3 0 0 4 8 8 4 2 9 0 6 5 0 0 9 0 3 2 8 3 3","0 0 3 0 9 9 6 3 4 0 4 7 0 0 1 2 7 4 0 8 9 8 9 0 1","0 0 0 5 7 8 4 5 2 8 2 9 2 8 1 4 8 6 2 2 9 2 6 7 0","1 6 7 3 4 4 1 6 8 0 3 3 8 2 5 7 7 0 1 6 4 6 4 9 3","1 3 1 1 3 0 2 7 6 4 3 0 9 5 7 4 9 0 9 4 0 6 5 8 7","1 6 4 4 2 2 2 1 4 1 6 2 8 9 7 6 9 0 4 9 3 4 9 6 4","0 1 1 0 9 8 7 5 1 7 7 9 0 9 0 1 5 2 6 7 9 5 8 3 1","1 3 9 5 5 2 3 0 4 9 8 2 4 3 4 4 1 0 0 1 0 7 0 9 2","0 1 3 3 9 7 7 3 6 0 7 9 0 0 2 7 8 7 7 7 8 8 3 4 0","1 2 2 0 5 4 3 6 9 0 9 4 6 9 6 8 6 0 6 0 2 9 8 5 9","0 1 3 7 7 5 4 0 5 4 2 9 0 8 1 7 4 8 5 1 8 5 7 8 0","1 5 8 9 3 1 2 9 5 3 1 0 4 7 5 1 4 0 9 2 1 6 1 6 8","0 0 1 6 9 8 7 0 7 2 2 6 0 2 2 6 7 1 3 0 8 8 7 9 1","0 0 5 6 9 7 4 4 3 0 2 5 1 2 3 2 2 1 4 2 9 1 0 9 0","0 0 9 6 7 7 6 7 8 5 8 5 2 9 3 0 1 5 8 7 9 3 8 2 1","1 3 1 2 5 1 0 9 4 2 3 0 5 8 7 4 3 0 1 2 3 4 9 2 9","1 3 2 3 3 0 2 8 6 3 3 1 9 8 6 4 2 0 4 2 6 5 7 4 2","0 1 3 9 7 8 4 7 0 6 5 9 1 6 2 4 0 2 0 3 8 4 4 5 0","0 1 8 4 9 9 5 4 7 9 8 5 0 5 0 4 6 6 6 2 8 9 6 1 0","1 8 8 0 5 1 3 7 6 3 4 0 4 1 5 8 2 0 9 8 2 6 1 6 7","1 8 5 1 1 1 1 4 5 9 5 2 5 7 9 2 5 0 2 0 2 6 6 9 2","0 1 5 2 7 8 6 0 0 3 3 8 0 1 2 3 2 3 4 0 8 8 4 7 0","0 1 2 8 8 7 4 0 2 9 3 5 0 1 2 4 2 5 9 7 9 7 6 3 1","1 2 9 5 3 3 0 3 5 4 5 3 4 7 7 1 5 0 7 9 2 0 3 1 4","1 2 5 7 4 1 0 4 9 8 6 1 4 9 7 2 8 0 3 7 1 3 6 5 7","0 0 5 2 7 6 4 3 4 8 3 9 2 6 3 1 5 3 8 7 8 5 9 8 1"}
Returns: { 1,  4,  5,  6,  11,  12,  14,  17,  20,  24 }

{"0 72 9 1 15 49 20 72 68 20 43 39 81 27 88","0 72 28 81 49 33 63 60 77 53 45 27 37 10 85","1 36 83 17 0 93 71 48 21 93 17 74 88 93 4","0 88 78 37 13 21 56 45 81 67 58 0 0 20 64","0 71 70 20 94 24 5 72 21 62 73 9 69 12 51","0 65 16 99 55 55 53 39 65 59 59 37 53 22 46","1 59 10 79 0 90 55 18 13 23 20 81 97 89 30","1 59 82 47 0 92 63 34 45 78 9 73 92 84 22","0 81 56 77 15 3 40 90 46 71 44 87 66 20 52","0 88 51 31 76 50 27 39 38 15 64 5 20 26 96","0 82 18 0 39 35 91 81 33 3 31 50 2 20 91","0 78 32 62 3 40 8 9 68 60 45 25 59 23 70"}
Returns: { 1,  4,  5,  10,  12,  13,  14 }

15)

{
"0 1944914038 1696137778 1525367830",
"0 1547932733 1185820653 1500052399",
"0 230149443 1358715189 501418065",
"0 1676118083 1499656529 2103271593",
"0 1441540020 1189300515 1544659186"}
Returns: { }

All the experiments have outcome 0, so there are no independent predictors.

Submissions are judged against all 50 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ExperimentalAnalyzer with a public method vector<int> getPredictors(vector<string> data) · 50 test cases · 2 s / 256 MB per case