Interviewstreet

[•Mishu91]

Am descoperit de curand un site destul de misto cu cateva probleme de antrenament si cateva probleme cu care zic ei ca aplici la niste firme. http://www.interviewstreet.com/ e site-ul. Ca sa vedeti problemele trebuie sa fiti logati, dar un "Sign in with Facebook" e suficient.

Dintre problemele de antrenament mi-a placut asta asta dar nu ma prea prind ce structura de date ar trebui folosit ca sa iasa complexitatea O(TlogT) sau O(TlogD). Are careva vreo idee?

[•wefgef]

Avînd un algoritm care îți spune dacă poți respecta toate deadline-urile, poți căuta binar răspunsul.

Ai task-urile sortate după deadline (faci asta la început, în afara căutării binare). Dacă la fiecare pas i suma minutelor necesare efectuării primelor i taskuri este mai mică sau egală cu deadline-ul i e OK.

Ai complexitatea O(M log T) pe query, în total O(M^2 log T).

[•Mishu91]

Nu am inteles exact la ce ajuta sortarea, pentru ca raspunsul fiecarui query este dat de primele i taskuri in ordinea in care apar. Si inca un lucru, de ce ai acolo M queryuri?

[•wefgef]

Nevermind, am citit prost enuntul.

Soluție bună:

Pentru un set de puncte fixat vrei să vezi care e răspunsul. Sortezi taskurile dupa D, faci sume partiale dupa M, si vezi diferenta maxima dintre SumaPartialaM[ i ] - D[ i ]. Pentru a rezolva problema dinamic poti folosi un aint.