diff options
Diffstat (limited to '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 Binary files differnew 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; + } +} |