?
# | 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 |
/** * * * * * * * * * * * * * * * * * * * * * * * * * 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; }
?
?
?
?