Need help in problem [Palindrome Pairs]

2 years ago

source link: http://codeforces.com/blog/entry/109100
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

alpha_pi's blog

By alpha_pi, history, 35 minutes ago,

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 )

Recommend