Skip to content

Instantly share code, notes, and snippets.

@zsrinivas
Created October 10, 2016 11:04
Show Gist options
  • Save zsrinivas/fc26c1eb13c56c9246b4b4886bb00e7d to your computer and use it in GitHub Desktop.
Save zsrinivas/fc26c1eb13c56c9246b4b4886bb00e7d to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
struct combinations {
typedef vector<int> combination_t;
bool completed;
int generated;
combinations(int N, int R) : completed(N < 1 || R > N), generated(0), N(N), R(R) {
for (int c = 1; c <= R; ++c)
curr.push_back(c);
}
combination_t next() {
combination_t ret = curr;
completed = true;
for (int i = R - 1; i >= 0; --i) {
if (curr[i] < N - R + i + 1) {
int j = curr[i] + 1;
while (i < R)
curr[i++] = j++;
completed = false;
++generated;
break;
}
}
for (int i = 0; i < ret.size(); ++i)
ret[i]--;
return ret;
}
private:
int N, R;
combination_t curr;
};
int remove_duplicates(bool** matrices, int rows, int cols) {
bool mark[rows];
for (int i = 0; i < rows; ++i) {
mark[i] = false;
}
for (int i = 0; i < rows; ++i) {
if (!mark[i]) {
for (int j = i + 1; j < rows; ++j) {
bool isequal = true;
for (int k = 0; k < cols; ++k) {
if (matrices[i][k] != matrices[j][k]) {
isequal = false;
break;
}
}
if (isequal) {
mark[j] = true;
}
}
}
}
int j = 0;
for (int i = 0; i < rows; ++i) {
if (!mark[i]) {
for (int k = 0; k < cols; ++k) {
matrices[j][k] = matrices[i][k];
}
j++;
}
}
return j;
}
int main() {
int n, m, k;
cin >> n >> m >> k;
bool** matrices = new bool*[k];
for (int i = 0; i < k; ++i) {
matrices[i] = new bool[n * m];
}
for (int i = 0; i < k; ++i) {
for (int j = 0; j < n*m; ++j) {
char c;
cin >> c;
matrices[i][j] = (c == '1');
}
}
k = remove_duplicates(matrices, k, n * m);
if (k == 1) {
cout << 0 << endl;
return 0;
} else if (k == 2) {
cout << 1 << endl;
return 0;
}
int initdiff = 1;
if (k == 3 || k == 4)
initdiff = 2;
else if (k == 5 || k == 6)
initdiff = 3;
for (int diff = initdiff; diff <= 4; ++diff) {
combinations allcombs(n * m, diff);
while(!allcombs.completed) {
vector<int> comb = allcombs.next();
set<long> nums;
bool found = true;
for (int i = 0; i < k; ++i) {
int cnum = 0;
for (int j = 0; j < comb.size(); ++j) {
if (matrices[i][comb[j]])
cnum |= 1 << j;
}
if (nums.find(cnum) != nums.end()) {
found = false;
break;
}
nums.insert(cnum);
}
// cout << nums << endl;
if (found) {
cout << diff << endl;
return 0;
}
}
}
cout << 5 << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment