Algorithms : add 05-advanced_algorithms_and_complexity 04-np-completeness

5 files changed, 276 insertions, 0 deletions

diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/00_np_completeness.pdf b/05-advanced_algorithms_and_complexity/04-np-completeness/00_np_completeness.pdf
new file mode 100644
index 0000000..fce9a8a
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/00_np_completeness.pdf
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/01-circuit_design/circuit_design.cpp b/05-advanced_algorithms_and_complexity/04-np-completeness/01-circuit_design/circuit_design.cpp
new file mode 100644
index 0000000..afc1a9f
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/01-circuit_design/circuit_design.cpp
@@ -0,0 +1,81 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+struct Clause {
+    int firstVar;
+    int secondVar;
+};
+
+struct TwoSatisfiability {
+    int numVars;
+    vector<Clause> clauses;
+
+    TwoSatisfiability(int n, int m) :
+        numVars(n),
+        clauses(m)
+    {  }
+
+    bool isSatisfiable(vector<int>& result) {
+        // This solution tries all possible 2^n variable assignments.
+        // It is too slow to pass the problem.
+        // Implement a more efficient algorithm here.
+        for (int mask = 0; mask < (1 << numVars); ++mask) {
+            for (int i = 0; i < numVars; ++i) {
+                result[i] = (mask >> i) & 1;
+            }
+
+            bool formulaIsSatisfied = true;
+
+            for (const Clause& clause: clauses) {
+                bool clauseIsSatisfied = false;
+                if (result[abs(clause.firstVar) - 1] == (clause.firstVar < 0)) {
+                    clauseIsSatisfied = true;
+                }
+                if (result[abs(clause.secondVar) - 1] == (clause.secondVar < 0)) {
+                    clauseIsSatisfied = true;
+                }
+                if (!clauseIsSatisfied) {
+                    formulaIsSatisfied = false;
+                    break;
+                }
+            }
+
+            if (formulaIsSatisfied) {
+                return true;
+            }
+        }
+        return false;
+    }
+};
+
+int main() {
+    ios::sync_with_stdio(false);
+
+    int n, m;
+    cin >> n >> m;
+    TwoSatisfiability twoSat(n, m);
+    for (int i = 0; i < m; ++i) {
+        cin >> twoSat.clauses[i].firstVar >> twoSat.clauses[i].secondVar;
+    }
+
+    vector<int> result(n);
+    if (twoSat.isSatisfiable(result)) {
+        cout << "SATISFIABLE" << endl;
+        for (int i = 1; i <= n; ++i) {
+            if (result[i-1]) {
+                cout << -i;
+            } else {
+                cout << i;
+            }
+            if (i < n) {
+                cout << " ";
+            } else {
+                cout << endl;
+            }
+        }
+    } else {
+        cout << "UNSATISFIABLE" << endl;
+    }
+
+    return 0;
+}
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp
new file mode 100644
index 0000000..70249aa
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/02-plan_party/plan_party.cpp
@@ -0,0 +1,74 @@
+#include <iostream>
+#include <vector>
+
+struct Vertex {
+    int weight;
+    std::vector <int> children;
+};
+typedef std::vector<Vertex> Graph;
+typedef std::vector<int> Sum;
+
+Graph ReadTree() {
+    int vertices_count;
+    std::cin >> vertices_count;
+
+    Graph tree(vertices_count);
+
+    for (int i = 0; i < vertices_count; ++i)
+        std::cin >> tree[i].weight;
+
+    for (int i = 1; i < vertices_count; ++i) {
+        int from, to, weight;
+        std::cin >> from >> to;
+        tree[from - 1].children.push_back(to - 1);
+        tree[to - 1].children.push_back(from - 1);
+    }
+
+    return tree;
+}
+
+void dfs(const Graph &tree, int vertex, int parent) {
+    for (int child : tree[vertex].children)
+        if (child != parent)
+            dfs(tree, child, vertex);
+
+    // This is a template function for processing a tree using depth-first search.
+    // Write your code here.
+    // You may need to add more parameters to this function for child processing.
+}
+
+int MaxWeightIndependentTreeSubset(const Graph &tree) {
+    size_t size = tree.size();
+    if (size == 0)
+        return 0;
+    dfs(tree, 0, -1);
+    // You must decide what to return.
+    return 0;
+}
+
+int main() {
+    // This code is here to increase the stack size to avoid stack overflow
+    // in depth-first search.
+    const rlim_t kStackSize = 64L * 1024L * 1024L;  // min stack size = 64 Mb
+    struct rlimit rl;
+    int result;
+    result = getrlimit(RLIMIT_STACK, &rl);
+    if (result == 0)
+    {
+        if (rl.rlim_cur < kStackSize)
+        {
+            rl.rlim_cur = kStackSize;
+            result = setrlimit(RLIMIT_STACK, &rl);
+            if (result != 0)
+            {
+                fprintf(stderr, "setrlimit returned result = %d\n", result);
+            }
+        }
+    }
+
+    // Here begins the solution
+    Graph tree = ReadTree();
+    int weight = MaxWeightIndependentTreeSubset(tree);
+    std::cout << weight << std::endl;
+    return 0;
+}
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/school_bus.cpp b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/school_bus.cpp
new file mode 100644
index 0000000..26bd942
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/03-school_bus/school_bus.cpp
@@ -0,0 +1,76 @@
+#include <iostream>
+#include <algorithm>
+#include <vector>
+
+using std::vector;
+typedef vector<vector<int> > Matrix;
+
+const int INF = 1e9;
+
+Matrix read_data() {
+    int vertex_count, edge_count;
+    std::cin >> vertex_count >> edge_count;
+    Matrix graph(vertex_count, vector<int>(vertex_count, INF));
+    for (int i = 0; i < edge_count; ++i) {
+        int from, to, weight;
+        std::cin >> from >> to >> weight;
+        --from, --to;
+        graph[from][to] = graph[to][from] = weight;
+    }
+    return graph;
+}
+
+std::pair<int, vector<int> > optimal_path(const Matrix& graph) {
+    // This solution tries all the possible sequences of stops.
+    // It is too slow to pass the problem.
+    // Implement a more efficient algorithm here.
+    size_t n = graph.size();
+    vector<int> p(n);
+    for (size_t i = 0; i < n; ++i)
+        p[i] = i;
+
+    vector<int> best_path;
+    int best_ans = INF;
+
+    do {
+        int cur_sum = 0;
+        bool ok = true;
+        for (size_t i = 1; i < n && ok; ++i)
+            if (graph[p[i - 1]][p[i]] == INF)
+                ok = false;
+            else
+                cur_sum += graph[p[i - 1]][p[i]];
+        if (graph[p.back()][p[0]] == INF)
+            ok = false;
+        else
+            cur_sum += graph[p.back()][p[0]];
+
+        if (!ok)
+            continue;
+        if (cur_sum < best_ans) {
+            best_ans = cur_sum;
+            best_path = p;
+        }
+    } while (std::next_permutation(p.begin(), p.end()));
+
+    if (best_ans == INF)
+        best_ans = -1;
+    for (size_t i = 0; i < best_path.size(); ++i)
+        ++best_path[i];
+    return std::make_pair(best_ans, best_path);
+}
+
+void print_answer(const std::pair<int, vector<int> >& answer) {
+    std::cout << answer.first << "\n";
+    if (answer.first == -1)
+        return;
+    const vector<int>& path = answer.second;
+    for (size_t i = 0; i < path.size(); ++i)
+        std::cout << path[i] << " ";
+    std::cout << "\n";
+}
+
+int main() {
+    print_answer(optimal_path(read_data()));
+    return 0;
+}
diff --git a/05-advanced_algorithms_and_complexity/04-np-completeness/04-reschedule_exams/reschedule_exams.cpp b/05-advanced_algorithms_and_complexity/04-np-completeness/04-reschedule_exams/reschedule_exams.cpp
new file mode 100644
index 0000000..b3ff8eb
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/04-np-completeness/04-reschedule_exams/reschedule_exams.cpp
@@ -0,0 +1,45 @@
+#include <iostream>
+#include <vector>
+#include <string>
+using namespace std;
+
+/*
+  Arguments:
+    * `n` - the number of vertices.
+    * `edges` - list of edges, each edge is a pair (u, v), 1 <= u, v <= n.
+    * `colors` - string consisting of `n` characters, each belonging to the set {'R', 'G', 'B'}.
+  Return value:
+    * If there exists a proper recoloring, return value is a string containing new colors, similar to the `colors` argument.
+    * Otherwise, return value is an empty string.
+*/
+string assign_new_colors(int n, vector<pair<int, int>> edges, string colors) {
+    // Insert your code here.
+    if (n % 3 == 0) {
+        string new_colors;
+        for (int i = 0; i < n; i++) {
+            new_colors.push_back("RGB"[i % 3]);
+        }
+        return new_colors;
+    } else {
+        return "";
+    }
+}
+
+int main() {
+    int n, m;
+    cin >> n >> m;
+    string colors;
+    cin >> colors;
+    vector<pair<int, int> > edges;
+    for (int i = 0; i < m; i++) {
+        int u, v;
+        cin >> u >> v;
+        edges.push_back(make_pair(u, v));
+    }
+    string new_colors = assign_new_colors(n, edges, colors);
+    if (new_colors.empty()) {
+        cout << "Impossible";
+    } else {
+        cout << new_colors << endl;
+    }
+}