h1. Solutii 'Junior Challenge 2019':jc2019

h2. Soluţie Deletegcd

(toc)*{text-align:center} *Lista de probleme*
* 'Deletegcd':jc2019/solutii#deletegcd
* 'Mixed Signals':jc2019/solutii#mixedsignals
* 'Obstacole':jc2019/solutii#obstacole
* 'Supersenzor':jc2019/solutii#supersenzor
* 'Overpower':jc2019/solutii#overpower
* 'Abba':jc2019/solutii#abba
 
==include(page="jc2019/solutii/deletegcd")==
 
==include(page="jc2019/solutii/mixedsignals")==
 
==include(page="jc2019/solutii/obstacole")==
 
==include(page="jc2019/solutii/supersenzor")==
 
==include(page="jc2019/solutii/overpower")==
 
==include(page="jc2019/solutii/abba")==
 

O primă soluţie, ce obţine 15 puncte este să încercăm să eliminăm fiecare element şi să vedem explicit dacă cel mai mare divizor comun al celorlalte numere este mai mare ca 1, parcurgându-le şi folosind algoritmul lui Euclid.Această soluţie are complexitatea $O(n+q*n*n*log(valmax))$.
Soluţia anterioară se poate optimiza, precalculând cel mai mare divizor comun pentru toate secvenţele din şir în $O(n*n*log(valmax))$, pentru a verifica în timp constant efectul eliminării unui număr (se observă că rămân maxim 2 secvenţe compacte de numere după eliminarea unui număr, a căror c.m.m.d.c poate fi calculat uşor).Această soluţie are complexitatea $O(n*(n+q)*log(valmax))$, obţinând 35 de puncte, şi poate fi optimizată cu tehnici precum Range Minimum Query sau precalcularea în $O(valmax*valmax)$ a tuturor c.m.m.d.c posibili, dar nu este necesar.
Pentru a obţine 75 de puncte, ne vom baza pe 2 observaţii:
1.Pentru ca o secvenţă de numere să aibă c.m.m.d.c diferit de 1, trebuie ca toate numerele să aibă un factor prim comun.
2.Dacă alegem 2 elemente din secvenţă, cel puţin unul din ele va rămâne în secvenţa finală, din care a fost scos un element.
Ca o urmare a acestor 2 observaţii, putem vedea dacă un şir respectă condiţia din enunţ verificând dacă cel puţin un factor prim a oricăror 2 numere de pe poziţii diferite din secvenţă divide toate numerele în afară de unul (sau toate numerele).Ţinând o listă sortată cu poziţiile numerelor care divid un numar prim $p$, pentru fiecare număr prim $p$, putem folosi căutare binară pentru a determina câte numere din o anumita secvenţă divid un anumit număr prim în $O(logn)$.De asemenea, avem doar $O(logvalmax)$ numere prime relevante datorită celor 2 observaţii.
Pentru a obţine 100 de puncte, este necesară optimizarea următoare: în loc de căutare binară, în lista unui număr prim vom ţine pentru fiecare poziţie din listă cât de multe numere consecutive există dacă începem cu poziţia respectivă.Astfel, putem sări în $O(1)$, la prima poziţie din dreapta care nu divide un număr prim, verificând dacă putem acoperi întreaga secvenţă cu cel mult $2$ salturi.Astfel, complexitatea se reduce la $O(log)$ pe query.Precalcularea listelor se poate face cu un ciur şi o parcurgere a şirului.