Algorithms : add 01-algorithmic_toolbox 03-divide_and_conquer

25 files changed, 236 insertions, 0 deletions

diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/00_divide_and_conquer.pdf b/01-algorithmic_toolbox/03-divide_and_conquer/00_divide_and_conquer.pdf
new file mode 100644
index 0000000..0d4a583
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/00_divide_and_conquer.pdf
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp
new file mode 100644
index 0000000..c93e2cf
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/binary_search.cpp
@@ -0,0 +1,36 @@
+#include <iostream>
+#include <cassert>
+#include <vector>
+
+using std::vector;
+
+int binary_search(const vector<int> &a, int x) {
+  int left = 0, right = (int)a.size(); 
+  //write your code here
+}
+
+int linear_search(const vector<int> &a, int x) {
+  for (size_t i = 0; i < a.size(); ++i) {
+    if (a[i] == x) return i;
+  }
+  return -1;
+}
+
+int main() {
+  int n;
+  std::cin >> n;
+  vector<int> a(n);
+  for (size_t i = 0; i < a.size(); i++) {
+    std::cin >> a[i];
+  }
+  int m;
+  std::cin >> m;
+  vector<int> b(m);
+  for (int i = 0; i < m; ++i) {
+    std::cin >> b[i];
+  }
+  for (int i = 0; i < m; ++i) {
+    //replace with the call to binary_search when implemented
+    std::cout << linear_search(a, b[i]) << ' ';
+  }
+}
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01 b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01
new file mode 100644
index 0000000..94106f5
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01
@@ -0,0 +1,2 @@
+5 1 5 8 12 13
+5 8 1 23 1 11
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01.a b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01.a
new file mode 100644
index 0000000..b1857aa
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/01-binary_search/tests/01.a
@@ -0,0 +1 @@
+2 0 -1 0 -1 
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/majority_element.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/majority_element.cpp
new file mode 100644
index 0000000..803db91
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/majority_element.cpp
@@ -0,0 +1,22 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+using std::vector;
+
+int get_majority_element(vector<int> &a, int left, int right) {
+  if (left == right) return -1;
+  if (left + 1 == right) return a[left];
+  //write your code here
+  return -1;
+}
+
+int main() {
+  int n;
+  std::cin >> n;
+  vector<int> a(n);
+  for (size_t i = 0; i < a.size(); ++i) {
+    std::cin >> a[i];
+  }
+  std::cout << (get_majority_element(a, 0, a.size()) != -1) << '\n';
+}
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/01 b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/01
new file mode 100644
index 0000000..76b15de
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/01
@@ -0,0 +1,2 @@
+5
+2 3 9 2 2
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/01.a b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/01.a
new file mode 100644
index 0000000..d00491f
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/01.a
@@ -0,0 +1 @@
+1
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/02 b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/02
new file mode 100644
index 0000000..18a4d51
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/02
@@ -0,0 +1,2 @@
+4
+1 2 3 4
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/02.a b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/02.a
new file mode 100644
index 0000000..573541a
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/02.a
@@ -0,0 +1 @@
+0
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/03 b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/03
new file mode 100644
index 0000000..d0ebc78
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/03
@@ -0,0 +1,2 @@
+4
+1 2 3 1
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/03.a b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/03.a
new file mode 100644
index 0000000..573541a
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/02-majority_element/tests/03.a
@@ -0,0 +1 @@
+0
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/sorting.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/sorting.cpp
new file mode 100644
index 0000000..7a60a12
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/sorting.cpp
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <vector>
+
+using std::vector;
+using std::swap;
+
+int partition2(vector<int> &a, int l, int r) {
+  int x = a[l];
+  int j = l;
+  for (int i = l + 1; i <= r; i++) {
+    if (a[i] <= x) {
+      j++;
+      swap(a[i], a[j]);
+    }
+  }
+  swap(a[l], a[j]);
+  return j;
+}
+
+void randomized_quick_sort(vector<int> &a, int l, int r) {
+  if (l >= r) {
+    return;
+  }
+
+  int k = l + rand() % (r - l + 1);
+  swap(a[l], a[k]);
+  int m = partition2(a, l, r);
+
+  randomized_quick_sort(a, l, m - 1);
+  randomized_quick_sort(a, m + 1, r);
+}
+
+int main() {
+  int n;
+  std::cin >> n;
+  vector<int> a(n);
+  for (size_t i = 0; i < a.size(); ++i) {
+    std::cin >> a[i];
+  }
+  randomized_quick_sort(a, 0, a.size() - 1);
+  for (size_t i = 0; i < a.size(); ++i) {
+    std::cout << a[i] << ' ';
+  }
+}
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/tests/01 b/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/tests/01
new file mode 100644
index 0000000..76b15de
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/tests/01
@@ -0,0 +1,2 @@
+5
+2 3 9 2 2
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/tests/01.a b/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/tests/01.a
new file mode 100644
index 0000000..e5f95a9
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/tests/01.a
@@ -0,0 +1 @@
+2 2 2 3 9 
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp
new file mode 100644
index 0000000..efc7a82
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp
@@ -0,0 +1,25 @@
+#include <iostream>
+#include <vector>
+
+using std::vector;
+
+long long get_number_of_inversions(vector<int> &a, vector<int> &b, size_t left, size_t right) {
+  long long number_of_inversions = 0;
+  if (right <= left + 1) return number_of_inversions;
+  size_t ave = left + (right - left) / 2;
+  number_of_inversions += get_number_of_inversions(a, b, left, ave);
+  number_of_inversions += get_number_of_inversions(a, b, ave, right);
+  //write your code here
+  return number_of_inversions;
+}
+
+int main() {
+  int n;
+  std::cin >> n;
+  vector<int> a(n);
+  for (size_t i = 0; i < a.size(); i++) {
+    std::cin >> a[i];
+  }
+  vector<int> b(a.size());
+  std::cout << get_number_of_inversions(a, b, 0, a.size()) << '\n';
+}
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01 b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01
new file mode 100644
index 0000000..b8b0218
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01
@@ -0,0 +1,2 @@
+5
+2 3 9 2 9
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01.a b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01.a
new file mode 100644
index 0000000..0cfbf08
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01.a
@@ -0,0 +1 @@
+2
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/points_and_segments.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/points_and_segments.cpp
new file mode 100644
index 0000000..3e9dfaf
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/points_and_segments.cpp
@@ -0,0 +1,38 @@
+#include <iostream>
+#include <vector>
+
+using std::vector;
+
+vector<int> fast_count_segments(vector<int> starts, vector<int> ends, vector<int> points) {
+  vector<int> cnt(points.size());
+  //write your code here
+  return cnt;
+}
+
+vector<int> naive_count_segments(vector<int> starts, vector<int> ends, vector<int> points) {
+  vector<int> cnt(points.size());
+  for (size_t i = 0; i < points.size(); i++) {
+    for (size_t j = 0; j < starts.size(); j++) {
+      cnt[i] += starts[j] <= points[i] && points[i] <= ends[j];
+    }
+  }
+  return cnt;
+}
+
+int main() {
+  int n, m;
+  std::cin >> n >> m;
+  vector<int> starts(n), ends(n);
+  for (size_t i = 0; i < starts.size(); i++) {
+    std::cin >> starts[i] >> ends[i];
+  }
+  vector<int> points(m);
+  for (size_t i = 0; i < points.size(); i++) {
+    std::cin >> points[i];
+  }
+  //use fast_count_segments
+  vector<int> cnt = naive_count_segments(starts, ends, points);
+  for (size_t i = 0; i < cnt.size(); i++) {
+    std::cout << cnt[i] << ' ';
+  }
+}
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/01 b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/01
new file mode 100644
index 0000000..9063981
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/01
@@ -0,0 +1,4 @@
+2 3
+0 5
+7 10
+1 6 11
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/01.a b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/01.a
new file mode 100644
index 0000000..e9ec950
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/01.a
@@ -0,0 +1 @@
+1 0 0 
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/02 b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/02
new file mode 100644
index 0000000..df7974d
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/02
@@ -0,0 +1,3 @@
+1 3
+-10 10
+-100 100 0
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/02.a b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/02.a
new file mode 100644
index 0000000..2790b88
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/02.a
@@ -0,0 +1 @@
+0 0 1 
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/03 b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/03
new file mode 100644
index 0000000..f7ba92e
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/03
@@ -0,0 +1,5 @@
+3 2
+0 5
+-3 2
+7 10
+1 6
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/03.a b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/03.a
new file mode 100644
index 0000000..0bd1e96
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/05-points_and_segments/tests/03.a
@@ -0,0 +1 @@
+2 0 
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/check b/01-algorithmic_toolbox/03-divide_and_conquer/check
new file mode 100755
index 0000000..8bdb3d4
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/check
@@ -0,0 +1,38 @@
+#! /bin/bash
+
+RESET="\033[0m"
+BLACK="\033[0;30m"
+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