Genetyka

Dane jest $n$ słów o długości $m$ nad alfabetem 4-literowym. Należy znaleźć słowo (będzie dokładnie jedno takie), które różni się od każdego innego na dokładnie $K$ pozycjach.

Bardzo łatwo jest napisać rozwiązanie działające w czasie $O(n^2 m)$, wystarczy bowiem sprawdzić dla każdej pary słów na ilu pozycjach się różnią.

Mnożenie macierzy

Zrobimy to jednak szybciej. Główny pomysł to wyrażenie zadania w terminach macierzowych i skorzystanie z pomysłowego triku.

Na początek skupimy się na podzadaniu 3, w którym alfabet jest ograniczony do dwóch liter. Niech $A_i$ oznacza wektor długości $m$, który koduje $i$-te słowo w ten sposób, że litery zamieniamy na liczby $1$ oraz $-1$. Przykładowo słowo ACCAC zostanie zakodowane przez $(1, -1, -1, 1, -1)$.

Rozważmy dwa wektory $A_i$ oraz $A_j$ i obliczmy ich iloczyn skalarny: $$A_i \cdot A_j = \sum_{1 \leq k \leq m} A_i[k] \cdot A_j[k].$$

Na każdej pozycji, która ma takie same litery, dostaniemy $1 \cdot 1 = (-1) \cdot (-1) = 1$, a na pozycjach z różnymi literami dostaniemy $1 \cdot (-1) = (-1) \cdot 1 = -1$. Zatem wynik iloczynu to będzie liczba pozycji o takich samych literach minus liczba pozycji o różnych literach. Jeśli więc chcemy, żeby $i$-te słowo różniło się od $j$-tego na $K$ pozycjach, to musi być $$A_i \cdot A_j = (m-K) - K = m - 2K.$$

Niech macierz $A$ będzie zawierać wszystkie słowa ułożone w wierszach (będzie zatem miała $n$ wierszy i $m$ kolumn). Przemnożenie macierzy $A$ przez pionowy wektor $V$ o długości $m$ daje w wyniku pionowy wektor długości $n$, zawierający na $i$-tej pozycji iloczyn skalarny $A_i \cdot V$.

Słowo $A_i$ jest tym, którego szukamy, jeśli przemnożenie macierzy $A$ przez pionowy wektor $A_i$ da nam w wyniku pionowy wektor $W_i$, w którym wszystkie wartości są równe $m-2K$, oprócz $i$-tej wartości, która jest oczywiście równa $m$ (bo oznacza $A_i \cdot A_i$).

Niestety, mnożenie macierzy $A$ przez wektor $V$ umiemy wykonać w czasie $O(nm)$, a potrzebujemy $n$ takich mnożeń (dla każdego wyboru $V$), zatem nadal daje to nam złożoność czasową $O(n^2 m)$.

Sprytna sztuczka -- sprawdzanie wyniku mnożenia macierzy

Okazuje się jednak, że sprawdzenie, czy wynik mnożenia macierzy jest konkretną macierzą $W$ można zrobić szybciej niż obliczenie wyniku mnożenia od zera.

Chcemy sprawdzić, czy $A \cdot A_s$ daje w wyniku $W_s$. To sprowadza się do sprawdzenia układu $n$ równań (dla $1 \leq i \leq n$): $$A_i \cdot A_s - W_s[i] = 0.$$

Zrobimy to metodą probabilistyczną. Losujemy $n$ dużych liczb $p_i$ i sumujemy wszystkie równania (modulo duża liczba pierwsza $P$), przemnażając $i$-te z nich przez liczbę $p_i$:

$$\sum_{i} p_i (A_i \cdot A_s - W_s[i]) = 0.$$

Jeśli układ był prawidłowy, to powyższa suma da 0. Okazuje się jednak, że jeśli suma ta jest 0, to z dużym prawdopodobieństwem układ równań musi być prawidłowy.

Wynika to z lematu Schwartza--Zippela, który orzeka, że niezerowy wielomian $n$ zmiennych o stopniu $d$ nad ciałem $S$ ewaluuje się do 0 dla losowych wartości z prawdopodobieństwem $\leq d/|S|$. Wykonywanie obliczeń modulo liczba pierwsza $P$ oznacza działania nad ciałem rozmiaru $|S| = P$.

Jeśli zatem weźmiemy wielomian $$\sum_{i} x_i (A_i \cdot A_s - W_s[i]),$$ to dla losowych $x_i = p_i$ jest bardzo mała szansa $1/P$, że będzie on 0, chyba że wielomian jest zerowy, czyli wszystkie $A_i \cdot A_s - W_s[i]$ są zerami. Biorąc $P=10^9+7$ szansa pomyłki jest bardzo mała. W razie potrzeby możemy ją zwiększyć, przez wzięcie większej liczby $P$ lub wykonanie obliczenia niezależnie dla kilku różnych wartości $P$.

Zatem, wystarczy sprawdzić, czy

$$\sum_{i} p_i (A_i \cdot A_s) = \sum_{i} p_i W_s[i]$$

Po prawej stronie mamy po prostu $$(\sum_{i} p_i) (m - 2K) + p_s \cdot 2K$$

a po lewej stronie mamy: $$\sum_{i} p_i ( \sum_{k} A_i[k] \cdot A_s[k]) = \sum_{i} \sum_{k} p_i \cdot A_i[k] \cdot A_s[k] = \sum_{k} ( \sum_{i} p_i \cdot A_i[k] ) \cdot A_s[k] = \sum_{k} B_k \cdot A_s[k],$$

gdzie wartość $B_k$ jest po prostu sumą elementów $k$-tej kolumny macierzy $A$, przemnożonych przez kolejne liczby $p_i$.

Wyznaczyć wektory $B_k$ możemy w czasie $O(nm)$. Dzięki temu każde sprawdzenie wektora $A_s$ będzie działać w czasie $O(n)$. Ostatecznie, złożoność czasowa całego algorytmu wyniesie $O(nm)$.

const int N = 4110, P = 1000000007;
int n,m,K;
char w[N][N];
int a[N][N];
int p[N],sum_p;
int b[N];

int main() {
  scanf("%d%d%d",&n,&m,&K);
  REP(i,n) scanf("%s",w[i]);

  REP(i,n) REP(j,m) {
    a[i][j] = w[i][j] == 'A' ? 1 : P-1;
  }

  REP(i,n) {
    p[i] = rand() % P;
    sum_p = (sum_p + p[i]) % P;
  }
  sum_p = ll(sum_p) * (P + m - 2*K) % P;

  REP(i,n) REP(j,m) {
    b[j] = (b[j] + ll(a[i][j]) * p[i]) % P;
  }

  int ans = -1;
  REP(s,n) {
    int sum = 0;
    REP(i,m) {
      sum = (sum + ll(b[i]) * a[s][i]) % P;
    }
    if (sum == (sum_p + ll(p[s]) * (2*K)) % P) {
      ans = s+1;
    }
  }

  printf("%d\n", ans);
}

Dowolny alfabet

Zrobimy sztuczkę, dzięki której dla dowolnego alfabetu rozmiaru $A$, algorytm będzie działał w czasie $O(Anm)$. Każde słowo zamieniamy na słowo binarne o długości $Am$, przez zastąpienie $i$-tej litery alfabetu $A$-literowym słowem składającym się z liter A i jednej litery C na $i$-tej pozycji. Zatem dla $A=4$ litery zastępujemy przez ciągi CAAA, ACAA, AACA i AAAC. Ciągi odpowiadające różnym literom różnią się na dokładnie dwóch pozycjach. Zatem dobre słowo różni się od wszystkich pozostałych na dokładnie $2K$ pozycjach. Wystarczy zatem wprowadzić następującą poprawkę do poprzedniego algorytmu:

  code['A'] = 0;
  code['C'] = 1;
  code['G'] = 2;
  code['T'] = 3;

  REP(i,n) REP(j,4*m) {
    a[i][j] = P-1;
  }
  REP(i,n) REP(j,m) {
    a[i][4*j + code[w[i][j]]] = 1;
  }
  m *= 4;
  K *= 2;