Najveći NZD


#1

Pitanje ili opis problema

Već duže vreme pokušavam da rešim zadatak Najveći NZD ali mi ne ide, izbacuje mi TLE, radio sam preko rekurzije, probao sa nizovima, kasnije sa listama (zbog njih mi izbacuje MLE), te tražim pomoć ovde. Ako neko može da mi pomogne neka mi da neke smernice kako i šta.

Link ka zadatku ili odgovarajućoj stranici

https://petlja.org/biblioteka/r/Problems/MAXNZD


#2

Nisam probao da ovo implementiram, ali mislim da bi trebalo da je ok resenje:

Neka je S suma svih elemenata a_i, i neka je g NZD brojeva koji ostanu na kraju. Posto je njihova suma takodje S, g mora deliti S. Za S<10^6 nema mnogo mogucih vrednosti g koje ovo zadovoljavaju (oko 800), tako da ih mozemo sve testirati – ostaje nam da u dobroj slozenosti (konkretno \mathcal{O}(N) proverimo da li mozemo napraviti k brojeva deljivih sa fiksnim g.

Primenimo sledeci niz operacija:

  • ako je prvi element niza a deljiv sa g, nastavimo dalje (i ignorisemo ga od sada),
  • u suprotnom, saberemo prvi i drugi

(napomena: nema potrebe da stvarno transformisemo niz, dovoljno je da pamtimo sumu sabranih brojeva)

Ako na kraju ove procedure ostane manje od k brojeva, za ovo g resenje ne postoji; u suprotnom, ukoliko imamo “visak” brojeva mozemo sabrati proizvoljne susedne da im smanjimo broj.

Kratka (i nejasna) skica dokaza tvrdjenja od gore: kako god napravimo brojeve u krajnjem resenju, prvi mora biti suma elemenata a_1, a_2, ..., a_i do nekog a_i za koje je ta suma deljiva sa g – dakle, zbir nekoliko brojeva koji ostaju na kraju ovom procedurom, i samim tim g mora deliti sumu a_1 + \dots + a_i. Slicno, sledeci broj je a_{i+1} + \dots + a_j i deljiv sa g, tako da je i suma a_1 + \dots + a_j deljiva sa g. Dakle, brojeve na kraju mozemo “razdvojiti” samo u tackama gde je suma deljiva sa g, tako da se resenje sa najvise brojeva dobija tako sto uzmemo svaku takvu tacku.


#3

Probaću da implementiram to, hvala.


#4

Imam još jedan problem, naime kad hoću da iskoristim push back na vektoru on ne uradi ništa, size vektora ostane 0 i ništa se ne dešava, a taj int ima vrednost u sebi provereno. U čemu može biti problem?


#5

Ovo ne bi trebalo da je moguce – ako nisi resio problem, mozes li da postavis deo koda koji ne radi?