Editorial Runda 8

Mihai Calancea
14 septembrie 2012

Inaugurăm prin acest blogpost o serie de editoriale care, sperăm noi, îşi vor face apariţia după fiecare rundă a concursului Infoarena Monthly. Scopul lor este de a augmenta latura educativă a concursului prin explicarea detaliată a soluţiilor problemelor propuse. Sperăm de-asemenea ca secţiunea de comentarii să devină o platformă potrivită pentru discuţii şi feedback despre subiecte şi despre formatul concursului în sine. Suntem conştienţi că o asemenea iniţiativă apare destul de târziu, concursul fiind deja în runda cu numărul 8, însă am considerat că o atitudine de tip "Las' ca începem de luni, asa se face treaba" n-ar fi fost foarte inspirata. Avand in vedere ca urmatorul "Luni" al Monthly-ului este practic in 2013. Acestea fiind zise, let s get to work.

Runda 8 a avut 91 de concurenţi înscrişi şi 79 de concurenţi care au submitat cel puţin o sursă. Echipa a subestimat însă dificultatea setului ales, astfel doar 2 concurenţi au terminat concursul având 3 probleme rezolvate, iar una dintre probleme nu a fost rezolvată corect de nimeni. Dacă ar fi să luăm ca referinţă concursurile de tip ACM, se spune că un set de probleme este bun dacă fiecare problemă este rezolvată de către cineva, dar nimeni nu rezolvă toate problemele. We're not quite there yet, dar ne străduim :).

Switch

O primă idee care poate rezolva această problemă este cea de a descrie un graf cu 16 noduri (fiecare matrice posibila) şi 4 arce care ies din fiecare nod (transformarile posibile). Astfel, se poate face un DFS pe acest graf pentru a se afla daca exista conexitate intre matricele date in input. Dacă problema ar fi cerut şi numărul minim de operaţii necesare, soluţia ar fi fost dată de o parcurgere în lăţime.

Însă această problemă are o soluţie mult mai scurtă, pe care mulţi concurenţi au intuit-o şi au implementat-o. Graful are de fapt doar două componente conexe. În prima se află matricele cu număr par de 1, iar în cealaltă cele cu număr impar. Pentru a demonstra acest lucru, observaţi că o operaţie de negare nu schimbă niciodată paritatea numărului de 1 (De ce?). Faptul că din orice matrice pară se poate ajunge in orice altă matrice pară este destul de evident, în special fiindcă multe dintre configuraţii sunt doar oglindiri/rotiri ale celorlalte.

Prima soluţie este mai flexibilă, iar corectitudinea ei nu depinde niciodată de particularităţile transformărilor sau ale matricelor, putând fi folosita şi pentru matrice de N x N. Ea are complexitate O(2 ^ N * M), unde M este numărul de transformări posibile. Cea de a doua soluţie are însă complexitate O(1) şi se scrie in 2 rânduri.

Cifre3

Această problemă avea în primă fază alt enunţ, iar cele 2 surse oficiale au la baza ideea problemei iniţiale. Astfel, marea majoritate a concurenţilor a ajuns să aiba o soluţie mult mai scurtă şi mai eficientă. Soluţia noastră se folosea de faptul ca numărul produselor posibile nu este foarte mare, din 2 motive.

1. Toate numerele trebuie să aibă ca factori primi doar numere din mulţimea 2 , 3 , 5 , 7, deoarece acestea sunt singurele cifre care sunt numere prime.
2. Având în vedere că numărul de cifre este limitat de 20, puterea maxima a lui 2 este limitată de 60 (numărul format din 20 de cifre de 8), cea a lui 3 de 40 , iar cele ale lui 5 si 7 chiar de catre 20.

Deci există maxim 60 * 40 * 20 * 20 = 960 000 de produse posibile. Observaţi că această margine superioară este o supraestimare destul de puternică, având în vedere că exponentul maxim nu poate fi atins de fiecare cifră în acelaşi timp.

Astfel, am putea să variem exponentii pentru fiecare dintre cele 4 cifre prime şi apoi să hotărâm pentru fiecare configuraţie daca se poate obţine dintr-un număr cu lungime între A şi B. Pentru a simplifica problema, observăm că dacă Lmin ar fi numărul minim de cifre necesar pentru a obţine numărul X, atunci pentru orice lungime L mai mare sau egală decât Lmin există un număr de lungime L care îl poate produce pe X. Adăugăm L - Lmin 1-uri in coadă. Pretty simple huh?. Numărul A devine astfel irelevant. Tot ce trebuie sa verificăm pentru un anumit număr X este dacă Lmin(X) este mai mic sau egal cu B.

Acest lucru se poate face printr-o abordare de tip greedy, ilustrată în fragmentul de cod de mai jos, extras din sursa lui Rareş Buhai, primul concurent care a rezolvat problema în timp de concurs.

int getNum(int x)
{	
	int result = 0;
	if (x != 1) ++result;
	for (int c2 = 0; c2 <= 3 * x; ++c2)
		for (int c3 = 0; c3 <= 2 * x; ++c3)
			for (int c5 = 0; c5 <= x; ++c5)
				for (int c7 = 0; c7 <= x; ++c7)
				{
					int minneed = c5 + c7, addmin = 100000;
					for (int k = 0; k <= min(1, min(c2, c3)); ++k)
						addmin = min(addmin, k + (c2 - k) / 3 + (c3 - k) / 2 + ((c2 - k) % 3 != 0) + ((c3 - k) % 2 != 0));
					minneed += addmin;
					
					if (minneed <= x)
						++result;
				}
	return result;
}

Acestea fiind zise, vă prezentăm soluţia lui Mihai Popa, a doua submisie corectă în timp de concurs.

int p = 3,add = 3;
	for ( int i = 2 ; i <= b ; ++i ){
		p += add;
		++add;
	}
	
	fprintf(g,"%d\n",p*p+1);

Demonstraţia o lăsăm ca tema acasă. Extindeţi raţionamentul de mai sus, potrivit căruia numerele de lungime L produc aceleasi produse ca numerele de lungime L - 1 şi, pe lângă acestea, unele noi pe baza celor vechi.
De notat că deşi soluţia lui Rareş (ca şi cea a comisiei..) este mai complexă şi mai greu de codat, are avantajul că necesită un timp scurt de gândire, fiindca este practic un brut. Alegerea unei soluţii nu neaparat eficiente sau scurte, dar care rezolvă problema în restricţiile date este uneori de preferat în dauna unei implementări simple cu idei uşor mai complicate, mai ales într-un concurs de tip Monthly, Codeforces, sau TC SRM.

Culori4

Deci contribuţia problemei ăsteia la concurs a fost o coloană de 0 adaugată în clasament?

Deşi problema pare să ceară fie o dinamică, fie un back optimizat până ajungi să dispreţuiesti autorul ca entitate prezentă pe Pământ, soluţia e de fapt destul de mişto. În general, problemele de colorare în sine sunt NP-complete, i.e se presupune ca nu admit soluţie în timp polinomial. Nu prea bag mâna în foc că acest caz particular este de asemenea NP-Complete^*, însă presupun că cel puţin problema de numărare a colorărilor este. (Dacă mă contraziceţi, aş fi chiar entuziasmat :D).

Să rezolvăm o variantă mai simplă a problemei. Să presupunem că nu există două caractere ? alăturate. Astfel, culoarea unui anumit semn de întrebare nu afecteaza colorarea altui semn de întrebare. Putem deci răspunde cu o formula.
ANS = p1 * p2 * p3 * ... pk unde pi este numărul de posibilităţi de a colora al i-lea semn de întrebare.

Dacă ar fi să privim matricea ca o tablă de şah, facem observaţia critică conform căreia celulele albe sunt independente complet de cele negre. Mai precis, toate celulele albe au doar vecini negri iar celulele negre au doar vecini albi. Aşa că presupunând că toate celulele albe sunt fixate (pentru fiecare ? de casuţă albă am ales deja culoarea) putem doar să trecem prin cele negre şi să înmulţim pentru fiecare ? numărul de valori pe care le poate lua semnul de întrebare respectiv, conform formulei precedente. Având în vedere că K, numărul de ?, este mai mic sau egal cu 18, atunci fie numărul de semne de întrebare albe este mai mic sau egal decât 9, fie cel de semne de întrebare negre este mai mic sau egal decat 9. Obţinem astfel o complexitate de timp O(5 ^ (K / 2) * K).

Triangles

Prima soluţie care ne vine în minte are complexitate O(N log N) şi nu se încadrează în timp. Pentru a ajunge la ea, realizăm ca întotdeauna are sens ca numerele alese să formeze o secvenţă continuă în şirul valorilor sortate. Pentru o anume secvenţă din şirul sortat, putem afla dacă toate cele K elemente din ea sunt bune verificând ca v[i] + v[i + 1] >= v[i + K - 1]. Cu alte cuvinte, verificăm ca cele mai mici două numere sa poată forma triunghi cu cel mai mare dintre ele (acesta este practic cazul limită. Daca vreun alt triplet nu îndeplineşte condiţia asta, atunci nici tripletul acesta nu o va îndeplini). Această idee se implementează foarte uşor, însă sortarea necesită timp O(N log N). Poate dacă parsăm? Nope. Radix sort? Nope.

Soluţia bună are o linie in plus faţă de cea descrisă anterior. Ideea este ca de fapt nu o să avem nevoie niciodată de toate cele N numere pentru a găsi o soluţie printre ele. Este suficient să păstrăm doar primele K * log(2, Vmax) numere. Valoare care in cazul de faţă este egală cu 150 000. De ce? Gândiţi-vă ce înseamnă dacă o anumită secventă (i , i + K + 1) nu reprezintă soluţie. Rezultă că v[i + K - 1] > v[i] + v[i + 1]. Deci V[i + K - 1] > 2 * v[i]. Cu alte cuvinte, cât timp nu găsim soluţie, odată la cel mult K numere, valorile se dubleaza. Dar numerele nu pot fi mai mari decat 10 ⁹, deci numărul de dublări este limitat de log(2, 10 ^ 9), care este aproximativ 30. Astfel complexitatea devine O((K log Vmax) log (K log Vmax)), iar linia despre care vorbeam este

n = min(n , 150 * 1000);