Türkçe

Sorunun çözümü için farketmemiz gereken ilk şey Dero'nun baştaki listeyi en kötü durumda bile 26 listeye bölebileceği. Dero her harf için farklı liste oluşturabilir ve her kelimede de 26 harften biri olması gerektiğinden toplamda 26 liste her durum için yeterli olur. Yani çözüm için hangi harfleri kullanmamız gerektiğini bulmalıyız.

En küçük liste sayısını bulmak için tüm durumları yani tüm harf kombinasyonlarını kontrol etmemiz gerekli, fakat tüm durumları normal bir şekilde kontrol etmeye kalkarsak zaman limitini geçemeyiz. 26 tane harf var ve hepsini kontrol etmemiz toplamda \(2^{26}\) tane duruma bakmamız gerekli. Bunu küçültmek için toplam durumları iki parçaya ayırabiliriz. Bu şekilde \(2^{13}\) karşılaştırma içeren 2 tane karşılaştırma yapıp 2 tane liste oluşturduktan sonra, bu iki listenin tüm elemanlarını birbiriyle karşılaştırmamız yeterli olacaktır.

Yiit'in verdiği listedeki şarkılarda bulunan harflerden oluşmayan bir harfler kümesini cevap olarak alamayız, çünkü bu durumda o şarkı sondaki listelerimiz içinde olmaz. Her şarkı ismi için bu kümeleri işaretlediğimizde, işaretlenmeyen kümeler içerisindeki en küçük kümeyi seçtiğimizde Dero'nun en az kaç listeye bölebileceğini bulabiliriz.

Tüm harf kombinasyonlarının yeterli olup olmadığını kontrol etmek için de Dynamic Programming ve Bitmask kullanabiliriz. Eğer alfabemizin 4 harften oluştuğunu düşünürsek, her şarkı ismindeki harf kümelerini bitlere şu şekilde çevirebiliriz:

• \(ab = 0011\)
• \(bc = 0110\)
• \(cd = 1100\)

Sonrasında bu kümelerin terslerini alıp, yeni bulduğumuz kümeleri "kullanılamaz" olarak işaretleriz:

• \(ab' = 1100\)
• \(bc' = 1001\)
• \(cd' = 0011\)

Fakat sadece bu kümeler değil, bu kümelerin tüm alt kümelerini de "kullanılamaz" olarak işaretlememiz gerekiyor. Eğer alfabedeki harf sayısı 4-5 gibi küçük bir sayı olsaydı, bu durumda tüm alt kümeleri recursive bir şekilde bulmak mümkündü. Fakat bu 26 harfli bir alfabede mümkün olmayacağından, ilk önce alfabeyi 2'ye bölmemiz gerekiyor. Sonrasında bu ikiye bölünmüş her parçayı en fazla \(\mathbf{2^{13}}\) kontrolden geçirerek bulabiliriz. Tüm alfabenin olduğu bir kümeden kontrole başlayarak, sırasıyla tüm kümeleri kontrol edebiliriz. Her "kullanılamaz" olarak işaretlediğimiz kümenin tüm harfleri için o harfi içermeyen alt kümelerini "kullanılamaz" olarak işaretlememiz gerekmektedir.

En sonda da bu kullanılabilir kümeler içerisinden en küçük kümeyi bulmamız yeterli olacaktır.

English

The first thing we need to realize about the problem is that Dero can split the playlist into 26 lists in the worst case. Dero can create a new playlist for each letter and since there will be at least one of the letters in each word, 26 lists would be sufficient. So we need to find which letters do we need for the solution.

We need to check all the combinations of letters for finding the minimum number of playlists. Checking all of them in a standard way would be costly and will result in exceeding the time limit because there are \(2^{26}\) combinations in total. We can divide the total cases into 2 in order to make it smaller. This way, we can make 2 comparisons which have \(2^{13}\) comparisons each and create 2 lists. At this point, comparing the elements of these 2 lists will be sufficient.

We cannot take a set of letters that are not composed of the letters in the playlist Yiit has given in our solution, because that song would not be an element of the lists in the final solution. If we mark each one of such sets, we can find the minimum number of playlists that Dero can make by taking the smallest set in the unmarked combinations.

To check whether the letter combinations are sufficient or not, we can use Dynamic Programming or Bitmask. Let's consider that our alphabet has 4 letters, we can convert each song name into bits in this form:

• \(ab = 0011\)
• \(bc = 0110\)
• \(cd = 1100\)

Then we can take the negations of these sets and mark them as "unusable":

• \(ab' = 1100\)
• \(bc' = 1001\)
• \(cd' = 0011\)

We need to mark not only these sets but their subsets as "unusable" as well. If our alphabet had a small number of letters like 4 or 5, we could find all of the subsets recursively. Since this is not possible for an alphabet of 26 letters, we first need to divide the alphabet into 2. Then in these 2 split alphabets, we can find every set in at most \(\mathbf{2^{13}}\) comparisons. Starting from a set containing all the letters of the alphabet, we can check every set. For each letter in a previously marked set, we need to mark every subset that does not contain that letter as "unusable".

Finally, we need to find the smallest possible among the usable sets.

Örnek Çözüm / Sample Solution

#include <bits/stdc++.h>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset

using namespace std;

typedef long long Lint;
typedef double db;
typedef pair<int,int> ii;
typedef pair<Lint,int> li;
typedef pair<int,char> ic;
typedef pair<db,db> dd;
typedef pair<ii,int> iii;
typedef pair<ii,ii> i4;

const int maxn = 200020;
const int maxm = 1000020;
const int MOd = 1e9+7;
const int MOd2 = 998244353;

#define K 8192

int a;
bitset<(1<<26)/K> used[K];
char num[1<<26];

void solve() {
    scanf("%d",&a);

    num[0]=0;
    for(int i=1;i<(1<<26);i++) 
        num[i] = num[i-(i&(-i))]+1;
    int mask = (1<<26) - 1;

    for(int i=1;i<=a;i++) {
        string s;
        cin >> s;
        int h = 0;
        for(int j=0;j<s.size();j++)
            h |= 1<<(s[j] - 'a');
        h = mask^h;
        used[h&(K-1)][h/K] = 1;
    }

    int h, c, ans = 26, cnt, ok;
    for(int j=K-1;j>=0;j--) {
        for(int i=mask/K;i>=0;i--) {
            if( used[j][i] ) {
                h = i;
                while( h ) {
                    c=i^(h&(-h));
                    used[j][c] = 1;
                    h &= h-1;
                }
            }
        }
    }

    for(int j=K-1;j>=0;j--) {
        h = j;
        while( h ) {
            c=j^(h&(-h));
            used[c] |= used[j];
            h &= h-1;
        }
    }

    for(int j=0;j<K;j++)
        for(int i=0;i<=mask/K;i++) 
            if( !used[j][i] ) umin( ans, num[i]+num[j] );

    cout << ans << endl;
}

int main() {
    int n = 1;
    while( n-- ) solve();
    return 0;
}