Salve a tutti,
qualcuno è riuscito a risolvere il problema Bug?
Non mi è chiarissimo l’algoritmo da adottare.
La strategia gready con coda a priorità mi è di difficile comprensione.
Grazie a tutti 
Davide
Un metodo alternativo è l’utilizzo di un Segment tree, ma è più complicato per uno che non ha dimestichezza.
Comunque l’idea di base è: supponiamo che posso risolvere i bug in T giorni, quali problemi dovrei scegliere per ottenere un risultato uniforme?
Quindi tu suggerisci di
con T a partire da 1 a crescere,
vedo se è possibile distribuire i bug con code di T per ogni studente, in modo che la coda più lunga sia al massimo T ?
Nope!
Semplifichiamo il problema: tutte le complessità sono uguali a 1, tutti gli studenti hanno costo 1.
Immagina di avere la fila dei bug: quanti studenti devi assumere per terminare in esattamente T giorni?
Una volta che hai risolto questo problema aggiungiamo un grado di difficoltà: complessità=1, costi diversi.
Infine completi con complessità e costi diversi. 
In questo caso ogni singolo bug degli M a disposizione può essere assegnato arbitrariamente a qualsiasi studente.
Per terminare esattamente in T giorni significa che la pila coda più lunga deve essere di lunghezza T. Quindi deve valere upper(M/T) = N.
Giusto?
No, ammetto che non ne esco fuori… e che non ci sto capendo nulla
Whooops mi ero completamente dimenticato di rispondere!
Comunque non pensare alle code o alle pile, pensa semplicemente agli studenti che assumi come dei separatori per la tua lista dei bug.
L’osservazione è corretta: per finire in T giorni è necessario che lo studente che risolve più bug ne risolva esattamente T.
Però possiamo notare anche un’altra cosa: conviene sempre prendere il più basso numero di studenti possibile, ciò significa che gli studenti assunti con meno di T bug da risolvere saranno al più 1.
Puoi schematizzare la cosa in questo modo (immaginiamo di voler risolvere 10 bug in 4 giorni):
SBBBB.SBBBB.SBB
Ora il passo successivo: complessità=1, costi differenti.
Quali studenti mi conviene sempre scegliere?
Quest’osservazione è corretta se si punta alla minimizzazione del numero di studenti impiegati. Infatti volendo risolvere in T giorni, sfrutto uno studente al massimo, finchè non mi risolve effettivamente T bug. Non appena cerco di risolvere il bug T+1 degli M, allora impiego un altro studente. Alla fine mi rimarrà uno studente con M-(N-1)*T bug da risolvere.
In questo caso conviene scegliere gli studenti con costo più basso. Quindi ho M bug da distribuire a N studenti in modo tale che ogni studente abbia T bug da risolvere. Il primo gruppo di bug viene affidato allo studente meno oneroso (quindi potrei avere la lista di studenti ordinata per costo crescente). Non appena saturo questo studente vado a quello di costo superiore (o uguale).
La cosa che mi sconcerta è che io non so a priori quanto vale T, essendo T una funzione da minimizzare.
Intendevo dire questo infatti: esiste al massimo uno studente tra quelli assunti che ha meno di T bug da risolvere, quindi il numero di studenti impiegato con la restrizione di finire in esattamente T giorni è minimo.
Benissimo, scegli gli studenti che costano meno.
Ora aggiungiamo l’ultimo step: anche le complessità sono diverse da 1, come ti comporti?
Sfrutta le osservazioni fatte fino adesso: raggruppare i bug a gruppi di T e assegnare ogni gruppo ad uno studente che abbia costo minimo.
Per quanto riguarda la tua domanda su T: è vero, noi stiamo cercando di minimizzare T, ma prima di minimizzare T dobbiamo trovare un modo efficiente per calcolare il costo di terminare in un certo T. 
Una volta che sappiamo calcolarlo potremo passare a minimizzarlo!
Hum, allora.
I Bug possono ora essere ordinati per complessità decrescente. Quindi a partire dal primo bug, lo assegno al primo studente capace di risolverlo (qui si introduce il concetto di complessità), ma di costo minimo. Degli N studenti infatti potrei averne N’ in grado di risolvere tale bug, ma devo prendere quello che costa meno. E una volta sfruttato questo studente, lui è in grado di risolvermi altri T-1 bug…tanto se è riuscito a risolvermi il primo, può tranquillamente risolvermi i successivi…visto che i bug sono ordinati per complessità decrescente.
Una volta saturato lo studente (mi ha risolto T bug), passo al prossimo gruppo di T bug e ripeto.
Esatto!
Ora ci rimane un problema: come prendo effettivamente gli studenti?
Metodo 1: O(N)
Una volta che so la complessità che devo affrontare, mi basta cercare linearmente nel mio array degli studenti quello che costa meno ma che sa anche risolvere il gruppo di bug.
Puoi migliorare leggermente la ricerca ordinando gli studenti in ordine crescente di costo così da fermarti al primo studente che non hai ancora preso in grado di risolvere il gruppo di bug, ma la complessità al caso peggiore è sempre O(N).
Metodo 2: O(logN)
Ecco che entra in gioco la coda di priorità che non riuscivi a comprendere.
Se io ordino gli studenti in ordine decrescente di abilità, preso il gruppo di bug, posso inserire in coda i costi di tutti gli studenti che riescono a risolvere il primo bug del gruppo.
A questo punto so che in cima alla coda ( metodo .top() ) ci sarà il costo che ha più priorità: generalmente è il valore più alto nella coda, però con qualche accorgimento possiamo organizzare la coda in modo che in cima ci sia il valore più basso.
Per fare ciò possiamo definire una classe di Compare con un operator() o più semplicemente possiamo inserire i costi nella coda cambiati di segno: in questo modo in cima alla coda ci saranno i costi in valore assoluto minori (ovviamente cambiati di segno).
Da notare anche che se la coda è vuota significa che non ci sono studenti in grado di risolvere il bug proposto, perciò non mi sarà possibile risolvere i bug in T giorni!
Dato che inserire un elemento in una priority_queue ha costo (logN) e che la ricerca del minimo è O(1) ( basta sfruttare il metodo .top() ) la complessità totale della singola ricerca è O(logN).
Metodo 3: O(logN) con Segment Tree
Un altro metodo che mi viene in mente è l’utilizzo di un Segment Tree.
Ordiniamo gli studenti in ordine crescente di abilità: se dobbiamo risolvere un bug di complessità C possiamo cercare tramite una ricerca binaria il primo studente che ha abilità A≥C; supponiamo che si trovi in posizione x.
Dobbiamo cercare lo studente libero tra tutti gli studenti ∈[x,n) che abbia costo minimo.
Per fare questo possiamo utilizzare un Segment Tree e appena scegliamo lo studente possiamo aggiornare l’albero con un nuovo costo minimo.
La ricerca binaria ha costo O(logN) e la ricerca con l’albero e l’aggiornamento del minimo hanno sempre costo O(logN) perciò il costo totale è O(logN) per singola ricerca.
Dato che dobbiamo effettuare M/T = O(M) ricerche, con il primo metodo otteniamo una complessità O(MN) mentre con gli altri due O(MlogN).
Adesso che sai come comportarti con un generico T, come lo minimizzi?
In questo caso potrei a monte ordinare gli studenti. Il qsort permette di specificare una funzione di comparazione per determinare quando uno studente è “minore”, “maggiore” o “uguale” ad un altro. Quindi posso combinare i criteri:
- Se uno studente ha abilità maggiore rispetto ad un altro allora lo precede.
- A parità di abilità uno studente con costo inferiore precede un altro con costo superiore.
In questo modo ho studenti ordinati per abilità decrescenti e a parità di abilità sono ordinati per costo crescente.
Immagino che su ogni studente debba essere anche usato un flag per capire se è stato “usato” o meno.
SegmentTree cerco di guardarlo meglio.
Coda con priorità così così. Ma il concetto c’è.
Bhe T ha come lower bound upper(M/N) e come upper bound M (un solo studente è in grado di risolvere tutti i bug compatibilmente coi vincoli).
Quindi nel migliore dei casi posso avere un T pari a upper(M/N). Provo con questo T, se non riesco allora faccio T++.
Nel peggiore dei casi un algoritmo basato su coda ci mette O(M)*O(MlogN).
qsort dimenticalo, è molto più efficiente sort della libreria algorithm.
In ogni caso l’osservazione è corretta: possiamo provare con il T più basso e incrementarlo finché non trovo un T fattibile, la complessità al caso peggiore sarà appunto O(M2logN).
Una soluzione del genere prende 100/100 probabilmente per la debolezza dei testcase oppure per ragioni random legate alla struttura del problema (un po’ com’era successo per Stringhe di Fibonacci dove una soluzione quadratica con N=106 otteneva punteggio pieno).
Esiste tuttavia un’ultima osservazione da fare: la natura del problema permette di ottimizzare ancora la ricerca del Tsol.
Puoi notare infatti che se definiamo S(T) come risposta alla domanda “Esiste una soluzione per T giorni?” e in particolare S(T)=0 se non esiste e S(T)=1 se esiste, allora siamo sicuri che:
- S(T)=0 ∀ T < Tsol
- S(T)=1 ∀ T ≥ Tsol
- S(0)=0
- S(M)=1
Possiamo quindi sfruttare queste osservazioni per cercare Tsol tramite ricerca binaria in O(logM) migliorando quindi il costo a O(MlogMlogN)
Quest’ultima osservazione è molto interessante.
Quindi esplorare T_i tra T_{min} e T{max} in maniera intelligente.
Imposto T_i = (T_{max}+T_{min})/2. Valuto Ti e se è 0 allora il nuovo T_i = (T_i+T_{max})/2, altrimenti Ti = (T_i+T_{min})/2.
etc…
PS: come fai a scrivere le formule nei tuoi post?
Yup!
La ricerca binaria è una tecnica molto potente!
Quando ci sono problemi dove ti chiedono la condizione minima perché si verifichi qualcosa controlla sempre che possa essere applicata questo tipo di ricerca.
Comunque per quanto riguarda le formule utilizzo semplicemente i tag HTML oppure inserisco le lettere che voglio evidenziare tra due $ (quest’ultimo comando non so a che linguaggio appartiene sinceramente °L°)
Ad esempio O(N) viene visualizzato come O(N)
Perfetto. Ora mi metto all’opera e poi ti dico.
Il forum utilizza MathJax (che permette di visualizzare formule scritte in un sottoinsieme del linguaggio \LaTeX). Qui trovi un tutorial su come scrivere le formule: MathJax basic tutorial and quick reference - Mathematics Meta Stack Exchange
1 Mi Piace
Era voluto 
Cito dalla sintetica soluzione che avevo scritto:
Ma ordinare l’array degli studenti nel modo che ho spiegato prima, non dovrebbe risolvere il problema della ricerca? io ho sempre in testa (o posizione i che scorre) lo studente più promettente in termnini di competenze e costo… ?
o no?
Una volta che assumi uno studente come fai a trovare il nuovo studente minimo?
Devi ripassarti tutti quelli visti in precedenza più alcuni nuovi che sono in grado di risolvere il nuovo gruppo di bug! 
Quindi ordinare è un euristica che al caso peggiore non cambia molto la complessità O(NM)