Hello CF family, I attempted to solve the Palindrome Pair problem last night. I had to look at the editorial and then the solution to the problem after failing several times. I attempted in O(N2) and received TLE in the 9th TC.
void solve()
{
int n;
cin >> n;
vector<string> v(n);
loop(n)
{
cin >> v[i];
}
map<pair<string, string>, bool> store;
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j =i+1; j < n; j++)
{
if (i != j)
{
string a = v[i];
string b = v[j];
// if (store.count({a, b}) == 0 or store.count({b,a})==0)
// {
if (isPalin((a + b)))
{
ans++;
}
else
{
map<char, int> m;
loop(a.size())
{
m[a[i]]++;
}
loop(b.size())
{
m[b[i]]++;
}
int cnt = 0;
for (auto x : m)
{
if (x.second % 2 != 0)
{
cnt++;
}
}
if (cnt <= 1)
ans++;
}
// }
// store[{a, b}] = true;
// store[{b, a}] = true;
}
}
}
// ans /= 2;
cout << ans << '\n';
// debug(store);
}
But I didn't catch the idea of using the bit mask here, nor did I get the problem's editorial. So I'm seeking for someone to help me with this problem.
Thanks ( in advance )
A pair of strings is a palindrome pair if and only if for each character 'a' through 'z', the frequency of the character in the first string + the frequency of the character in the second string = an even number, * with at most one exception *.
That being said, we only need to know the parities of the frequencies of each letter in each string. And since a frequency is either even or odd (only 2 different states), we can represent each state of the frequency of a letter as a bit. Thus, we can represent the parities of the frequencies of all letters from 'a' to 'z' in a string using 26 bits: bit 0 = 0 if frequency of 'a' is even and 1 otherwise; bit 1 = 0 if frequency of 'b' is even and 1 otherwise; etc. An int variable will do the trick.
Oh, and what do we have here? A very relevant bitmask for each string (and these can be computed in a total of 1,000,000 steps, as there are at most 1,000,000 characters in the input file)!
And how do we check the condition I mentioned in the beginning of the comment? Why, using a bitwise operation called... XOR! (Think about it for a while; even + even = even, 0 XOR 0 = 0; even + odd = odd, 0 XOR 1 = 1; odd + even = odd, 1 XOR 0 = 1; odd + odd = even, 1 XOR 1 = 0)
The problem is now simplified. A pair of strings is a palindrome pair if and only if the XOR of both masks is either 0 or a number with one single bit set to 1. So, if and only if the XOR is 0 or a power of 2 (1, 2, 4, 8, 16, 32, 64, 128, 256, ..., 2^25).
Now, iterate through each string from 1 to n. Let this string be S and its bitmask be B. How many strings form a palindrome pair with S? Well, how many strings have a bitmask B' such that B XOR B' = 0 or 1 or 2 or 4 or 8 or ... or 2^25?
For each string S in the 1-to-n iteration, iterate through the numbers: 0, 1, 2, 4, 8, ..., 2^25. Specifically, try the number 0 separately and then try the numbers: 1<<0, 1<<1, 1<<2, ..., 1<<25. For each string S with bitmask B and for each final number F, we need to find the number of strings (different than this S) such that B XOR B' = F. Now, remember that X XOR X = 0 for any X! So we have that this condition is equivalent to B XOR B' XOR B = F XOR B <=> B' = F XOR B.
Any ideas yet?
Your unordered map approach was really close to the optimal approach, however you used string keys and didn't find this bitmask approach.
Store each string bitmask in an unordered_map. Count the bitmasks equal to F XOR B using the map, let the number be C. (If F = 0, remember to subtract 1 from C; you shouldn't count the string itself!) The answer to the problem is the sum of all C's divided by 2 (because the pair {1, 2} is equal to the pair {2, 1}, and this algorithm counts both pairs).
TL;DR Bitmask for parity of frequency, XOR of bitmasks for testing of condition and unordered_map for counting of pairs.
This is what called explanation. Thanks brother Andrei_ierdnA.