Problem 1: Dimension reduction (2017/2018)

While analyzing data and real-world problems we often deal with high dimensional data. They are usually hard to visualize and may even pose a threat to validity of the model, e.g. when multicollinearity is an issue. In such situations, one of the solutions can be applying to the dataset a dimension reduction algorithm, such as PCA or t-SNE.

Let us think about a very naive dimension reduction algorithm, that can be applied to vector data' = [a0, a1, ... , aN-1]. The dimension reduction is achieved by finding the linear combination of the elements of the vector, so that the resulting vector would be of length 4. In general case, one could put fractional weights in the formulas; however, for simplicity let us assume that weights are either 1 or 0, and the elements of the resulting vector have to be the sums of the subsequent elements of the original vector. Since we do not want to lose any information, each element of the original vector should be added to exactly one of the elements of the result vector.

Write a function is_dim_reduction which, given the original vector data of positive integers of length N, and K queries, each of which is a vector of positive integers of length 4, decides for each of the queries whether it is possible that the given query could be the result of such a naive dimension reduction algorithm. For example, for data' = [1,2,3,4,5,6,7,8,9,10]:

Testing program in C++

#include <iostream>
#include <vector>
#include <array>
using namespace std;

// you can add extra includes or auxiliary functions/variables if needed

vector<bool> is_dim_reduction(const vector<int>& data, const vector<array<int,4>>& queries) {
  // write your solution here
  return {};
  }

int main() {

  vector<int> test_data =
    {1,2,3,4,5,6,7,8,9,10};

  vector<array<int,4>> test_queries = {
    {15,6,15,19},
    {16,5,15,19},
    {5,10,19,21},
    {21,7,8,9},
    {21,7,8,19},
    {28,15,9,10},
    {28,8,9,10} 
    };

  vector<bool> expected_result = 
    {true, false, true, false, true, false, true};

  auto result = is_dim_reduction(test_data, test_queries);
  for(auto v: result)
    cout << (v?"YES\n":"NO\n");
  if(result == expected_result)
    cout << "Result correct!\n";
  else
    cout << "Result incorrect!\n";
  return 0;
  }

Testing program in Python

# add your own imports and auxiliary functions if needed

def is_dim_reduction(data, queries):
  # implement your solution here
  return []

test_data = [1,2,3,4,5,6,7,8,9,10]

test_queries = [
  [15,6,15,19],
  [16,5,15,19],
  [5,10,19,21],
  [21,7,8,9],
  [21,7,8,19],
  [28,15,9,10],
  [28,8,9,10] 
  ]
  
expected_result = [True, False, True, False, True, False, True]

my_result = is_dim_reduction(test_data, test_queries)
print(my_result)

if my_result == expected_result:
  print("Result correct!")
else:
  print("Result incorrect!")

Rules