Initial commit

3 files changed, 64 insertions, 0 deletions

diff --git a/10_advanced_techniques/a.out b/10_advanced_techniques/a.out
new file mode 100755
index 0000000..54ec8d4
--- /dev/null
+++ b/10_advanced_techniques/a.out
diff --git a/10_advanced_techniques/hamming_distance_2136.cpp b/10_advanced_techniques/hamming_distance_2136.cpp
new file mode 100644
index 0000000..a4b0b7d
--- /dev/null
+++ b/10_advanced_techniques/hamming_distance_2136.cpp
@@ -0,0 +1,22 @@
+#include <algorithm>
+#include <bit>
+#include <iostream>
+#include <vector>
+
+int main() {
+        unsigned n, k;
+        std::cin >> n >> k;
+        std::vector<unsigned> a(n);
+        for (unsigned i = 0; i < n; i++) {
+                for (unsigned j = 0, p = 1; j < k; j++, p <<= 1) {
+                        char c;
+                        std::cin >> c;
+                        if (c == '1') a[i] += p;
+                }
+        }
+        int s = k+1;
+        for (unsigned i = 0; i < n; i++)
+                for (unsigned j = i+1; j < n; j++)
+                        s = std::min(s, std::popcount(a[i] ^ a[j]));
+        std::cout << s << "\n";
+}
diff --git a/10_advanced_techniques/meet_in_the_middle_1628.cpp b/10_advanced_techniques/meet_in_the_middle_1628.cpp
new file mode 100644
index 0000000..a38c5d4
--- /dev/null
+++ b/10_advanced_techniques/meet_in_the_middle_1628.cpp
@@ -0,0 +1,42 @@
+#include <algorithm>
+#include <iostream>
+#include <numeric>
+#include <unordered_map>
+#include <vector>
+
+void add_to_map(size_t i, size_t e, long long s,
+    const std::vector<long long>& a,
+    std::unordered_map<long long, long long>& m) {
+        if (i == e) { m[s]++; return; }
+        add_to_map(i+1, e, s, a, m);
+        add_to_map(i+1, e, s+a[i], a, m);
+}
+
+long long f(size_t i, size_t e, long long t, long long s,
+    const std::vector<long long>& a,
+    const std::unordered_map<long long, long long>& m) {
+        if (t < 0 || t > s) return 0;
+        if (i == e) return m.find(t) == m.end() ? 0 : m.at(t);
+        return f(i+1, e, t, s-a[i], a, m) + f(i+1, e, t-a[i], s-a[i], a, m);
+}
+
+int main() {
+        size_t n, p;
+        long long x, s{0};
+        std::cin >> n >> x;
+        std::vector<long long> a(n);
+        for (size_t i = 0; i < n; i++)
+                std::cin >> a[i];
+
+        std::sort(a.begin(), a.end(), std::greater<long long>());
+        s = std::accumulate(a.begin(), a.end(), 0LL);
+        if (x > s) {
+                std::cout << "0\n";
+                return 0;
+        }
+
+        p = a.size()/2;
+        std::unordered_map<long long, long long> m;
+        add_to_map(p, a.size(), 0, a, m);
+        std::cout << f(0, p, x, s, a, m) << "\n";
+}