/*
COCI 2016 Vjestica
- Firstly, notice that N is very small. This implies that we should use a bitmask
- For each mask, we split the active words into 2 groups and solve recursively for those
- solve(mask) = min(solve(A) + solve(B)) where A + B = mask, A & mask == A, B & mask == B, and A & B == 0
- Complexity: O(N^2 * 2^N)
*/
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
int n;
unordered_map<char, int> cnt[16];
int dp[1 << 16];
int solve(int mask) {
int ans = INT_MAX, common = 0, old_mask = mask;
if (~dp[mask]) return dp[mask];
if (!mask) return dp[mask] = 0;
// cout << mask << endl;
unordered_map<char, int> diff;
for (char i = 'a'; i <= 'z'; i++) {
diff[i] = INT_MAX;
FOR(j, 0, n) if (mask & (1 << j)) diff[i] = min(diff[i], cnt[j][i]);
common += diff[i];
}
FOR(i, 0, n) {
if (mask & (1 << i)) {
if (diff == cnt[i]) mask -= (1<<i);
else for (char j = 'a'; j <= 'z'; j++) cnt[i][j] -= diff[j];
}
}
if (!mask) return dp[old_mask] = common;
FOR(i, (common == 0), mask) {
if ((mask & i) == i) ans = min(ans, solve(i) + solve(mask - i));
}
FOR(i, 0, n) {
if (mask & (1 << i)) {
for (char j = 'a'; j <= 'z'; j++) cnt[i][j] += diff[j];
}
}
return dp[old_mask] = ans + common;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(dp, -1, sizeof(dp));
cin >> n;
FOR(i, 0, n) {
for (char j = 'a'; j <= 'z'; j++) cnt[i][j] = 0;
string s;
cin >> s;
for (char j : s) cnt[i][j]++;
}
cout << solve((1 << n) - 1) + 1;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
632 KB |
Output isn't correct |
| 2 |
Incorrect |
31 ms |
632 KB |
Output isn't correct |
| 3 |
Incorrect |
23 ms |
632 KB |
Output isn't correct |
| 4 |
Execution timed out |
2070 ms |
632 KB |
Time limit exceeded |
| 5 |
Incorrect |
1729 ms |
680 KB |
Output isn't correct |
| 6 |
Incorrect |
1684 ms |
728 KB |
Output isn't correct |
| 7 |
Incorrect |
1313 ms |
884 KB |
Output isn't correct |
| 8 |
Incorrect |
1648 ms |
760 KB |
Output isn't correct |
| 9 |
Incorrect |
1749 ms |
880 KB |
Output isn't correct |
| 10 |
Incorrect |
1664 ms |
888 KB |
Output isn't correct |
