problem.txt (2214B)
1 B. Hamming Distance Sum 2 time limit per test 3 2 seconds 4 memory limit per test 5 256 megabytes 6 7 Genos needs your help. He was asked to solve the following programming problem by Saitama: 8 9 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. 10 11 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|. 12 Input 13 14 The first line of the input contains binary string a (1 ≤ |a| ≤ 200 000). 15 16 The second line of the input contains binary string b (|a| ≤ |b| ≤ 200 000). 17 18 Both strings are guaranteed to consist of characters '0' and '1' only. 19 Output 20 21 Print a single integer — the sum of Hamming distances between a and all contiguous substrings of b of length |a|. 22 23 --- 24 25 Constraints: 26 27 - hamming distance 28 - number of indices with differing values 29 - given binary string find hamming distances between a and all contiguous substrings of b of length |a| 30 31 32 --- 33 34 examples: 35 36 01 37 00111 38 39 all ct substrings of size |a|: 40 41 00 01 11 11 42 01 01 01 01 43 44 1 + 0 + 1 + 1 45 46 = 3 47 48 ex2: 49 50 0011 51 0110 52 53 all ct substrings of size |a|: 54 55 0110 56 0011 57 58 = 2 59 60 --- 61 62 Thoughts: 63 64 - could materialize all substrings but that's slow 65 - there's a reuse here it seems 66 - 1111 67 - 0000000000 68 - so like we computs the distance between the 0->3 and we track which elements have a delta with a boolean 69 - then for the next one we push another char onto our comparison string, adding 1 or 0 if they differ 70 - then we pop from the start and decrement our current value if relevant 71 - we can actually do this with a circular array under the hood 72 - second line can't be smaller than first per problem 73 74 --- 75 76 Key insights: 77 78 - we care about the number of zeroes / ones that happen after the current index in ranges of a 79 - this performs only necessary comparisons, caching computations in a prefix sum array 80 81 --- 82 83 TIME: 1h 17m