codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

608B.md (1977B)


      1 Source: https://codeforces.com/problemset/problem/608/B
      2 
      3 B. Hamming Distance Sum
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Genos needs your help. He was asked to solve the following programming problem by Saitama:
     22 
     23 The length of some string *s* is denoted |*s*|. The Hamming distance between two strings *s* and *t* of equal length is defined as ![](https://espresso.codeforces.com/bbe2d432c57bbd368335d01f4f53b687ff302346.png), where *s**i* is the *i*-th character of *s* and *t**i* 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.
     24 
     25 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*|.
     26 
     27 Input
     28 
     29 The first line of the input contains binary string *a* (1 ≤ |*a*| ≤ 200 000).
     30 
     31 The second line of the input contains binary string *b* (|*a*| ≤ |*b*| ≤ 200 000).
     32 
     33 Both strings are guaranteed to consist of characters '0' and '1' only.
     34 
     35 Output
     36 
     37 Print a single integer — the sum of Hamming distances between *a* and all contiguous substrings of *b* of length |*a*|.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 01  
     45 00111
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 3
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 0011  
     58 0110
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 2
     65 ```
     66 
     67 Note
     68 
     69 For the first sample case, there are four contiguous substrings of *b* of length |*a*|: "00", "01", "11", and "11". The distance between "01" and "00" is |0 - 0| + |1 - 0| = 1. The distance between "01" and "01" is |0 - 0| + |1 - 1| = 0. The distance between "01" and "11" is |0 - 1| + |1 - 1| = 1. Last distance counts twice, as there are two occurrences of string "11". The sum of these edit distances is 1 + 0 + 1 + 1 = 3.
     70 
     71 The second sample case is described in the statement.