General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
195731060 Practice:
TheBhediyaOfDalalStreet
1800F - 31 C++20 (GCC 11-64) Time limit exceeded on test 27 4000 ms 71252 KB 2023-03-02 23:27:16 2023-03-03 15:59:20
→ Source
/** * * * * * * * * * * * * * * * * * * * * * *
*                                             *
*         The world is a scary place          *
*  Now that you've woken up the demon in me   *
*                                             *
* * * * * * * * * * * * * * * * * * * * * * **/

#include <bits/stdc++.h>
#define int long long
#define endl "\n"

using namespace std;

/* TODO LIST:
    0) DP (Hard)
    1) DSU (Hard) (*Done)
    2) Bitmask DP Practice (*Done)
    3) smallest prime factor practice
    4) Digit DP Practice
    5) Dijkstra (Hard) (*Done)
    6) Meet in the middle (*Done): http://codeforces.com/contest/888/problem/E, https://codeforces.com/problemset/problem/1006/F
    7) Bridges practice: https://codeforces.com/blog/entry/68138
    8) SOS DP: https://codeforces.com/blog/entry/45223, USACO (*Done)
    9) Diameter of tree (practice): https://codeforces.com/contest/456/problem/E, https://codeforces.com/contest/1404/problem/B, https://codeforces.com/blog/entry/101271
    10) Binary Lifting (Hard)
    11) Graph - MST (*Done)
    12) USACO - Finish Gold (Stacks onwards)
*/

// Pro tip: Always use the get_parent(u) method instead of parent[u] in DSU


// Intuitively, feels like a bitmask problem
// consider writing strings as a bitmask of exisisting characters
// Then we need m1 | m2 having 25 set bits
// But that doesn't help with odd frequency criteria
// So define another mask, m1 = mask of characters with odd frequency
// This allows us to write for string st,
// m = m1(s) ^ m2(t) should have 25 set bits, note that we can't do OR here, cuz odd + odd = even
// This also means, we can use a map or trie to solve this somehow
// The above condition also implies that the length of the string is odd (25 * odd)

// But the above condition is not sufficient, because there may be 26 characters in resulting string
// So we should impose another con

// The extra condition will lead to AND operation and make the process cumbersome
// Instead let's iterate over possible m values (m1(s) ^ m2(t)) and only consider strings
// that don't have the unset bit in m

// say m = 1111...101, then we will consider s, t without b in it
// This can be done for each mask, since there are only 26, so 26 * O(n) for finding
// the strings which don't have character i in them, and then store them in a frequency map
// and then iterate over the strings again O(n) to get the answer for the mask

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int T = 1;
    // cin >> T;
    for (int t = 1; t < T + 1; t ++) {
        int n;
        cin >> n;
        string s[n];
        for (int i = 0; i < n; i ++) {
            cin >> s[i];
        }
        int cur_mask[n] = {}, cnt[n][26];
        memset(cnt , 0, sizeof cnt);
        for (int i = 0; i < n; i ++) {
            for (auto& c : s[i]) {
                cnt[i][c - 'a'] ++;
            }
            cur_mask[i] = 0;
            for (int x = 0; x < 26; x ++) {
                cur_mask[i] += ((cnt[i][x] % 2) * (1 << x));
                // cout << cnt[i][x] << endl;
            }
            // cout << cur_mask[i] << endl;
        }

        int ans = 0;
        for (int j = 0; j < 26; j ++) {
            int mask = (1 << 26) - (1 << j) - 1;
            map<int, int> C;
            for (int i = 0; i < n; i ++) {
                if (cnt[i][j]) continue; // contains j-th character
                // cout << i << ' ' << j << ' ' << cur_mask[i] << endl;
                ans += C[(mask ^ cur_mask[i])];
                C[cur_mask[i]] ++;
            }
        }
        cout << ans << endl;
    }

    return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details