Algorithms : add 02-data_structures 02-priority_queues_and_disjoint_sets

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
new 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
+