|
Titlul: Interviewstreet Scris de: Andrei Misarca din Noiembrie 06, 2011, 02:14:55 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/ (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 (http://www.interviewstreet.com/recruit/challenges/solve/view/4e1491425cf10/4e80227a603af) 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? Titlul: Răspuns: Interviewstreet Scris de: Andrei Grigorean din Noiembrie 06, 2011, 17:27:58 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). Titlul: Răspuns: Interviewstreet Scris de: Andrei Misarca din Noiembrie 06, 2011, 21:19:17 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?
Titlul: Răspuns: Interviewstreet Scris de: Andrei Grigorean din Noiembrie 06, 2011, 21:23:53 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. |