From 701b6b88ac8258a5c21197bb726825e7592d762b Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Fri, 25 Mar 2022 09:38:27 +0100
Subject: Algorithms : add 05-advanced_algorithms_and_complexity
 03-np-completness

---
 .../03-np-completness/00_np-completeness.pdf       | Bin 0 -> 1171949 bytes
 .../01-gsm_network/gsm_network.cpp                 |  45 +++++++++++++++++++++
 .../02-cleaning_apartment/cleaning_apartment.cpp   |  42 +++++++++++++++++++
 .../03-budget_allocation/budget_allocation.cpp     |  43 ++++++++++++++++++++
 4 files changed, 130 insertions(+)
 create mode 100644 05-advanced_algorithms_and_complexity/03-np-completness/00_np-completeness.pdf
 create mode 100644 05-advanced_algorithms_and_complexity/03-np-completness/01-gsm_network/gsm_network.cpp
 create mode 100644 05-advanced_algorithms_and_complexity/03-np-completness/02-cleaning_apartment/cleaning_apartment.cpp
 create mode 100644 05-advanced_algorithms_and_complexity/03-np-completness/03-budget_allocation/budget_allocation.cpp

diff --git a/05-advanced_algorithms_and_complexity/03-np-completness/00_np-completeness.pdf b/05-advanced_algorithms_and_complexity/03-np-completness/00_np-completeness.pdf
new file mode 100644
index 0000000..7a89a16
Binary files /dev/null and b/05-advanced_algorithms_and_complexity/03-np-completness/00_np-completeness.pdf differ
diff --git a/05-advanced_algorithms_and_complexity/03-np-completness/01-gsm_network/gsm_network.cpp b/05-advanced_algorithms_and_complexity/03-np-completness/01-gsm_network/gsm_network.cpp
new file mode 100644
index 0000000..5eafa18
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/03-np-completness/01-gsm_network/gsm_network.cpp
@@ -0,0 +1,45 @@
+#include <ios>
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+struct Edge {
+    int from;
+    int to;
+};
+
+struct ConvertGSMNetworkProblemToSat {
+    int numVertices;
+    vector<Edge> edges;
+
+    ConvertGSMNetworkProblemToSat(int n, int m) :
+        numVertices(n),
+        edges(m)
+    {  }
+
+    void printEquisatisfiableSatFormula() {
+        // This solution prints a simple satisfiable formula
+        // and passes about half of the tests.
+        // Change this function to solve the problem.
+        cout << "3 2" << endl;
+        cout << "1 2 0" << endl;
+        cout << "-1 -2 0" << endl;
+        cout << "1 -2 0" << endl;
+    }
+};
+
+int main() {
+    ios::sync_with_stdio(false);
+
+    int n, m;
+    cin >> n >> m;
+    ConvertGSMNetworkProblemToSat converter(n, m);
+    for (int i = 0; i < m; ++i) {
+        cin >> converter.edges[i].from >> converter.edges[i].to;
+    }
+
+    converter.printEquisatisfiableSatFormula();
+
+    return 0;
+}
diff --git a/05-advanced_algorithms_and_complexity/03-np-completness/02-cleaning_apartment/cleaning_apartment.cpp b/05-advanced_algorithms_and_complexity/03-np-completness/02-cleaning_apartment/cleaning_apartment.cpp
new file mode 100644
index 0000000..5690be7
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/03-np-completness/02-cleaning_apartment/cleaning_apartment.cpp
@@ -0,0 +1,42 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+struct Edge {
+    int from;
+    int to;
+};
+
+struct ConvertHampathToSat {
+    int numVertices;
+    vector<Edge> edges;
+
+    ConvertHampathToSat(int n, int m) :
+        numVertices(n),
+        edges(m)
+    {  }
+
+    void printEquisatisfiableSatFormula() {
+        // This solution prints a simple satisfiable formula
+        // and passes about half of the tests.
+        // Change this function to solve the problem.
+        cout << "3 2" << endl;
+        cout << "1 2 0" << endl;
+        cout << "-1 -2 0" << endl;
+        cout << "1 -2 0" << endl;
+    }
+};
+
+int main() {
+    ios::sync_with_stdio(false);
+
+    int n, m;
+    cin >> n >> m;
+    ConvertHampathToSat converter(n, m);
+    for (int i = 0; i < m; ++i) {
+        cin >> converter.edges[i].from >> converter.edges[i].to;
+    }
+
+    converter.printEquisatisfiableSatFormula();
+
+    return 0;
+}
diff --git a/05-advanced_algorithms_and_complexity/03-np-completness/03-budget_allocation/budget_allocation.cpp b/05-advanced_algorithms_and_complexity/03-np-completness/03-budget_allocation/budget_allocation.cpp
new file mode 100644
index 0000000..d2bfc51
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/03-np-completness/03-budget_allocation/budget_allocation.cpp
@@ -0,0 +1,43 @@
+#include <ios>
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+struct ConvertILPToSat {
+    vector< vector<int> > A;
+    vector<int> b;
+
+    ConvertILPToSat(int n, int m) : A(n, vector<int>(m)), b(n)
+    {}
+
+    void printEquisatisfiableSatFormula() {
+        // This solution prints a simple satisfiable formula
+        // and passes about half of the tests.
+        // Change this function to solve the problem.
+        cout << "3 2" << endl;
+        cout << "1 2 0" << endl;
+        cout << "-1 -2 0" << endl;
+        cout << "1 -2 0" << endl;
+    }
+};
+
+int main() {
+    ios::sync_with_stdio(false);
+
+    int n, m;
+    cin >> n >> m;
+    ConvertILPToSat converter(n, m);
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < m; j++) {
+        cin >> converter.A[i][j];
+      }
+    }
+    for (int i = 0; i < n; i++) {
+      cin >> converter.b[i];
+    }
+
+    converter.printEquisatisfiableSatFormula();
+
+    return 0;
+}
-- 
cgit v1.1-2-g2b99