Revizia anterioară Revizia următoare
Problema A
Este evident ca produsul maxim ar fi obtinut prin inmultirea celor mai mari trei numere din sir. Fie M1, M2, M3 cele mai mari 3 numere din sir, iar P1, P2, P3 pozitiile pe care se afla acestea. Pentru simplitatea explicatiei, vom trata cazul in care P1 < P2 < P3. Pentru acest caz, vom alege subsecventele: [1, P1], [P1 + 1, P2], [P2 + 1, P3]. Cum maximul din prima subsecventa este M1, maximul din cea de-a doua subsecventa este M2, iar maximul din cea de-a treia subsecventa este M3. Deci, produsul maxim a fost obtinut, si anume M1 * M2 * M3. Analog si pentru celelalte cazuri.
Problema cu becuri
Raci
Suma5
Solutie prototip: (nonfinala)
Problema este o aplicatie clasica a arborilor de intervale cu lazy propagation. Fiecare nod al arborelui de intervale va retine informatii legate de:
- Capatul stang al intervalului (st)
- Capatul drept al intervalului (dr)
- Suma elementelor din interval (s1)
- Raspunsul la un query fix pe acel interval (s2)
Acum singura problema care ne mai ramane este unirea a doua noduri a si b intr-un singur nod c (altfel spus, unirea a doua jumatati de interval intr-un singur interval, mentinand toate informatiile de mai sus). Informatiile legate de capetele noului interval sunt usor de calculat dupa urmatoarele formule intuitive:
a.st = b.st;
a.dr = c.dr;Calcularea sumei noului interval se obtine prin adunarea sumelor intervalelor a si b.
a.s1 = b.s1 + c.s1;Calcularea noului s2 este putin mai complexa:
a.s2 = b.s2 + (c.s2 + c.s1 * (b.dr - b.st + 1) );Problema a fost aleasa drept cea mai grea problema a setului pentru ca rezolvarea presupunea cunoasterea si aplicarea teoriei, dar si o atentie sporita intr-o implementare laborioasa.
