Soluţii Junior Challenge 2012 - runda 1
Narbi
Problema cere să răspundem la întrebări de forma "câţi biţi de 1 se găsesc în scrierea binară numerelor din intervalul [1, Xi] ?". Deoarece Xi > Xi-1, avem Ri = Ri-1 + f(Xi-1+1) + f(Xi-1+2) + ... + f(Xi), unde f(x) este egal cu numărul de biţi de 1 din configuraţia binară a lui X. Mai notăm şi că, din modul de calculare a întrebărilor, valoarea maximă a lui XN este maxim VMax = 16 * N.
Soluţie O(VMax log VMax)
Putem calcula f(x) parcurgând toţi biţii din configuraţia lui x şi numărând, simplu, pe cei care au valoarea 1. Deoarece un număr x are maxim log2 x biţi semnificativi, vom avea complexitatea de O(log VMax) pe query. Această soluţie obţine 50 de puncte.
Soluţie O(VMax) amortizat
Observăm că atunci când adunăm 1 la un număr, în configuraţia sa binară se schimbă doar anumiţi biţi, în felul următor: se parcurg biţii începând cu cel mai nesemnificativ, iar toţi cei de valoare 1 se schimbă în 0, până când se întâlneşte un bit de 0, care devine 1. (de exemplu 100111 se transformă în 101000). Astfel, putem folosi această parcurgere pentru a calcula f(x) în funţie de f(x-1), astfel: f(x) = f(x-1) - last(x-1) + 1, unde last(x) este egal cu numărul de biţi de 1 de la finalul reprezentării lui x (cei număraţi în parcurgerea de mai sus). Numărul de operaţii efectuate pentru calcularea funcţiei last pentru numere de la 1 la N este N/2 * 1 + N/4 * 2 + N/8 * 3 + N/16 * 4 + ... care tinde la 2.46*N. Această soluţie obţine între 80 şi 100 de puncte, în funţie de optimizările făcute.
Soluţie O(VMax)
Dezvoltăm ideea precedentă pe baza observaţiei urmatoare: last(x-1) este egal cu poziţia celui mai nesemnificativ bit de 1 din configuraţia lui x. Cum putem izola cel mai nesemnificativ bit de 1 dintr-un număr? Mai întâi, putem să îl ştergem din configuraţia lui x cu operaţia (x and (x-1)), iar apoi să îl izolăm doar pe el făcând operaţia xor cu numărul iniţial. Aceste operaţii sunt de fapt funcţia LSB = (x and (x-1) ) xor x. (LSB este abreviere pentru Least Significant Bit). Totuşi, LSB returnează cea mai mică putere a lui 2, nu poziţia pe care se află bitul. Astfel, trebuie să ţinem un hash pentru a transforma rapid puterea lui 2 în poziţia bitului. Putem realiza un hash perfect (în care nu există coliziuni), pentru a evita verificări suplimentare). Pentru aceasta, soluţia oficială ţine următoarea funcţie de hash: hash(2X % 71) = X. Astfel putem calcula în O(1) valoarea lui last(x), complexitatea finală fiind O(VMax). Această soluţie obţine 100 de puncte.
Pokemon2
Soluţie O(N*M)
Mai întâi, este nevoie să observăm că, pentru fiecare Rare Candy dat unui pokemon aflat pe poziţia i, trebuie să oferim câte un Rare Candy tuturor pokemonilor de pe poziţiile i+1 ... N. Mai întâi vom dori să scăpăm de restricţiile impuse de diferenţele care trebuie să existe între pokemoni. Aceste restricţii consumă încă de la început Rare Candy-uri, mai exact S = dif1,2 * (n-1) + dif2,3 * (n-2) + ... + difn-1,n * 1. Astfel, ne rămân Mf = M - S Rare Candy-uri de împărţit.
De aici, problema se rezolvă cu programare dinamică, astfel: calculăm di,j, numărul de moduri să împărţim j Rare Candy-uri la primii i pokemoni. Recurenţa este următoarea: di,j = di-1,j + di,j-(n-i+1). Mai detaliat, putem fie să începem chiar de acum să dăm Rare Candy-uri lui i (şi venim din di-1,j), sau îi mai dăm un Rare Candy lui i şi implicit tuturor pokemonilor de pe poziţiile i+1 ... N, (şi venim din di,j-(n-i+1)). Această soluţie obţine 40 de puncte dacă reţinem toată matricea (şi vom avea complexitate a memoriei O(N*M)), sau 100 de puncte dacă reţinem doar ultimele 2 linii ale matricei.
Snooker
Soluţie O(K * NrMante4)
Observăm că dacă lovim bila albă cu o singură mantă, astfel încât după ricoşeu să treacă printr-un anumit punct, prelungirea traiectoriei sale iniţiale va trece prin imaginea punctului reflectat, ca în oglindă, de pe mantă. (vezi figura).
De aici ne vine ideea să reflectăm întreaga masă (însemnând poziţiile bilelor roşii şi ale punctelor-ţintă) de 5 ori în sus şi în jos, iar apoi să reflectăm masa astfel prelungită de 5 ori înspre stânga şi înspre dreapta. Astfel, vom obţine o masă de dimensiuni 11*N pe 11*M.
Acum trebuie doar să verificăm pe rând pentru toate punctele de interes dacă vreo bilă roşie intersectează segmentul dintre poziţia iniţială şi punctul vizat. Putem face acest lucru verificând dacă triunghiul determinat de cele 3 puncte are înălţimea din punctul asociat bilei roşii mai mică decât 2, caz în care avem intersecţie, sau aplicând formula distanţei de la un punct la o dreaptă. Mai trebuie să avem grijă ca punctul de intersecţie să se afle pe segment, verificând dacă distanţele de la bila roşie la bila albă sau la punctul de interes sunt ambele mai mici decât baza triunghiului.
Deoarece avem NrMante2 puncte de interes şi K*NrMante2 bile roşii, complexitatea finală este O(K * NrMante4). Această soluţie obţine 100 de puncte.
