Submission #168908

#	Time	Username	Problem	Language	Result	Execution time	Memory
168908		dolphingarlic	Vještica (COCI16_vjestica)	C++14	48 / 160	2057 ms	1148 KiB

vjestica

/*
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;
map<char, int> cnt[16];
int dp[1 << 16];

int get_pref(int mask) {
    map<char, int> pref;
    int ans = 0;
    for (char j = 'a'; j <= 'z'; j++) {
        pref[j] = INT_MAX;
        FOR(i, 0, n) {
            if (mask & (1 << i)) pref[j] = min(pref[j], cnt[i][j]);
        }
        ans += pref[j];
    }
    return ans;
}

int solve(int mask) {
    int pref = get_pref(mask);
    if (__builtin_popcount(mask) == 1) return pref;

    int ans = INT_MAX;
    FOR(i, 1, mask) {
        if ((i & mask) == i) {
            ans = min(ans, dp[i] + dp[mask - i] - pref);
        }
    }
    return ans;
}

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]++;
    }

    FOR(i, 1, (1 << n)) dp[i] = solve(i);

    cout << dp[(1 << n) - 1] + 1;
    return 0;
}

• Subtask 1: 48 / 160