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 educativa a concursului prin explicarea detaliata a solutiilor problemelor propuse. Sperăm de-asemenea ca secţiunea de comentarii să devină o platforma 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 Ş).

Problema 1 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.

Problema 2 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Ş

*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.
*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 poate î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ş, 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.

Problema 3. Culori4

_Deci contribuţia problemei ăsteia la concurs ar fi o coloană de 0 adaugată în clasament?
Şerban Stan._