I miei bug sono ordinati per difficoltà.
gli studenti sono ordinati per abilità decrescente. A parità di abilità sono ordinati per costo crescente.
Quindi in posizione i=0 ho lo studente più capace ed economico. A lui affido T bug da risolvere. Dopo di che ho lo studente i=1 e a lui faccio risolvere altri T bug…
E chi ti dice che è necessario assumere lo studente più bravo per risolvere il primo gruppo di bug?
Devi anche tenere in considerazione la quantità S di punti che puoi offrire (di cui non abbiamo parlato in questa discussione): per assurdo potresti dare il primo gruppo di bug all’ultimo studente nella tua lista perché è meno qualificato del primo ma costa molto meno e la sua abilità è sufficiente!
Bhe il fatto che i bug siano ordinati per complessità…I bug più difficili li affido allo studente più bravo (approccio Gready).
Oppure non ho capito il discorso che abbiam fatto prima?
- Caso semplice. M bug li ripartisco uniformemente tra gli N studenti in modo da avere code di T bug per ogni studente
- Costi differenti. Scelgo gli studenti con costo più basso di volta in volta.
- Complessità differenti. Scelgo il più capace e il più economico per risolvermi il primo gruppo di bug (che sono i più difficili). Etc…
Nope: preso un gruppo di bug, lo cedo allo studente più economico che è in grado di risolverlo, non al più bravo!
Non è la stessa cosa 
Esempio:
- Bug: 1 1 1 1
- (Abilità,Costo): (100,100) (100,200) (1,10) (1,15)
- Punti disponibili: 100
Secondo il tuo ragionamento non potresti ottenere una soluzione migliore di T=5 perché ogni volta assumi il primo studente (più bravo ed economico) che consuma tutto i punti.
Invece la soluzione ottima sarebbe T=2 assumendo gli ultimi studenti.
uhm, ora mi è chiaro. E con qualche forma di ordinamento non è possibile ottenere in O(1) lo studente più economico e in grado di risolverlo ?
Solo con il metodo della coda di priorità (che comunque è O(logN) all’inserimento).
Che complessità hanno questi due algoritmi. Ero convinto che qsort replicasse il QuickSort con complessità O(NlogN)
std::sort() implementa una versione ottimizzata del QuickSort, solita complessità O(NlogN) ma è molto più rapido nella pratica.
Inoltre è più facile da usare (soprattutto in gara) in quanto non devi fare casini con i puntatori.
e qsort? Anche lui mediamente ha complessità O(NlogN) ?
Sisi 
E inoltre c’è std::stable_sort() che implementa, se non erro, MergeSort con complessità O(NlogN) anche al caso peggiore, ma generalmente è più veloce std::sort().
Se non sbaglio qsort è O(NlogN) nel caso medio, ma O(N^2) nel caso peggiore. std::sort(), invece, è O(NlogN) anche nel caso peggiore.
quante cose imparo…
Sto provando a svolgere questo esercizio seguendo il tuo metodo, e per adesso sto cercando di sviluppare la funzione che mi verifica se posso finire il lavoro in t giorni ma c’è un problema io per testarla la provo con k=t in modo di verificare se riesco a portare a termine il lavoro anche con il massimo dei giorni , ma in 6 subtask mi da la determinazione si/no sbagliata.
Questo è il codice(scusa per il disordine 
https://pastebin.com/Gi5sYmV5
Come strutture sto utilizzando:
-una deque ordinata per gli errori
-una matrice per gli studenti che tiene conto di capacità costo e se ho gia usato lo studente precedentemente(ho dovuto aggiungere un campo bool per questo compito perche non posso rimuoverlo non essendo una coda)
La funzione l ho sviluppata in questo modo, sapendo t i ed il numero degli studenti calcola quanti esercizi devo dare ad ogni studente e poi lo studente lo ricerca con una semplice ricerca lineare prendendo il piu economico fra quelli che lo sanno fare. Gli errori che secondo me faccio sono legati alle strutture ossia non sono le strutture adeguate,(infatti quando cerco lo stidente io ho la matrice che li ordina per capacita e poi per costo e quando trovo quello con la capacita minima e che costa di meno lo prendo ma in realta se uno ha una capacità maggiore e costa di meno dovrei prendere lui) se riesci a dargli un’occhiata mi faresti un favorone
Mi ero completamente dimenticato di questo problema 
Premesso che non sono proprio un asso a debuggare (infatti spesso a volentieri non riesco a debuggare nemmeno il mio di codice 
), noto che stai facendo un po’ un miscuglio di idee 
Le prime cose che noto sono queste:
- Non hai bisogno di applicare il metodo del tempo T per sapere se la lista di bug è “risolvibile”
- Nel caso volessi farlo, quando elimini gli errori dal fondo della
dequelo fai rispetto all’indiceiche ha poco a che vedere con gli errori. Piuttosto direi di eliminare i primitpartendo dal fondo
- Un’altra cosa che non mi torna è come gestisci il
whileuna volta che sai cheA[conta].capa>=diff. In pratica riparti da 0 e continui a cercare finchéA[i].capa>diff, non sarebbe meglio partire dai=contae continuare finchéA[i].capa>=diff? Prova a pensarci!
Ripeto che non sono proprio bravo a debuggare codice altrui, probabilmente ho capito male alcune cose che hai scritto, nel dubbio continua a chiedere se hai bisogno e sicuramente io o qualcun altro riusciremo ad aiutarti!
Innanzitutto grazie per l’aiuto poi
-Lo so che non mi serve farlo per l output finale (provare la funzione con tempo t) ma lo volevo fare per capire se l algoritmo della funzione fosse giusto ossia se tutte le risposte si/no fossero state correte allora sarei passato al passo successivo
- Hai ragione una svista mia
-Il while lo uso in un modo complicato e non necessario al problema ma necessario per le strutture che utilizzo , perche usando una matrice(soluzione sicuramente non ottimale) non posso per effettuare per esempio una pop allora metto la variabile diponibile a false e poicon il while evito quelli con il false.
E comunque ho corretto con la i con la t ma i subtask che sbaglio sono ancora gli stessi, credo che l’errore lo compio è con gli studenti perche credo di fare dei casini con la matrice. Tu che struttura hai usato per gli studenti?
E anche se non centra visto che sembri molto preparato posso chiederti se stai facendo ancora le superiori ?
Scusa per il ritardo, comunque tornando al while, la cosa che non mi torna è perché metti un > al posto di >=, nel senso che tu nell’if trovi il primo studente che ha l’abilità per il problema più difficile che ti rimane, tuttavia con il while lo vai a perdere!
Esempio, il problema più difficile che devi risolvere ha difficoltà 10, gli studenti sono ordinati in ordine decrescente di abilità in questo modo [10, 10, 10, 1].
Il tuo scopo sarebbe, una volta trovato il 10 più a sinistra, andare a prendere quello più a destra (che è il meno costoso tra loro) tuttavia a causa della condizione “diversa” del while, ti fermi ancora prima di iniziare a cercare.
Un altro problema con questo metodo è che tu nell’idea del while vai a scegliere il più “a destra” tra quelli che possono risolvere il bug più complesso, tuttavia potrebbe essere che il più a destra è anche il più costoso e ha un costo proibitivo rispetto alla somma S (non so se mi sono spiegato bene, provo a fare un esempio).
Studenti (abilità, costo): [(20, 1), (10, 10), (10, 5), (10, 5), (1, 1)].
Bug (complessità): [1, 5, 10]
Somma disponibile: 2
Con l’if vai a beccare lo studente (20, 1), successivamente con il while (supponendo la condizione >=, perché la versione > abbiamo già visto essere problematica) ti fermi al (10, 5) e concludi che la somma disponibile non è sufficiente, tuttavia lo sarebbe stata per la coppia (20, 1).
Si hai perfettamente ragione, mi ero scordato di quell’uguale, devo modificare ancora qualcosina nel codice e ci sono. Comunque grazie mille per l’auito qui sul forum mi sono accorto che ci sono molte cose che devo ancora imparare. Anche se non posso piu partecipare alle olimpiadi in quanto quest’anno era l’ultimo anno a disposizione e sto ancora rosicando per il 6 posto di bologna nelle olimpiadi di informatica a squadre dove con 5 minuti in piu avremmo (probabilmente )fatto rescaling e saremmo stati primi a pari merito. Inoltre quest’anno non sono riuscito a fare le oii perche sono in stage all’estero