Hello, Codeforces!

Text may have a lot of mistakes, but i really tried very hard to make my post understandable.

set<pair<int, int>> candidates;
void add(int i, int j) {
    if (i >= n || j >= n) return;
    candidates.insert({i, j}); //IMPORTANT, code should comapre not i, j pairs but fractions a[i]/b[j]
}

...

candidates.insert({0, 0});
for (int i = 0; i < k; ++i) {
    auto [x, y] = *candidates.begin();
    candidates.erase(candidates.begin());
    add(x + 1, y);
    add(x, y + 1);
auto [x, y] = *candidates.begin();
int g = __gcd(a[x], b[y]);
x = a[x] / g;
y = b[y] / g;
cout << x << '/' << y;

It can be imagined as a weighted directed graph at $$$n^2$$$ vertexes where edge $$$(i, j) \rightarrow (k, l)$$$ exists if $$$(i, j) \leq (k, l)$$$, and edge weight $$$w= (k, l) - (i, j)$$$. Then if you run Dijkstra on this graph, it will pass all the fractions in sorted order. Then the transition from the vertex $$$(i, j)$$$ to vertex $$$(i+ 1, j)$$$ it will be no worse than any transition from the vertex $$$(i, j)$$$ to vertex $$$(i+ k, j), 0 < k$$$

Every time we get the $$$i$$$-th element in the sorted array, we remove 1 element from the candidates and add no more than 2 new ones. We get that time complexity $$$O(k*logk)$$$

Every time we get the $$$i$$$-th element in the sorted array, we remove 1 element from the candidates and add no more than 2 new ones. Since each bad pair can only meet in one pair $$$(cnt_x, cnt_y)$$$, we will process each bad pair no more than once. We get that time complexity $$$O(k*logk)$$$

The milk tea in China is very delicious. There are many binary ("either-or") options for customizing a milk tea order, such as:

"with ice" OR "no ice" "with sugar" OR "no sugar" "with bubbles" OR "no bubbles" "with pudding" OR "no pudding" and so on. A customer's preferences for their milk tea can be represented as a binary string. For example, using the four properties above (in the order they are given), the string 1100 means "with ice, with sugar, no bubbles, no pudding".

Today, Shakti is on duty to buy each of his N friends a milk tea, at a shop that offers P binary options. But after collecting everyone's preferences, Shakti found that the order was getting too complicated, so Shakti has decided to buy the same type of milk tea for everyone. Shakti knows that for every friend, for every preference that is not satisfied, they will complain once. For example, if two of the friends have preferences for types 101 and 010, and Shakti chooses type 001, then the first friend will complain once and the second friend will complain twice, for a total of three complaints.

Moreover, there are M different forbidden types of milk tea that the shop will not make, and Shakti cannot choose any of those forbidden types.

What is the smallest number of complaints that Shakti can get? $$$1 \leq N \leq 100, 1 \leq P \leq 100, 0 \leq M \leq min(100, 2^P - 1)$$$.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

/*
⣿⣿⣷⡁⢆⠈⠕⢕⢂⢕⢂⢕⢂⢔⢂⢕⢄⠂⣂⠂⠆⢂⢕⢂⢕⢂⢕⢂⢕⢂
⣿⣿⣿⡷⠊⡢⡹⣦⡑⢂⢕⢂⢕⢂⢕⢂⠕⠔⠌⠝⠛⠶⠶⢶⣦⣄⢂⢕⢂⢕
⣿⣿⠏⣠⣾⣦⡐⢌⢿⣷⣦⣅⡑⠕⠡⠐⢿⠿⣛⠟⠛⠛⠛⠛⠡⢷⡈⢂⢕⢂
⠟⣡⣾⣿⣿⣿⣿⣦⣑⠝⢿⣿⣿⣿⣿⣿⡵⢁⣤⣶⣶⣿⢿⢿⢿⡟⢻⣤⢑⢂
⣾⣿⣿⡿⢟⣛⣻⣿⣿⣿⣦⣬⣙⣻⣿⣿⣷⣿⣿⢟⢝⢕⢕⢕⢕⢽⣿⣿⣷⣔
⣿⣿⠵⠚⠉⢀⣀⣀⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⢕⢕⢕⢕⢕⢕⣽⣿⣿⣿⣿
⢷⣂⣠⣴⣾⡿⡿⡻⡻⣿⣿⣴⣿⣿⣿⣿⣿⣿⣷⣵⣵⣵⣷⣿⣿⣿⣿⣿⣿⡿
⢌⠻⣿⡿⡫⡪⡪⡪⡪⣺⣿⣿⣿⣿⣿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃
⠣⡁⠹⡪⡪⡪⡪⣪⣾⣿⣿⣿⣿⠋⠐⢉⢍⢄⢌⠻⣿⣿⣿⣿⣿⣿⣿⣿⠏⠈
⡣⡘⢄⠙⣾⣾⣾⣿⣿⣿⣿⣿⣿⡀⢐⢕⢕⢕⢕⢕⡘⣿⣿⣿⣿⣿⣿⠏⠠⠈
⠌⢊⢂⢣⠹⣿⣿⣿⣿⣿⣿⣿⣿⣧⢐⢕⢕⢕⢕⢕⢅⣿⣿⣿⣿⡿⢋⢜⠠⠈
⠄⠁⠕⢝⡢⠈⠻⣿⣿⣿⣿⣿⣿⣿⣷⣕⣑⣑⣑⣵⣿⣿⣿⡿⢋⢔⢕⣿⠠⠈
⠨⡂⡀⢑⢕⡅⠂⠄⠉⠛⠻⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢋⢔⢕⢕⣿⣿⠠⠈
⠄⠪⣂⠁⢕⠆⠄⠂⠄⠁⡀⠂⡀⠄⢈⠉⢍⢛⢛⢛⢋⢔⢕⢕⢕⣽⣿⣿⠠⠈
*/
#define all(a) a.begin(), a.end()
#define FNAME ""
#define int ll
typedef pair<int, int> pii;
#define _ << ' ' <<
#define vec vector
const bool DEBUG = true;

#ifndef HOME
#define err \
    if (0) cerr
#else
#define err \
    if (DEBUG) cerr
#endif

#ifdef int
const int INF = 2e16;
#else
const int INF = 2e9;
#endif
mt19937 gen(time(0));
//END

set<pii> st;
const int MAXN = 1e5;
vec<int> t[MAXN];
int lst = 0;
vec<int> cnt;
int n;
void add(vec<int> &v) {
    t[lst] = v;
    int tmp = 0;
    int sz = v.size();
    for (int i = 0; i < sz; ++i) {
        if (v[i]) {
            tmp += n - cnt[i];
        } else {
            tmp += cnt[i];
        }
    }
    st.insert({tmp, lst});
    lst++;
}
void solve() {
    //code here
    
    int m, p;
    cin >> n >> m >> p;
    
    cnt.assign(p, 0);
    lst = 0;
    st.clear();


    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < p; ++j) {
            int x = s[j] - '0';
            cnt[j] += x;
        }
    }
    set<vec<int>> usd;
    for (int i = 0; i < m; ++i) {
        vec<int> v(p);
        for (int j = 0; j < p; ++j) {
            char x;
            cin >> x;
            if (x == '1') v[j] = 1;
        }
        usd.insert(v);
    }
    vec<int> init(p);
    for (int i = 0; i < p; ++i) {
        if (cnt[i] > n - cnt[i]) {
            init[i] = 1;
        }
    }
    add(init);
    set<vec<int>> myusd;
    while (!st.empty()) {
        auto [x, i] = *st.begin();
        st.erase(st.begin());
        vec<int> v = t[i];
        if (usd.count(v) == 0) {
            cout << x;
            return;
        }
        myusd.insert(v);
        for (int i = 0; i < p; ++i) {
            v[i] ^= 1;
            if (myusd.count(v) == 0) {
    
                add(v);
            }
            v[i] ^= 1;
        }
    }
//    assert(0);


    //
}

signed main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
    //freopen("input.txt", "w", stdout);
#else
    if (FNAME != "") {
        freopen(FNAME ".in", "r", stdin);
        freopen(FNAME ".out", "w", stdout);
    }
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
        cin >> tt;
    for (int req = 0; req < tt; ++req) {
        unsigned start = clock();
        cout << "Case #" << req + 1 << ": ";
        solve();
        cout << '\n';
        unsigned end = clock();
        cerr << "WorkTime: " << (end - start) / (double) CLOCKS_PER_SEC << '\n';
    }
}