diff options
Diffstat (limited to '01-algorithmic_toolbox')
5 files changed, 244 insertions, 41 deletions
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 index c93e2cf..40f8f01 100644 --- 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 @@ -4,9 +4,16 @@ using std::vector; -int binary_search(const vector<int> &a, int x) { - int left = 0, right = (int)a.size(); - //write your code here +int binary_search(const vector<int> &a, int x) +{ + int left = 0, right = (int) a.size(); + while (left <= right) { + int mid = (left + right) / 2; + if (a[mid] == x) return mid; + if (a[mid] < x) left = (mid + 1); + else right = (mid - 1); + } + return -1; } int linear_search(const vector<int> &a, int x) { @@ -30,7 +37,7 @@ int main() { 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]) << ' '; + std::cout << binary_search(a, b[i]) << ' '; } + std::cout << '\n'; } 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 index 803db91..448eceb 100644 --- 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 @@ -3,12 +3,49 @@ #include <vector> using std::vector; +using std::swap; -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 get_majority_element(vector<int> &a, int left, int right, int &r) +{ + /* std::cout << "["<<left<<";"<<right<<"]"<<std::endl; */ + + if (left == right) { + r = a[left]; + /* std::cout << " 1 * " << r << std::endl; */ + return 1; + } + + int ret; + int n = right - left + 1; + int mid = (left + right) / 2; + + ret = get_majority_element(a, left, mid, r); + if (ret > 0) { + for (size_t i = mid + 1; i <= right; i++) { + if (a[i] == r) ret += 1; + } + if (ret > n / 2) { + /* std::cout << " " << ret << " * " << r << std::endl; */ + return ret; + } + /* std::cout << " nope " << ret << "/"<< n << std::endl; */ + } + + ret = get_majority_element(a, mid + 1, right, r); + if (ret > 0) { + for (size_t i = left; i <= mid; i++) { + /* std::cout << a[i] << " " <<r <<std::endl; */ + if (a[i] == r) ret += 1; + } + if (ret > n / 2) { + /* std::cout << " " << ret << " * " << r << std::endl; */ + return ret; + } + /* std::cout << " nope " << ret << "/"<< n << std::endl; */ + } + + /* std::cout << " nope" << std::endl; */ + return 0; } int main() { @@ -18,5 +55,6 @@ int main() { for (size_t i = 0; i < a.size(); ++i) { std::cin >> a[i]; } - std::cout << (get_majority_element(a, 0, a.size()) != -1) << '\n'; + int r; + std::cout << (get_majority_element(a, 0, a.size() - 1, r) > 0) << '\n'; } 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 index 7a60a12..b27af77 100644 --- a/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/sorting.cpp +++ b/01-algorithmic_toolbox/03-divide_and_conquer/03-sorting/sorting.cpp @@ -4,6 +4,27 @@ using std::vector; using std::swap; +/* int partition3(vector<int> &a, int l, int r) */ +/* { */ +/* int x = a[l]; */ +/* int i = l + 1; */ +/* int j = r; */ +/* int k = r; */ +/* while (i <= k) { */ +/* int v = a[j]; */ +/* if (v < x ) { */ +/* swap(a[i], a[j]); */ +/* i++; */ +/* } else if (v > x) { */ +/* swap(a[j], a[k]); */ +/* k--; */ +/* j--; */ +/* } */ +/* else */ +/* j--; */ +/* } */ +/* } */ + int partition2(vector<int> &a, int l, int r) { int x = a[l]; int j = l; @@ -22,12 +43,30 @@ void randomized_quick_sort(vector<int> &a, int l, int r) { return; } - int k = l + rand() % (r - l + 1); - swap(a[l], a[k]); - int m = partition2(a, l, r); + int p = l + rand() % (r - l + 1); + swap(a[l], a[p]); + /* int m = partition2(a, l, r); */ + + p = a[l]; + int i = l + 1; + int j = r; + int k = r; + while (i <= j) { + int v = a[j]; + if (v < p ) { + swap(a[i], a[j]); + i++; + } else if (v > p) { + swap(a[j], a[k]); + k--; + j--; + } + else + j--; + } - randomized_quick_sort(a, l, m - 1); - randomized_quick_sort(a, m + 1, r); + randomized_quick_sort(a, l, i - 1); + randomized_quick_sort(a, k + 1, r); } int main() { @@ -41,4 +80,5 @@ int main() { for (size_t i = 0; i < a.size(); ++i) { std::cout << a[i] << ' '; } + std::cout << '\n'; } 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 index efc7a82..8400a2d 100644 --- a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp +++ b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp @@ -2,15 +2,41 @@ #include <vector> using std::vector; +using std::swap; -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; +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); + + size_t i = left, j = ave, k = left; + + while ((i != ave) && (j != right)) { + if (a[i] <= a[j]) { + b[k] = a[i]; + i++; + + } else { + b[k] = a[j]; + j++; + number_of_inversions += (ave - i); + } + k++; + } + + for( ; i != ave; i++, k++) + b[k] = a[i]; + + for( ; j != right; j++, k++) + b[k] = a[j]; + + for(i = left, k = left; i < right; i++, k++) + a[i] = b[k]; + + return number_of_inversions; } int main() { 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 index 3e9dfaf..1720870 100644 --- 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 @@ -2,37 +2,129 @@ #include <vector> using std::vector; +using std::swap; -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; +enum T { + L = 0, P = 1, R = 2 +}; + +struct Pair +{ + int v; + T t; + int i; +}; + +void randomized_quick_sort(vector<Pair> &pairs, int l, int r) +{ + if (l >= r) + return; + + int p = l + rand() % (r - l + 1); + swap(pairs[l], pairs[p]); + + int v = pairs[l].v; + int t = pairs[l].t; + int i = l + 1; + int j = r; + int k = r; + while (i <= j) { + int w = pairs[j].v; + if (w < v ) { + swap(pairs[i], pairs[j]); + i++; + } else if (w > v) { + swap(pairs[j], pairs[k]); + k--; + j--; + } else { + w = pairs[j].t; + if (w < t) { + swap(pairs[i], pairs[j]); + i++; + } else if (w > t) { + swap(pairs[j], pairs[k]); + k--; + j--; + } else + j--; + } + } + + randomized_quick_sort(pairs, l, i - 1); + randomized_quick_sort(pairs, k + 1, r); } -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]; +/* int binary_search_point(const vector<Pair> &pairs, int x) */ +/* { */ +/* int left = 0; */ +/* int right = pairs.size(); */ +/* int m = 0; */ + +/* while (left <= right) { */ +/* m = (left + right) / 2; */ +/* Pair p = pairs[m]; */ +/* if (p.v == x) { */ +/* if (p.t == T::P) return m; */ +/* else if (p.t == T::L) left = (m + 1); */ +/* else right = (m - 1); */ +/* } */ +/* else if (p.v < x) left = (m + 1); */ +/* else right = (m - 1); */ +/* } */ +/* return -1; */ +/* } */ + +vector<int> fast_count_segments(vector<Pair> pairs, vector<int> points) +{ + /* for (size_t i = 0; i < pairs.size(); i++) */ + /* std::cout << pairs[i].v << ";" << pairs[i].t << " "; */ + /* std::cout << std::endl; */ + + randomized_quick_sort(pairs, 0, pairs.size() - 1); + + /* for (size_t i = 0; i < pairs.size(); i++) */ + /* std::cout << pairs[i].v << ";" << pairs[i].t << " "; */ + /* std::cout << std::endl; */ + + vector<int> cnt(points.size()); + int v = 0; + for (size_t i = 0; i < pairs.size(); i++) { + Pair p = pairs[i]; + if (p.t == T::L) + v += 1; + else if (p.t == T::R) + v -= 1; + else + cnt[p.i] = v; } - } - return cnt; + 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<Pair> pairs(n * 2 + m); + size_t i = 0; + size_t max = (2 * n); + for (; i < max; i++) { + std::cin >> pairs[i].v; + pairs[i].t = T::L; + i++; + std::cin >> pairs[i].v; + pairs[i].t = T::R; } vector<int> points(m); - for (size_t i = 0; i < points.size(); i++) { + for (i = 0; i < m; i++) { std::cin >> points[i]; + int j = i + max; + pairs[j].v = points[i]; + pairs[j].t = T::P; + pairs[j].i = i; } - //use fast_count_segments - vector<int> cnt = naive_count_segments(starts, ends, points); + vector<int> cnt = fast_count_segments(pairs, points); for (size_t i = 0; i < cnt.size(); i++) { std::cout << cnt[i] << ' '; } + std::cout << '\n'; } |