alpha_pi's blog

By alpha_pi, history, 4 years ago, In English

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 )

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it