diff options
Diffstat (limited to '01-algorithmic_toolbox')
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 Binary files differnew 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 |