Solutii Happy Coding 2007

Abc2

Tritzi

Regine2

Rfinv

Pali

Furnica

Flori2

Bitmap

Cascaval

Cercuri3

Antitero

Sistem2

Optic

Zvon

Solutia "oficiala" are complexitatea O(N*logN) si presupune calculul urmatoarelor valori:

• TMIN[i] = timpul minim necesar pentru a propaga zvonul in subarborele lui i, din momentul in care i afla zvonul. In mod clar, TMIN¹ reprezinta rezultatul cautat.

Pentru a calcula TMIN[i], vom calcula intai valorile TMIN ale fiiilor lui i, pe care le vom sorta apoi descrescator: TMIN[f1] ≥ TMIN[f2] ≥ .. ≥ TMIN[fK]. Ordinea in care i va transmite zvonul fiilor sai este chiar ordinea descrescatoare a valorilor TMIN a acestora. In aceste conditii, TMIN[i] = maxim { 1 + TMIN[f1], 2 + TMIN[f2], .., K + TMIN[fK] }.

Probleme asemanatoare:
* Consilul tribului/BOI 2003
* Optic/Happy Coding 2007

Cerc2

Puteri2

Aimin

Multimi

Nrbanda

Tramvai

Biti3

Clear

H

Permavg

Kboard