diff options
17 files changed, 289 insertions, 0 deletions
diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/00_priority_queues_and_disjoint_sets.pdf b/02-data_structures/02-priority_queues_and_disjoint_sets/00_priority_queues_and_disjoint_sets.pdf Binary files differnew file mode 100644 index 0000000..4f9a793 --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/00_priority_queues_and_disjoint_sets.pdf diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/build_heap.cpp b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/build_heap.cpp new file mode 100644 index 0000000..3cb2e91 --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/build_heap.cpp @@ -0,0 +1,63 @@ +#include <iostream> +#include <vector> +#include <algorithm> + +using std::vector; +using std::cin; +using std::cout; +using std::swap; +using std::pair; +using std::make_pair; + +class HeapBuilder { + private: + vector<int> data_; + vector< pair<int, int> > swaps_; + + void WriteResponse() const { + cout << swaps_.size() << "\n"; + for (int i = 0; i < swaps_.size(); ++i) { + cout << swaps_[i].first << " " << swaps_[i].second << "\n"; + } + } + + void ReadData() { + int n; + cin >> n; + data_.resize(n); + for(int i = 0; i < n; ++i) + cin >> data_[i]; + } + + void GenerateSwaps() { + swaps_.clear(); + // The following naive implementation just sorts + // the given sequence using selection sort algorithm + // and saves the resulting sequence of swaps. + // This turns the given array into a heap, + // but in the worst case gives a quadratic number of swaps. + // + // TODO: replace by a more efficient implementation + for (int i = 0; i < data_.size(); ++i) + for (int j = i + 1; j < data_.size(); ++j) { + if (data_[i] > data_[j]) { + swap(data_[i], data_[j]); + swaps_.push_back(make_pair(i, j)); + } + } + } + + public: + void Solve() { + ReadData(); + GenerateSwaps(); + WriteResponse(); + } +}; + +int main() { + std::ios_base::sync_with_stdio(false); + HeapBuilder heap_builder; + heap_builder.Solve(); + return 0; +} diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/01 b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/01 new file mode 100644 index 0000000..ac4e9ed --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/01 @@ -0,0 +1,2 @@ +5 +5 4 3 2 1 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/01.a b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/01.a new file mode 100644 index 0000000..d071298 --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/01.a @@ -0,0 +1,4 @@ +3 +1 4 +0 1 +1 3 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/02 b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/02 new file mode 100644 index 0000000..1df2e06 --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/02 @@ -0,0 +1,2 @@ +5 +1 2 3 4 5 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/02.a b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/02.a new file mode 100644 index 0000000..573541a --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/01-make_heap/tests/02.a @@ -0,0 +1 @@ +0 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/job_queue.cpp b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/job_queue.cpp new file mode 100644 index 0000000..920e7ac --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/job_queue.cpp @@ -0,0 +1,62 @@ +#include <iostream> +#include <vector> +#include <algorithm> + +using std::vector; +using std::cin; +using std::cout; + +class JobQueue { + private: + int num_workers_; + vector<int> jobs_; + + vector<int> assigned_workers_; + vector<long long> start_times_; + + void WriteResponse() const { + for (int i = 0; i < jobs_.size(); ++i) { + cout << assigned_workers_[i] << " " << start_times_[i] << "\n"; + } + } + + void ReadData() { + int m; + cin >> num_workers_ >> m; + jobs_.resize(m); + for(int i = 0; i < m; ++i) + cin >> jobs_[i]; + } + + void AssignJobs() { + // TODO: replace this code with a faster algorithm. + assigned_workers_.resize(jobs_.size()); + start_times_.resize(jobs_.size()); + vector<long long> next_free_time(num_workers_, 0); + for (int i = 0; i < jobs_.size(); ++i) { + int duration = jobs_[i]; + int next_worker = 0; + for (int j = 0; j < num_workers_; ++j) { + if (next_free_time[j] < next_free_time[next_worker]) + next_worker = j; + } + assigned_workers_[i] = next_worker; + start_times_[i] = next_free_time[next_worker]; + next_free_time[next_worker] += duration; + } + } + + public: + void Solve() { + ReadData(); + AssignJobs(); + WriteResponse(); + } +}; + +int main() { + std::ios_base::sync_with_stdio(false); + JobQueue job_queue; + job_queue.Solve(); + return 0; +} diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/01 b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/01 new file mode 100644 index 0000000..398cf52 --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/01 @@ -0,0 +1,2 @@ +2 5 +1 2 3 4 5 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/01.a b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/01.a new file mode 100644 index 0000000..a7444f5 --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/01.a @@ -0,0 +1,5 @@ +0 0 +1 0 +0 1 +1 2 +0 4 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/02 b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/02 new file mode 100644 index 0000000..5c52f5c --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/02 @@ -0,0 +1,2 @@ +4 20 +1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/02.a b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/02.a new file mode 100644 index 0000000..8f6e97f --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/02-job_queue/tests/02.a @@ -0,0 +1,20 @@ +0 0 +1 0 +2 0 +3 0 +0 1 +1 1 +2 1 +3 1 +0 2 +1 2 +2 2 +3 2 +0 3 +1 3 +2 3 +3 3 +0 4 +1 4 +2 4 +3 4 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/merging_tables.cpp b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/merging_tables.cpp new file mode 100644 index 0000000..1bcf468 --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/merging_tables.cpp @@ -0,0 +1,66 @@ +#include <cstdio> +#include <cstdlib> +#include <vector> +#include <algorithm> +#include <iostream> + +using std::cin; +using std::cout; +using std::endl; +using std::max; +using std::vector; + +struct DisjointSetsElement { + int size, parent, rank; + + DisjointSetsElement(int size = 0, int parent = -1, int rank = 0): + size(size), parent(parent), rank(rank) {} +}; + +struct DisjointSets { + int size; + int max_table_size; + vector <DisjointSetsElement> sets; + + DisjointSets(int size): size(size), max_table_size(0), sets(size) { + for (int i = 0; i < size; i++) + sets[i].parent = i; + } + + int getParent(int table) { + // find parent and compress path + } + + void merge(int destination, int source) { + int realDestination = getParent(destination); + int realSource = getParent(source); + if (realDestination != realSource) { + // merge two components + // use union by rank heuristic + // update max_table_size + } + } +}; + +int main() { + int n, m; + cin >> n >> m; + + DisjointSets tables(n); + for (auto &table : tables.sets) { + cin >> table.size; + tables.max_table_size = max(tables.max_table_size, table.size); + } + + for (int i = 0; i < m; i++) { + int destination, source; + cin >> destination >> source; + --destination; + --source; + + tables.merge(destination, source); + cout << tables.max_table_size << endl; + } + + return 0; +} diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/01 b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/01 new file mode 100644 index 0000000..252302b --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/01 @@ -0,0 +1,7 @@ +5 5 +1 1 1 1 1 +3 5 +2 4 +1 4 +5 4 +5 3 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/01.a b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/01.a new file mode 100644 index 0000000..83a8f07 --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/01.a @@ -0,0 +1,5 @@ +2 +2 +3 +5 +5 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/02 b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/02 new file mode 100644 index 0000000..2fd0683 --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/02 @@ -0,0 +1,6 @@ +6 4 +10 0 5 0 3 3 +6 6 +6 5 +5 4 +4 3 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/02.a b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/02.a new file mode 100644 index 0000000..d291c0f --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/03-merging_tables/tests/02.a @@ -0,0 +1,4 @@ +10 +10 +10 +11 diff --git a/02-data_structures/02-priority_queues_and_disjoint_sets/check b/02-data_structures/02-priority_queues_and_disjoint_sets/check new file mode 100755 index 0000000..b73ff99 --- /dev/null +++ b/02-data_structures/02-priority_queues_and_disjoint_sets/check @@ -0,0 +1,38 @@ +#! /bin/bash + +RESET="\033[0m" +RED="\033[0;31m" +GREEN="\033[0;32m" +BROWN="\033[0;33m" + +BIN=/tmp/bin +OUTA=/tmp/_outa +OUTB=/tmp/_outb +GPP_OPTS="-std=c++11 -O2" + +for path in $(find -name \*.cpp | sort); do + src=${path##*/} + dir=${path%/*} + echo -e "${RED}validate $BROWN$dir$RESET/$GREEN$src$RESET" + pushd $dir >/dev/null || exit 1 + echo -e " ${RED}compile $GREEN$src$RESET" && g++ $GPP_OPTS $src -o $BIN || exit 1 + if [ -d tests ]; then + echo -e " ${RED}check $GREEN$src$RESET" + for t in $(find ./tests -name "*[^a~]"|sort); do + if [ -f $t -a -f "$t.a" ]; then + cat $t | $BIN > $OUTA + cat $t.a > $OUTB + cmp $OUTA $OUTB >/dev/null + if [ $? -ne 0 ]; then + echo -e " $BROWN$t$RESET is ${RED}KO$RESET" + else + echo -e " $BROWN$t$RESET is ${GREEN}ok$RESET" + fi + fi + done + else + echo -e " ${RED}no tests$RESET" + fi + popd > /dev/null +done + |