Solutii Infoarena Monthly 2012 Runda 1

APM2

Restrictiile problemei permit ca o rezolvare de complexitate O(N * Q) sau O(N * Q * log*N) sa treaca toate testele.
Observam ca raspunsul pentru o anumita muchie de query (x y) este costul maxim al unei muchii pe drumul x -> y in APM-ul initial, din care scadem o unitate.
Pentru a demonstra acest lucru, ne folosim de urmatoarea proprietate a APM-ului: Daca o muchie (x y) inafara APM-ului inchide ciclu cu APM-ul, muchia aceasta este maxima pe ciclul in discutie. Revenind la problema noastra, daca asociem costul maxim - 1 muchiei noastre de query, aceasta formeaza acum un ciclu pe care nu este muchie maxima, deci va fi in APM. Pentru o idee mai intuitiva, ganditi-va ce se intampla cand rulam agloritmul lui Kruskal.

Avand aceste observatii se contureaza 2 solutii care intra in timp:
1. Pentru fiecare muchie de query se efectueaza un df pe APM-ul initial pentru muchia maxima pe drumul (x y). Complexitate O(M log M + N * Q);
2. Raspundem la query-uri in timpul constructiei APM-ului initial astfel: De fiecare data cand unim 2 componente conexe (adaugam o muchie in APM) , verificam pentru fiecare muchie de query daca acum are capetele in aceeasi componenta. In caz afirmativ, raspunsul este costul muchiei adaugate - 1. Complexitate O(M log M + N * Q * log*N);

Problema admite solutii mai rapide: O(M log M + N log N + Q log N) sau O(M log M + (Q + M) log M). S-a considerat ca aceste solutii sunt prea complicate pentru un concurs cu acest format, insa invitam utilizatorii sa le gaseasca ca exercitiu.

Bursa

Problema poate fi rezolvata printr-un algoritm greedy: Daca valoarea actiunilor pe ziua curenta este maxim local ( v[i - 1] < v[i] > v[i + 1]) vindem toate actiunile pe care le avem, iar daca este minim local (v[i - 1] > v[i] < v[i + 1]) cumparam cate actiuni putem. Nu are rost niciodata sa cumparam actiuni daca le putem cumpara mai ieftin a doua zi, sau sa vindem daca le putem vinde mai scump in ziua urmatoare, ceea ce ne conduce la concluzia enuntata anterior.
Ultima zi este caz particular, daca aceasta este minim local nu vom cumpara actiuni fiindca nu mai avem ocazia sa le vindem.

Trivia
Suma de bani creste exponential cu numarul de maxime locale. Daca va ofera cineva ponturi la bursa pentru o perioada asa indelungata, pregatiti-va sa scrieti numere mari pentru contul bancar. It's not worth the effort.

Paranteze2

Solutia cautata are complexitate O(n) si se foloseste de programare dinamica.
Astfel D[i] seminifica numarul de subsecvente parantezate corect care incep pe pozitia i.
Acest vector se poate calcula astfel pentru o anumita pozitie i: Fie next[i] pozitia pe care se termina prima parantezare corecta care incepe pe pozitia i. Atunci D[i] = 1 + D[next[i] + 1].
Pentru a calcula vectorul next[] in timp liniar, vom altera algoritmul clasic de verificare a unei parantezari, bazat pe o stiva.

for (i=1;s[i];++i)
		if (st.size() && s[st.top()]=='(' && s[i]==')')
			next[st.top()]=i+1,st.pop();
		else st.push(i);

	for (--i;i>0;--i)
		if (next[i])
			Din[i]= 1 + Din[next[i]],Rez+=Din[i];

Texttrim

Problema se rezolva respectand indicatiile din enunt, avand grija la detalii de implementare si cazuri particulare (de exemplu cazuri in care raspunsul este '...').
Una dintre solutiile oficiale:

int len = strlen(s);
	long long wdt = 0;
	int pos = -1;
	for (int i = 0; i < len; i++)
	{
		int letterWidth;
		if (s[i] == ' ') letterWidth = sizes[0];
		else letterWidth = sizes[s[i] - 'a' + 1];
		
		if (wdt + letterWidth <= fieldWidth - 3) pos = i;
		wdt += letterWidth;
	}
	if (wdt <= fieldWidth) puts(s);
	else { 
		for (int i = 0; i <= pos; i++) printf("%c", s[i]);
		printf("...\n");
	}