Skip to content

Instantly share code, notes, and snippets.

@boompig

boompig/acm-bankruptcy.cpp

Last active Aug 29, 2015
Embed
What would you like to do?
ACM Solution to the 2012 Europe 'kingdom bankruptcy' problem
#include <iostream>
#include <vector>
#include <bitset>
#include <set>
using namespace std;
#define LOG_LEVEL 0
#define DEBUG(s) { \
if (LOG_LEVEL) { std::cerr << s << endl; } \
}
const int MAX_K = 20;
vector<vector<int> > debtMatrix;
bitset<MAX_K> reachable;
bitset<MAX_K> bankrupt;
set<unsigned long> visited;
bool isBankrupt (int kingdom, int n) {
int score = 0;
for (int i = 0; i < n; i++) {
if (! bankrupt[i]) {
score += debtMatrix[i][kingdom];
}
}
return score < 0;
}
/**
* Count is the number of bits flipped
*/
void DFS(int count, int n) {
visited.insert(bankrupt.to_ulong());
if (count == n - 1) {
// find the last kingdom standing
for (int i = 0; i < n; i++) {
if (! bankrupt[i]) {
reachable[i] = 1;
break;
}
}
return;
}
for (int i = 0; i < n; i++) {
if (! bankrupt[i] && isBankrupt(i, n)) {
bankrupt[i] = 1;
// make sure that we haven't explored this route before
if (visited.find(bankrupt.to_ulong()) == visited.end()) {
DFS(count + 1, n);
}
// undo the op
bankrupt[i] = 0;
}
}
}
int main() {
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
cerr.sync_with_stdio(false);
int T;
cin >> T;
int n, tmp;
for (int t = 0; t < T; t++) {
cin >> n;
debtMatrix.clear();
reachable.reset();
visited.clear();
bankrupt.reset();
for (int i = 0; i < n; i++) {
vector<int> debtRow (n);
for (int k = 0; k < n; k++) {
cin >> debtRow[k];
}
debtMatrix.push_back(debtRow);
}
DFS(0, n);
DEBUG(visited.size());
int j = 0;
//DEBUG("j");
for (int i = 0; i < n; i++) {
if (reachable[i]) {
if (j > 0) cout << " ";
cout << (i + 1);
j++;
}
}
if (j == 0) {
cout << 0;
}
cout << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.