Брой 26 на Списание Инфоман
 


Есенен турнир 2004, Задача А2. ПРОЧИТ НА ГЕН

Уловието на задачата може да прочетете тук.

Решение

Първо, ще преобразуваме входните данни в по- удобен вид. Всеки кодон е съставен от 3 бази, за всяка база има по 4 възможности –  A, C, G, T. Следователно имаме 43=64 различни кодона. Ще представим всеки един кодон с едно от числата в интервала 0..63. Така опростихме условието “Да се намери броят на разлчините белтъци (последователности от кодони), които са подпоследователности на дадената ни редица” до следното: “Дадена е редица от числа, да се намери броят на различните редици от числа, подредици на дадената”.  Така получихме задача от теорията на информатиката и за нейното решаване ще приложим познатите информатически методи, а именно ще решим така поставената задача по метода на динамичното оптимиране.

Нека дадената ни в началото редица да отбележим с a1, a2, …, an. Нека си поставим задача да намерим колко на брой различни подредици има до даден елемент t, за всяко tn и нека бележим това число със S[t]. Очевидно S[n] е отговора на задачата. Сега нека, типично за принципа на динамичното оптимиране, да решим задачата за дадено t, като изпозваме решенията за всички по-малки задачи (за всяко i < t). Нека се запитаме какъв може да е видът на редицата спрямо елемента който седи на текущата позиция t. Вариантите са два:

1. Eлементът at се среща за първи път в редицата на позиция t.

В този случай можем към всички редици, които сме имали до елементът t-1 да добавим елемента at в края и освен това да конструираме нова редица с дължина 1, съставена само от елемента at. Така със сигурност няма да повторим елемент, понеже до моментът няма редици завършващи на елеменът at. В този случай получаваме, че ако вариантите до предишния елемент са били S[t-1], то броят на редиците до елементът t са:

S[t] = 2*S[t-1]+1.

2. Елементът at се среща по-рано в редицата.

Сега разсъждаваме аналогично и към всяка от редиците, преброени до позиция t-1 прибавимяме елемента at в края. Ще получим S[t-1] нови редици. Обаче ще имаме повторения, а именно това ще са всички редици, които са били “завършени” от предишното срещане на елемента at в редицата. Нека то е било на позиция r. Тогава за всяка редица, чиито край е бил преди позиция r ние сме добавили at в края и ако го направим отново с елемента на позиция t ще повторим редици. Затова от броя трябва да извадим S[r-1], което е точно броят на тези редици. Очевидно редиците, които завършват на позиции между r и t-1 включително няма как да бъдат повторени. Така получаваме зависимостта:

S[t] = 2*S[t-1] – S[r-1].

По този начин изчерпахме възможните случаи (т.е. всеки елемент или е бил срещан преди, или не). Получихме, че:

S[0] = 0, инициализация, до нулевия елемент имаме нула редици

За t > 0:

S[t] = 2*S[t-1] + 1, ако числото на позиция t се появява за първи път, или

S[t] = 2*S[t-1] – S[r-1], ако числото на позиция t не се появява за първи път и r е позицията на последното, преди позиция t появяване на това число в редицата.

Тъй като всеки елемент бива изчислен точно един път, а за пресмятането му използваме константен брой елементарни операции (едно умножение и едно събиране), сложността на това решение е O(N), където N е броят на числата в началната редица.

 

Примерна реализация:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 4000002

char s[3*MAX]; // posledowatelnostta ot azotni bazi
int n,t[MAX]; // vhodnia masiw, preobrazuwan w chisla
int last[64]; // last[i] = poslednata pozicia, na koiato se sreshta
// ili 0, ako oshte ne e sreshtan
int dp[MAX]; // masiwa za realizacia na dinamichnoto

int main () {
int i,j,st2;
	// chetem whoda
	fgets(s,3*MAX,stdin);
	n = (strlen(s)-1)/3;
	// i go preobrazuwame ot posledowatelnost i ot stringowe w chisla
	// AAA = 0, AAC = 1, AAG = 2, AAT = 3, ACA = 4,... TTT = 63
	for (i=0;i<n;i++) {
		t[i+1] = 0;
		st2 = 16;
		for (j=0;j<3;j++) {
			if (s[3*i+j]=='C')
				t[i+1]+=1*st2;
			if (s[3*i+j]=='G')
				t[i+1]+=2*st2;
			if (s[3*i+j]=='T')
				t[i+1]+=3*st2;
			st2/=4;
		}
	}

	dp[0] = 0; // inicializirame
	for (i=1;i<=n;i++) {
		if (last[t[i]]) {
			dp[i] = 2*dp[i-1] - dp[last[t[i]] - 1];
		} else {
			dp[i] = 2*dp[i-1] + 1;
		}
		while (dp[i]<0) // wajno!
			dp[i]+=(1<<20);
		dp[i]%=(1<<20);
		last[t[i]] = i;
	}
	printf("%d\n",dp[n]); // dp[n] - reshenieto
	return 0;
}			
			

Автор: Слави Маринов


обратно към брой 26