Problema Informatica - Olimpiada

[•RazvanInfo10]

Salut, sunt in clasa a-11-a, si ma bate la cap o problema de informatica:

Primăria a construit un nou centru pentru conferinţe. N companii şi-au manifestat interesul de a închiria centrul pentru a ţine propriile conferinţe. O companie client doreşte să închirieze centrul doar dacă acesta este disponibil pe întreaga durată a evenimentului. Primăria a decis că cea mai bună strategie de închiriere este aceea de a face un profit cât mai mare în urma închirierii, prin urmare va închiria centrul de conferinţe acelor companii în urma cărora va obţine un profit maxim. Pentru fiecare companie client se cunoaşte perioada pentru care doreşte să închirieze centrul de conferinţe, precum şi suma de bani pe care e dispusă să o plăteasca pentru inchiriere.
Cerinţă
Scrieţi un program care determină profitul maxim pe care poate să îl obţină primăria prin închirerea centrului de conferinţe

Exemplu:

profit.in:

6
1 5 6
4 7 3
7 10 8
2 4 2
6 12 9
9 11 5

profit.out:

15

Sunt oarecum incepator in Informatica, dar vreau sa stiu daca gandesc bine problema, parerea mea este:
Sa luam ex:1 5 6 --> In intervalul de timp: 1-5 s-a castigat 6, trebuie sa verific toate celelalte intervale de timp care sunt egale sau intre acestea, si sa comparam castigul ? De ex:
1 5 6
7 10 8
6 12 9
---> In intervalul 6-12 se castiga 9, iar in intervalul 7-12(este mai mic) dar se castiga doar 8, deci o sa se ia cel mai mare castig ?
O gandesc bine problema?Va rog sa-mi explicati ce gresesc si unde gresesc.
Multumesc mult.

[•PlayLikeNeverB4]

Ar fi util sa postezi si limitele pentru N si pentru intervale.

[•RazvanInfo10]

•   1 ≤ N ≤ 100000
•   1 ≤ a ≤ b ≤ 100000
•   Pentru 30% din teste, N ≤ 20.
•   Pentru 70% din teste, N ≤ 5 000.
Dacă o conferinţă are loc între momentele de timp a şi b,atunci se consideră că şi capetele a si b fac parte din conferinţă

[•PlayLikeNeverB4]

Problema se face cu programare dinamica. Initial sortezi intervalele dupa capatul din stanga.
Starea este dp[i] = profitul maxim dintre primele i intervale.
Fiind la intervalul i, ai doua variante: fie nu il alegi si mergi in dp[i + 1]; fie il alegi si mergi in dp[j], unde j este cel mai mic indice astfel incat intervalul j nu e inclus in intervalul i. Indicele j il poti afla prin cautare binara.
Deci, complexitatea finala: O(NlogN).

[•RazvanInfo10]

Foarte Complicat, nu pot face asa ceva in cod...

[•deneo]

Nasol atunci. Fa probleme mai simple.

[•freak93]

a si b sunt mici ca poate face O(N): DP = max(DP[i - 1], DP[a - 1] + 1 unde [a, i]  e un interval din alea N)

[•RazvanInfo10]

Am inteles, eu invat informatica singur acasa(clasa 11) si invat de 2 luni, ce spuneti este timp pana in februarie sa pot participa la olimpiada de Informatica(pana la judeteana, nu cer mai mult(inca nu am experienta)).Si vreau sa-mi dati niste sfaturi daca se poate cum sa invat, si daca am timp in acest interval.

[•freak93]

Intra pe arhiva educationala si incearca sa iti pui la punct cunostintele. Acolo problemele sunt explicate si au exemple. Cand ti se pare ca ai inteles pe deplin una din probleme ai sa gasesti la sfarsitul paginii o lista de probleme ce folosesc acel concept, incearca sa le rezolvi pe fiecare, dar daca nu iti ies nu te speria, unele necesita mult mai mult decat inveti din arhiva educationala.

[•RazvanInfo10]

Am inteles, eu sunt matematica-informatica(liceu) dar nu ma pricep prea bine la Matematica, stiu decat bazele(de maxim un 6 la bacalaureat) are vreun efect ? La facultatea de matematia-informatica, specializarea: Informatica, se pune mare accent pe matematica?

[•freak93]

La Universitatea Bucuresti da, e important sa iti pui bine la punct cunostiintele de mate pentru facultate, insa pentru informatica (olimpiada) cunostiintele de mate pana in clasa a 10-a sunt aproximativ suficiente,  ele pe care le dobandesti in clasele 11-12 sunt mai putin importante decat ce poti invata la informatica.