Algorithms : add 05-advanced_algorithms_and_complexity 03-np-completness

4 files changed, 130 insertions, 0 deletions

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
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/03-np-completness/00_np-completeness.pdf
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;
+}