DreamTeam Selection (dreamteam)

Sto tentando di risolvere DreamTeam Selection (dreamteam): https://cms.di.unipi.it/#/task/ioit_dreamteam/statement ma ho fallisco solo gli ultimi due casi .:triumph:

Il codice è questo: https://pastebin.com/VzMNLh5Q

Il mio algoritmo è sviluppato in questo modo, innanzitutto ha complessità (NLogN) data dalla sort(), pooi si sviluppa in questo modo:
Io assegno ad ogni studente quello che secondo me è il suo valore effettivo che viene calcolato in questo modo:
-Se lo studente è migliore del suo migliore amico allora il suo valore effettivo è dato dalla bravura che ha nel lavorare
da solo.
-Se lo studente non è il più bravo allora il suo valore sarà: La sua bravura nel lavorare con il suo migliore amico meno
la differenza fra la bravura del suo migliore amico(sicuramente più bravo di lui) tra la sua capacità nel lavorare da solo e quella di lavorare in coppia.

Successivamente scelgo quelli con il valore effettivo più alto: Perche io l’ho ragionata cosi : essendo le amicizie simmetriche allora per una coppia di amici non ha mai nessun vantaggio scegliere il più debole prima del più forte, quindi scelgo sempre prima i più bravi poi se prendendo il più scarso è comunque piu conveniente di prendere tutti gli altri piu bravi allora viene scelto. Onestamente non capisco l’errore in quanto il mio ragionamento sembra corretto ed si adatta ad una politica greedy,

L’idea è giusta ma il codice ha qualche buco:

  • Quando scegli l’amico scarso, automaticamente li scegli entrambi (con il nuovo assegnamento di abilità), perciò nel ciclo finale avresti i+=2 e non i++.
  • Potrebbe capitare di scegliere l’amico scarso (cioè la coppia) quando arrivi a K-1 e quindi sforare il limite sulla squadra
  • Potrebbe anche capitare di scegliere l’amico scarso (cioè la coppia) e subito dopo scegliere l’amico forte

Ma in realtà nessuna delle 3 cose (se ho capito cosa intendi) non dovrebbe verificarsi

Non li scelgo mai in coppia sia quando gli assegno il punteggio che quando li scelgo lo faccio per un solo studente alla volta.

Vale la stessa cosa che ho detto prima, non li scelgo mai a coppie quindi la dimensione della squadra viene incrementata di 1 alla volta. [quote=“VashTheStampede, post:2, topic:4644”]
Potrebbe anche capitare di scegliere l’amico scarso (cioè la coppia) e subito dopo scegliere l’amico forte
[/quote]

Questo non può mai verificarsi, l’amico forte se verrà scelto, verrà sempre scelto prima di quello più debole per lo stesso ragionamento che hp spiegato qui.[quote=“frakkiobello, post:1, topic:4644”]
ssendo le amicizie simmetriche allora per una coppia di amici non ha mai nessun vantaggio scegliere il più debole prima del più forte, quindi scelgo sempre prima i più bravi poi se prendendo il più scarso è comunque piu conveniente di prendere tutti gli altri piu bravi allora viene scelto
[/quote]

E se non mi sono spiegato bene intendo dire che, io mi ordino gli studenti per un valore effettivo e questo valore effettivo sarà sempre maggiore per lo studente che lavora meglio da solo in quanto inizialmente quel valore è maggiore della capacitò del suo migliore amico, e successivamente il valore effettivo del migliore amico viene diminuito in quanto prima di tutto lavoro con il suo livello di bravura nel lavorare a coppia(che è sempre minore) e secondariamente a quel valore tolgo la differenza fra la bravura dell’amico piu bravo nel lavorare singolarmente e la bravura nel lavorare a coppia che sarà sempre una quantità positiva(B[i].valeff=A[i].due-(A[A[i].amico].solo-A[A[i].amico].due);). Quindi andando poi a scegliere i ragazzi con il valore effettivo maggiore è impossibile scegliere prima l’amico più scarso.

Svolgi le parentesi e ottieni:

B[i].valeff = A[i].due + A[A[i].amico].due − A[A[i].amico].solo

il significato di questa espressione è più o meno questo: l’amico scarso ora ha un’abilità che equivale a considerare la coppia di amici, meno l’abilità in singolo del suo migliore amico. Quel “meno” è un valore di correzione che andrebbe applicato quando inserisci in squadra questo amico scarso mentre è già presente l’amico forte, non so se mi sono spiegato.

Per questo ti dico che con questo “nuovo” valore effettivo dell’amico scarso è come aver già inserito in squadra l’amico forte :stuck_out_tongue:

Nope, perché tu ordini in base ai valori “effettivi”, significa che se l’amico forte, da solo, è meno forte di far lavorare insieme la coppia, allora verrà dopo all’amico debole (con il nuovo valore effettivo).
EDIT: e questo accade ogni volta che forte.P \leq \frac{forte.Q+debole.Q}{2}

Davvero non capisco cosa ci sia di sbagliato nel farlo. Lo so che con i calcoli che faccio nel valore del secondo amico è già come se avessi già inserIto il primo ma dal ragionamenti che ho fatto è così. Dimmi dove sbaglio con questo ragionamento:
-Nel caso in cui io ne debba scegliere uno di una coppia allora scelgo quello che lavora meglio da solo
-Se entrambi meritano di essere scelti allora lo applico direttamente al secondo in questo modo supponendo N=6 e K=4 e ho già scelto che i 3 migliori della loro coppia li ho scelti , allora non devo prendere quello più bravo fra i 3 rimasti nel lavorare in 2 ma quello che, considerando anche l’influenza sull’altro ragazze, è più conveniente.

Prova a farmi un esempio dove il più bravo a lavorare singolarmente fra i 2 verrà scelti dopo perché non ci arrivo. Cioè è possibile che il più bravo singolarmente sia più debole dell altro a lavorare in coppia ma con il mio algoritmo non dovrebbe dare problemi perché se ne prendè solo uno prende il più bravo singolarmente altrimenti li prede entrambi e non ci sono problemi

Scusa se non capisco ahahaha :smile:

Si in effetti hai ragione, quel caso non può accadere grazie a Q\leq{}P
Il problema comunque è sul ciclo di “riassegnamento”.

Prova questo input :slight_smile:

2 2
1 10 1
0 10 1
1 Mi Piace

Ma anche in questo caso credo che il risultato sia giusto, dato che devi scegliere esattamente K studenti al primo studente darò un valore effettivo di 10 mentre al secondo si -8 (1-9) e la somma sarà quindi 2 che è corretto .

Il tuo programma però non da 2 :stuck_out_tongue:

Ok ho risolto. In effetti non avevo pensato al caso in cui abbiano la stessa capacità

1 Mi Piace