Boshkash_Hates_CP's blog

Need Help With Problem Palindrome Pairs
By Boshkash_Hates_CP, history, 3 days ago, In English

Hello CF , First thing first , happy new year , May this year bring you health , happiness and successes in all you do !

i have struggled to understand Palindrome Pairs solution "in terms of bitmasks" , as i'm newbie.

i didn't thought about the iterative solution as it will be o(n^2) which will case TLE ,so i was trying to get a better solution and i wasn't able to , so i saw the solution which is something like this:

int main()
{
   FastIO;
   ll n ;cin >>n;
   map<ll,ll> mp;
   ll ans = 0;
   while(n--)
   {
      STR s;cin>>s;
      ll m = 0;
      for(auto x : s)
      {
         ll v = x-'a';
         m ^= (1 << v);
      }
      ans += mp[m];
      for(int x = 0 ; x < 26 ; x++)
      {
         m ^= (1 << x);
         ans += mp[m];
         m ^= (1 << x);
      }
      mp[m]++;
   }
   cout << ans;
}

i don't get it , i mean i know to check if a string is a Palindrome or not we get it's mask and check it's power of 2 or not by XOR'ing the values of each char ....help

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

..

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't use masks, just used vectors

My submission

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain your submission , please

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For a permutation to be a palindrome, there should be either no odd freq alphabet(obtained by taking each freq array twice) or exactly 1 odd freq alphabet(switching each even freq to odd and checking how many are there)

      → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Basically a pair is good, if it has at most one letter which has odd frequency (Because otherwise we wouldn't form a palindrome). So what we really care about is the parity of frequency of every letter. The bitmask has 1 (on position i) if it has odd frequency for i-th letter, otherwise 0. You can see that two bitmasks are good pair, if they differ on at most one position. We iterate over this position brutally and add to answer the number of pairs formed with the current string (m^(1<<x) differs exactly on one bit from m and in mp[x] we count the number of strings which have mask x so far). Of course we also add to the answer the number of the strings which have the same mask as current string.

→ Reply