Milyen algoritmussal lehetne az alábbi feladatot megoldani?

Szerintem teljesen érthető a feladat, bár az engem is érdekelne, hogy az O(n^2) még benne van-e a 0.3 mp futásidőben n=200.000-re.

Az én (elég egyszerű) ötletem:

1. Egyszer végigmegyünk a teljes szekvencián, és lejegyezzük, hogy az első k elem között melyik betű hányszor fordul elő, 4 vektorban. Ez kihagyható lépés, ha beépíted a 2. lépésbe, de O(n) idő, ráadásul később lehet vele töredékeket nyerni, szóval nekem "megéri". :)

2. Kezdőelem szerint iterálunk, és megnézzük, hogy az adott kezdőelemmel mi a leghosszabb mutáns részsorozat az egyes betűkkel. Ha megvan az 1. lépés vektora, akkor ez triviális. Ezt a hosszt lejegyezzük mind a 4 betűre. Ez O(n^2).

3. Maxkeressel megkeressük, hogy hol volt a leghosszabb a lejegyzett hossz. O(n), de ez is beépíthető a 2. pontba.

Összesen O(n^2), de nem lepne meg, ha ügyes implementálással nlogn lenne átlagban, ha nem vizsgálsz olyan részsorozatokat, ahol már tudod, hogy létezik hosszabb (ehhez viszont kell az 1. lépés).

UPDATE: oké, közben rájöttem, hogy mire is gondolt a költő. :D (#4 vagyok.) Csak elkövettem azt a hibát, hogy egy biológiai példát felvonultató kérdésnél figyelembe vettem a biológia, és a tudományos logika elemi szabályait. Mint kiderült, nem szabadott volna.

A feladat arról szól, hogy olyan karaktersorozatokat kell keresni, ahol az egyik karakter előfordulása legalább 50%-os, és az összes ilyen létező karaktersorozatból kell a leghosszabbat megállapítani.

Igaz, ez izomból t*könrúgja a feladat leírását, hiszen ez nem arról szól, hogy ha bárhol találunk tetszőleges hosszú olyan szakaszt, ahol az egyik bázis 50%-os többségben van, akkor az már mutációt okozna. Ilyen meggondolással lemehetnénk abázistripletek szintjére, ott viszont azzal szembesülnénk, hogy vannak olyan aminosavak, amiket mindenképpen a feladat szerint mutációt okozó bázishármasok kódolnak. Pl. a Lysine, aminek a kódja AAA vagy AAG. Szép is lenne, ha az összes előfordulása lépten-nyomon mutációt okozna. :D Vagy akár menjünk le n=1 hosszra. Akkor meg minden egyes bázis mutációt hotdozna, hiszen mondjuk egy 1 darab guaninból álló, 1 bázis hosszúságú "sorozatban" a guanin 100%-os többségben van.

Igen, értem, hogy ez egy algoritmustechnikai feladat akart lenni. Csak van az a feladatkészítési alapelv, hogy ne adjunk fel értelmetlen feladatot. Ha már fel akarjuk dobni azzal, hogy (látszólag) életközelivé tesszük a példát, azt lehetne úgy is csinálni, hogy a feladat ne váljon nettó hülyeséggé.

A másik alapelv, hogy a feladat legyen érthető és egyértelmű. Komolyan egy tanár (egy diplomás értelmiségi) nem képes egzakt módon megfogalmazni egy feladatot? A csapból is az folyik, hogy a specifikációnak egyértelműnek, és mindenre kiterjedőnek kell lenni. Erre ad egy olyan feladatot, ami finoman szólva is többféle képpen értelmezhető?

"Ha egy átlagos gépen, pl. a te gépeden lefut"

Oké. Akkor kicsit ismét kötekedek. Mi van, ha az enyémen 0,29 másodperc alatt fut le, az iskolain meg 0,31 alatt? Mi számít átlagos gépnek?

Igen, tudom, ezek kukacoskodások, neki lehet állni egy programot megoldani úgy is, ha nem egyértelmű a specifikáció, csak ebben az esetben nem biztos, hogy a technikailag jó megoldás az ügyfélnek is jó. Aztán majd jön kifogásként a "de hát én nem így gondoltam". Ja. Én meg iratkozzak be gondolatolvasás tanfolyamra? Pont arra kéne törekedni, hogy az ember megszokja, hogy PONTOSAN le kell írni a kívánt szoftver működését. Akkor talán nem ilyen pongyolaságokkal kéne nyaggatni az embereket.

A megoldás kulcsa:

Nem, legalábbis, nem feltétlenül kell a teljes szekvenciát végig vizsgálni.

Van O(nlogn) és O(n) megoldás is, de egyáltalán nem triviális.

[link]

Gyors otlet:

1. vegigiteralok T,A,G,C bazisokon

2. Az adott bazisra (pl. T) keszitek egy indexlistat az elhelyezkedesrol, es egy listat a kovetkezo ugyanolyan bazis tavolsagarol: O(n)

3. Veszem a tavolsagok listajanak osszes reszsorozatat: O(n*n)

4. Ha teljesul adott reszsorozatra, hogy idx_utolso_elem - idx_elso_elem >= 2*sum(reszsorozat), akkor elmentem megjeloltkent az adott reszsorozatot: O(n)

Megj.: ezek hossza: 2*sum(reszsorozat)

5. Kivalasztom az osszes megjelolt reszsorozat kozul azt, ami a leghosszabb, elmentem.

6. Kivalasztom a 4 bazis leghosszabbjai kozul az abszolut leghosszabbat.

Ezen meg ugy lehetne javitani, hogy a reszhalmazokat okos sorrendben vizsgaljuk meg.

Az én értelmezésem szerint:

* van egy n hosszú string, amiben valahol van egy k hosszúságú sub-string, ahol az egyik betű száma > k/2.

* A feladat az, hogy megtaláljuk a legnagyobb ilyen k-t.

* Én ezért azt csinálnám, hogy a tesztelt k-t felülről n-től közelíteném.

* k=n-re ez egy teszt, k=n-1 az két teszt, és így tovább.

* Az első olyan k, ami teljesíti a feltételt lesz a nyerő.

Az, hogy ennek le kell futnia 0.3s alatt egy 200k hosszú stringre, azt sugallja, hogy ennél valami szofisztikáltabb megoldást kell keresni.

#15 konkrétan belinkelte az O(n) megoldást is, az nlogn meg fent van mindenhol kb.

[link]

[link]