algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit 9a7d3e604a7ad5fe7c9862c1c5fe751a19ab0b02
parent 5ef301c7ce5585cc8ff0502fd4c19d5b26a94bc4
Author: Andrew Laack <andrew@laack.co>
Date:   Sat, 17 Oct 2026 13:14:37 -0500

Hamming distance sum

Diffstat:
Acomp/hamming-distance-sum/.problem.txt.swo | 0
Acomp/hamming-distance-sum/.problem.txt.swp | 0
Acomp/hamming-distance-sum/ex1.in | 2++
Acomp/hamming-distance-sum/ex2.in | 2++
Acomp/hamming-distance-sum/main.cpp | 35+++++++++++++++++++++++++++++++++++
Acomp/hamming-distance-sum/problem.txt | 83+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/hamming-distance-sum/t1.cpp | 34++++++++++++++++++++++++++++++++++
Acomp/hamming-distance-sum/t2.cpp | 23+++++++++++++++++++++++
8 files changed, 179 insertions(+), 0 deletions(-)

diff --git a/comp/hamming-distance-sum/.problem.txt.swo b/comp/hamming-distance-sum/.problem.txt.swo Binary files differ. diff --git a/comp/hamming-distance-sum/.problem.txt.swp b/comp/hamming-distance-sum/.problem.txt.swp Binary files differ. diff --git a/comp/hamming-distance-sum/ex1.in b/comp/hamming-distance-sum/ex1.in @@ -0,0 +1,2 @@ +01 +00111 diff --git a/comp/hamming-distance-sum/ex2.in b/comp/hamming-distance-sum/ex2.in @@ -0,0 +1,2 @@ +0011 +0110 diff --git a/comp/hamming-distance-sum/main.cpp b/comp/hamming-distance-sum/main.cpp @@ -0,0 +1,35 @@ +#include <iostream> +#include <vector> +#include <string> + +int main() { + std::string a, b; + std::cin >> a; + std::cin >> b; + long long res = 0; + // inclusive prefix sum + std::vector<long long> prefixSum {}; + std::vector<long long> prefixSumZero {}; + long long sum = 0; + long long sumZero = 0; + + for(int i = 0; i < b.size(); ++i) { + if(b[i] == '1') { + sum += 1; + } else { + sumZero += 1; + } + + prefixSum.push_back(sum); + prefixSumZero.push_back(sumZero); + } + + for(int x = 0; x < a.size(); ++x) { + if(a[x] == '0') { + res += prefixSum[(b.size()-1) - (a.size() - 1 - x)] - prefixSum[x] + (b[x] == '1'); + } else { + res += prefixSumZero[(b.size()-1) - (a.size() - 1 - x)] - prefixSumZero[x] + (b[x] == '0'); + } + } + std::cout << res << std::endl; +} diff --git a/comp/hamming-distance-sum/problem.txt b/comp/hamming-distance-sum/problem.txt @@ -0,0 +1,83 @@ +B. Hamming Distance Sum +time limit per test +2 seconds +memory limit per test +256 megabytes + +Genos needs your help. He was asked to solve the following programming problem by Saitama: + +The length of some string s is denoted |s|. The Hamming distance between two strings s and t of equal length is defined as , where si is the i-th character of s and ti is the i-th character of t. For example, the Hamming distance between string "0011" and string "0110" is |0 - 0| + |0 - 1| + |1 - 1| + |1 - 0| = 0 + 1 + 0 + 1 = 2. + +Given two binary strings a and b, find the sum of the Hamming distances between a and all contiguous substrings of b of length |a|. +Input + +The first line of the input contains binary string a (1 ≤ |a| ≤ 200 000). + +The second line of the input contains binary string b (|a| ≤ |b| ≤ 200 000). + +Both strings are guaranteed to consist of characters '0' and '1' only. +Output + +Print a single integer — the sum of Hamming distances between a and all contiguous substrings of b of length |a|. + +--- + +Constraints: + +- hamming distance + - number of indices with differing values +- given binary string find hamming distances between a and all contiguous substrings of b of length |a| + + +--- + +examples: + +01 +00111 + +all ct substrings of size |a|: + +00 01 11 11 +01 01 01 01 + +1 + 0 + 1 + 1 + += 3 + +ex2: + +0011 +0110 + +all ct substrings of size |a|: + +0110 +0011 + += 2 + +--- + +Thoughts: + +- could materialize all substrings but that's slow +- there's a reuse here it seems + - 1111 + - 0000000000 + - so like we computs the distance between the 0->3 and we track which elements have a delta with a boolean + - then for the next one we push another char onto our comparison string, adding 1 or 0 if they differ + - then we pop from the start and decrement our current value if relevant + - we can actually do this with a circular array under the hood + - second line can't be smaller than first per problem + +--- + +Key insights: + +- we care about the number of zeroes / ones that happen after the current index in ranges of a + - this performs only necessary comparisons, caching computations in a prefix sum array + +--- + +TIME: 1h 17m diff --git a/comp/hamming-distance-sum/t1.cpp b/comp/hamming-distance-sum/t1.cpp @@ -0,0 +1,34 @@ +#include <iostream> +#include <string> + +long dist(int idxL, std::string& a, std::string& b) { + long sum = 0; + for(int i = 0; i < a.size() - 1; i+=2) { + if(b[idxL+i] != a[i]) { + sum += 1; + } + if(b[idxL+i+1] != a[i+1]) { + sum += 1; + } + } + if(a.size() % 2 != 0) { + if(a[a.size()-1] != b[idxL+a.size()-1]) { + sum += 1; + } + } + + return sum; +} + +int main() { + std::string a,b; + + std::cin >> a; + std::cin >> b; + long sum = 0; + + for(int x = 0; x <= (b.size() - a.size()); ++x) { + sum += dist(x,a,b); + } + std::cout << sum << std::endl; +} diff --git a/comp/hamming-distance-sum/t2.cpp b/comp/hamming-distance-sum/t2.cpp @@ -0,0 +1,23 @@ +#include <iostream> +#include <string> + +int main() { + std::string a, b; + std::cin >> a; + std::cin >> b; + + long res = 0; + + for(int x = 0; x < a.size(); ++x) { + + auto current = a[x]; + int ub = b.size() - (a.size() - x); + + for(int i = x; i <= ub; ++i) { + if(current != b[i]) { + res += 1; + } + } + } + std::cout << res << std::endl; +}