biObjTree

//
// Created by Vlad Nitu on 16.01.2023.
//

#include <bits/stdc++.h>
#include "Files.h"

using namespace std;


#define MAX_DEPTH 5
#define FMAX 501
#define ll long long
#define mkp make_pair
#define mkt make_tuple
#define lsb(x) (x & -x)

void __print(int x) { cerr << x; }

void __print(long x) { cerr << x; }

void __print(long long x) { cerr << x; }

void __print(unsigned x) { cerr << x; }

void __print(unsigned long x) { cerr << x; }

void __print(unsigned long long x) { cerr << x; }

void __print(float x) { cerr << x; }

void __print(double x) { cerr << x; }

void __print(long double x) { cerr << x; }

void __print(char x) { cerr << '\'' << x << '\''; }

void __print(const char *x) { cerr << '\"' << x << '\"'; }

void __print(const string &x) { cerr << '\"' << x << '\"'; }

void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename T, typename V, typename W>
void __print(const std::tuple<T, V, W> &x) {
    cerr << '{';
    __print(std::get<0>(x));
    cerr << ',';
    __print(std::get<1>(x));
    cerr << ',';
    __print(std::get<2>(x));
    cerr << '}';
}

template<typename T, typename V>
void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}

template<typename T>
void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}

void _print() { cerr << "]\n"; }

template<typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}

#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

int D, label, N = 0, dim = 0, feature;
std::vector<int> labels, xs;
std::vector<std::vector<int>> features;
std::string line;

inline size_t hash_vector(const std::vector<int> &vec) { // SO
    std::size_t seed = vec.size();
    for (auto &i: vec) {
        seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
    return seed;
}

std::unordered_map<size_t, vector<pair<int, int>>> memo[MAX_DEPTH];
bool feats[FMAX];


void reduce(vector<pair<int, int>> &v) { // O(v * log(v)), remove duplicates and keep track (by a single pass) of only the non-dominated Pareto fronts

    sort(v.begin(), v.end());
    vector<pair<int, int>> ans{};

    for (const auto [FP, FN]: v) {
        if (ans.empty())
            ans.push_back({FP, FN});
        else if (FN < ans.back().second)
            ans.push_back({FP, FN});
    }

    swap(v, ans);
}

inline vector<pair<int, int>> combine(vector<pair<int, int>> &l, const vector<pair<int, int>> &r) {

    vector<pair<int, int>> ans{};
    for (int i = 0; i < l.size(); ++i)
        for (int j = 0; j < r.size(); ++j)
            ans.push_back({l[i].first + r[j].first, l[i].second + r[j].second});

    reduce(ans);

    return ans;
}

inline vector<pair<int, int>> solve(int depth, const std::vector<int> &datapoints) {

    vector<pair<int, int>> ans{};

    size_t hash_value = hash_vector(datapoints);

    if (memo[depth].find(hash_value) != memo[depth].end())
        return memo[depth][hash_value];

    if (depth == D - 1) { // D = 1 case

        for (int split = 0; split < dim; ++split)

            if (feats[split]) {

                int a = 0, b = 0, c = 0, d = 0;

                for (const int &index: datapoints) {
                    const std::vector<int> &v = features[index];
                    if (v[split] == 0) {
                        if (labels[index] == 0)
                            a++;
                        else
                            b++;
                    } else {
                        if (labels[index] == 0)
                            c++;
                        else
                            d++;
                    }
                }

                // cand1 (0, 0) -> (a + c, 0)
                // cand2 (0, 1) -> (c, b)
                // cand3 (1, 0) -> (a, d)
                // cand4 (1, 1) -> (0, b + d)

                pair<int, int> candidate1{a + c, 0}, candidate2{c, b}, candidate3{a, d}, candidate4{0, b + d};


                ans.push_back(candidate4);
                ans.push_back(candidate2);
                ans.push_back(candidate3);
                ans.push_back(candidate1);

                reduce(ans);

                if (!ans.empty() && ans[0].first == 0 && ans[0].second == 0)
                    break;
            }

        memo[depth][hash_value] = ans;
        return ans;
    } else {

        for (int split = 0; split < dim; ++split)
            if (feats[split]) {

                feats[split] = false;

                std::vector<int> neg{};
                std::vector<int> pos{};

                for (const int &index: datapoints) {
                    const std::vector<int> &v = features[index];
                    if (v[split] == 0)
                        neg.push_back(index);
                    else
                        pos.push_back(index);
                }

                vector<pair<int, int>> l{};
                vector<pair<int, int>> r{};

                l = solve(depth + 1, neg);
                if (!l.empty())
                    r = solve(depth + 1, pos);

                if (!l.empty() && !r.empty()) {
                    vector<pair<int, int>> combined = combine(l, r);
                    ans.insert(ans.begin(), combined.begin(), combined.end()); // Remove duplicates
                    reduce(ans);
                }
                feats[split] = true;

                if (!ans.empty() && ans[0].first == 0 && ans[0].second == 0)
                    break;
            }
    }

    memo[depth][hash_value] = ans;
    return ans;
}

inline std::vector<int> init() {
    N = (int) features.size();
    dim = (int) features[0].size();

    vector<int> datapoints(N);
    for (int i = 0; i < N; ++i)
        datapoints[i] = i;

    for (int i = 0; i < dim; ++i)
        feats[i] = true;

    return datapoints;
}

inline std::vector<int> read() {
    std::stringstream stringstream;
    std::getline(std::cin, line);
    stringstream << line;
    stringstream >> D;
    stringstream.clear();

    while (std::getline(std::cin, line)) {
        stringstream << line;
        stringstream >> label;
        labels.push_back(label);

        xs = std::vector<int>{};
        while (stringstream >> feature)
            xs.push_back(feature);

        features.push_back(xs);

        stringstream.clear();
    }

    return init();
}

inline void rwFrom(const char *read_filename, const char *write_filename) {
    // Speed-up reading
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    freopen(read_filename, "r", stdin);
    freopen(write_filename, "w", stdout);
}

int main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

//    std::cout << "We are currently in: " << std::filesystem::current_path() << '\n';

    auto start = std::chrono::steady_clock::now();

    rwFrom(Files::anneal_in, Files::anneal_out);
    std::vector<int> datapoints = read();

    vector<pair<int, int>> ans = solve(0, datapoints);


    for (const pair<int, int> &FP_FN: ans)
        cout << FP_FN.first << ' ' << FP_FN.second << '\n';

//    auto end = std::chrono::steady_clock::now();
//
//    std::cout << "Elapsed time: "
//              << std::chrono::duration_cast<std::chrono::seconds>(end - start).count()
//              << " sec";

    return 0;
}