[2013-okruzno-ss-kaladont] Vremensko ogranicenje?

Pitanja i problemi
1

Radi se o zadatku: https://petlja.org/BubbleBee/r/Problems/2013-okruzno-ss-kaladont#

Kod izgleda ovako: https://pastebin.com/jNELAVVt Python 2.x

Dakle kod ima slozenost toliku da ucitava i vrsi sva racunanja u samo jednom ciklusu. Mislim da od ovoga ne moze prostije, ili gresim?

Ako ne gresim da li se radi o tome da C++ i Pascal (ako se ne varam) koji su dozvoljeni na takmicenju isti ovaj kod izvrsavaju mnogo brze? I da bi zbog toga trebalo povecati vremensko ogranicenje za ostale programske jezike?

2

Nisam ekspert sto se tice Python-a, a narocito slozenosti odredjenih operacija u Python-u ali prilicno sam siguran da je sledeci deo koda jako skup za izvrsavanje:

nastavak1=string1lista[len(string1lista)-k:len(string1lista)]    
    pocetak2=string2lista[0:k]
   
    if(nastavak1==pocetak2):

Izvlacenje dva podniza, a potom njihovo poredjenje.

Ako prepises kod koji prolazi u Pascal-u u Python, prilicno sam siguran da ce se izvrsavati u najgorem slucaju jednako brzo. Osim ako ne znas tacnu slozenost izvrsavanja Python funkcija (i operacija) koje koristis, mozda je bolje da sam implementiras te funkcije.

3

Pa to i jeste zadatak. Potrebno je uporediti zadnjih K elemenata jednog niza (reci) i prvih K drugog.
Ukoliko bih rucno prolazio kroz niz slozenost bi bilo O(K) za taj prolaz. Na https://stackoverflow.com/questions/1115313/cost-of-len-function linku ljudi kazu da je slozenost te komande O(1) - nezavisno od duzine niza.

Kodovi takmicara koje sam nasao imaj taj ‘rucni’ prolaz i njihovi kodovi prolaze bez problema.

4

Ali ja ovde vidim 2 nepotrebne slice operacije da bi se elementi jednostavno uporedili. Dakle, iako je slozenost O(K), ovaj deo koda je jako skup. Moguce da je vremensko ogranicenje tesno i da ne dozvoljava takve propuste.

5

Upravu si!
Ja sam se sinoc zbunio kada sam odgovarao, sada sve radi!

1 Like