608B - Hamming Distance Sum - CodeForces Solution


combinatorics strings *1500

Please click on ads to support us..

Python Code:

a, b, ans, c = input(), input(), 0, [0]
d = len(b) - len(a)
for i in range(len(b)):
    c.append(c[-1] + int(b[i]))
for i in range(len(a)):
    ones = c[d + i + 1] - c[i]
    zeros = d + 1 - ones
    ans += ones if a[i] == "0" else zeros
print(ans)

C++ Code:

#include <bits/stdc++.h>
using namespace std;
int main() {
   string s,t;
   cin>>s>>t;
   set<string>se;
   long long sum=0;
   vector<int>z(t.size()+1),o(t.size()+1);
   for(int i=0;i<t.size();i++)
   {
      z[i+1]+=z[i]+(t[i]=='0');
      o[i+1]+=o[i]+(t[i]=='1');
   }
   for(int i=0;i<s.size();i++)
   {
       int l=i,r=t.size()-s.size()+i+1;
       if(s[i]=='1') sum+=z[r]-z[l];
       else
           sum+=o[r]-o[l];
   }
   cout<<sum;
    return 0;
}


Comments

Submit
0 Comments
More Questions

302A - Eugeny and Array
1638B - Odd Swap Sort
1370C - Number Game
1206B - Make Product Equal One
131A - cAPS lOCK
1635A - Min Or Sum
474A - Keyboard
1343A - Candies
1343C - Alternating Subsequence
1325A - EhAb AnD gCd
746A - Compote
318A - Even Odds
550B - Preparing Olympiad
939B - Hamster Farm
732A - Buy a Shovel
1220C - Substring Game in the Lesson
452A - Eevee
1647B - Madoka and the Elegant Gift
1408A - Circle Coloring
766B - Mahmoud and a Triangle
1618C - Paint the Array
469A - I Wanna Be the Guy
1294A - Collecting Coins
1227A - Math Problem
349A - Cinema Line
47A - Triangular numbers
1516B - AGAGA XOOORRR
1515A - Phoenix and Gold
1515B - Phoenix and Puzzle
155A - I_love_username