Ciao a tutti, come da titolo sto tentando di risolvere il problema projectgroup delle ois ma fino ad ora ho ottenuto uno score di 90.91/100 punti. Il mio algoritmo cerca per prima cosa tutti i possibili gruppi e poi man mano rimuove quelli infattibili, ovvero quelli in cui uno studente sia presente anche in altri gruppi. Per fare questo inizio rimuovendo il gruppo che genera più “conflitti”, ovvero quello per il quale sommando il numero di volte che appare lo stesso studente (in altri gruppi) si ottiene il valore maggiore; il tutto fino a quando ogni studente non appare al massimo una sola volta. Non so se il mio ragionamento sia corretto o meno, a questo punto credo di sbagliare su qualche particolare… Il codice è il seguente: https://pastebin.com/xFh0XnuM
In realta’ il tuo algoritmo e’ di tipo greedy (come il mio, infatti ottengo 94.92). La soluzione da 100/100 mi pare di aver capito che non sia greedy.
Ho appena controllato i tag e ho visto che c’è proprio il tag greedy, quindi può darsi che stiamo sbagliando noi qualcosa 
Comunque all’inizio avevo provato a farlo in dp ma come mi aspettavo ottengo TLE nell’ultimo subtask totalizzando solo 70 punti (la complessità è abbastanza elevata in quanto non ho la possibilità di memoizzare perchè altrimenti sforerei con la memoria).
Il problema è che i testcase che non risolvo con la strategia greedy sono proprio tra quelli che danno TLE con l’algoritmo dp, quindi non so neanche se quell’algoritmo sia giusto al 100% 
Il tag greedy l ho messo io e ho ottenuto 100/100.
Hai considerato il caso in cui ci sono più gruppi che generano lo stesso numero di conflitti ?
Si, avevo pensato che in quel caso fosse indifferente rimuovere uno o l’altro. Dici che l’errore sia questo?
Yep, rimuovendo uno qualsiasi tra quelli con più conflitti ho ottenuto 93.02 / 100.
ps: se qualcuno riesce a risolverlo in dp e vorrebbe spiegarmelo mi farebbe piacere XD
Potresti darmi un suggerimento su come scegliere il gruppo da rimuovere tra quelli che generano lo stesso numero di conflitti?
Comunque per quanto riguarda la dp io avevo pensato una cosa del genere: per ogni gruppo ho 2 possibilità: considerarlo nella soluzione finale o meno, per cui richiamo la funzione che io ho nominato “search” con parametro 0 (indice del primo gruppo), quindi la funzione richiama sé stessa con i+1 per due volte, prima non inserendo l’i-esimo gruppo nella soluzione, dopo di che inserendolo, infine si restituisce la soluzione che contiene più gruppi (spero di essermi spiegato). Il problema è che senza memoizzare la complessità è esponenziale (credo) e non trovo un modo efficiente per farlo.
Mi è difficile darti un suggerimento visto che io conto il numero di conflitti in base a quanti gruppi non posso formare scegliendo di creare un determinato gruppo.
Non so se è equivalente 
Nel mio caso eliminavo il gruppo in cui le alterantive mi facevano fare più gruppi possibili.
Io il numero di conflitti li conto così: se abbiamo ad esempio i gruppi
A={0, 1, 2}, B={0, 1, 3}, C={3, 4, 5}, D={6, 7, 8}
il gruppo A genera 5 conflitti perchè faccio “volte in cui appare lo 0” (2) + volte in cui appare 1 (2) + volte in cui appare il 2 (1) = 5. In realtà i conflitti sono solo 2 perchè al risultato finale bisognerebbe fare -3 (in quanto usando la formula vista prima contiamo anche le occorrenze nel gruppo stesso).
il gruppo B ne genera quindi 6 (3 effettivi), C ne genera 4 (1 effettivo) e D 3 (0 effettivi).
Io il numero di conflitti li conto così: se abbiamo ad esempio i gruppi
A={0, 1, 2}, B={0, 1, 3}, C={3, 4, 5}, D={6, 7, 8}
il gruppo A genera 5 conflitti perchè faccio “volte in cui appare lo 0” (2) + volte in cui appare 1 (2) + volte in cui appare il 2 (1) = 5. In realtà i conflitti sono solo 2 perchè al risultato finale bisognerebbe fare -3 (in quanto usando la formula vista prima contiamo anche le occorrenze nel gruppo stesso).
il gruppo B ne genera quindi 6 (3 effettivi), C ne genera 4 (1 effettivo) e D 3 (0 effettivi).
Non mi è chiaro perché A abbia 2 conflitti e B 3.
Mi verrebbe da pensare che A sia in conflitto solo con B e che B sia in conflitto solo con A e con C.
Comunque anch’io devo trovare un buon modo per decidere che gruppo scartare quando i gruppi ad avere il massimo numero di conflitti sono più di uno.
Secondo il mio algoritmo A ha 2 conflitti perchè 2 dei suoi elementi sono presenti in altri gruppi (in questo caso 0 e 1 sono presenti in B), allo stesso modo B ha 3 conflitti perchè 0 e 1 sono contenuti in A e 3 in C.