Salve a tutti,
sull’esercizio nemico mortale ho scritto un sorgente che, una volta eseguito, riesce a risolvere
solo due casi. In particolare mi da anche un testcase errato che, seppur diverso da quello dato dal problema, dovrebbe essere giusto
codice`
https://pastebin.com/ZRE9Mm1g
Esercizio:
https://cms.di.unipi.it/#/task/nemesi/statement
Vi ringrazio anticipatamente
Onestamente non so se tu stia cercando di implementare il classico algoritmo di graph colouring o qualcos’altro. Non capisco il senso del tuo sorgente, a dire il vero (forse perché avendo risolto il problema ho in mente solo la soluzione esatta? in tal caso chiedo venia).
Ti do qualche suggerimento per risolvere l’algoritmo in via lineare: puoi provare che, sotto opportune condizioni come quelle di questo problema il problema non è più NP-arduo? Puoi provare che il numero di gruppi massimo e minimo ha un limite dovuto a tale impostazione?
Quello che fa il codice è passare elemento per elemento (for) e verificare se è possibile aggiungerlo all’ultimo gruppo se il suo nemico mortale non è gia nel gruppo e se lui non è il nemico mortale di nessun altro (uso un array di bool di dimensione N).
Ogni volta che finisco il for creo un nuovo gruppo e vado avanti fino a quando non ho terminato di inserire le persone nei gruppi.
La complessità dovrebbe essere bassa e permettere di risolvere ogni task solo che vorrei capire, partendo da questa soluzione, gli errori che ho commesso.
In particolare se provi ad eseguirlo mi da uno dei due subtask di test sbagliato, nonostante sia corretto.
Per esempio sul secondo esempio il mio programma restituisce il 3 ed il 4 invertiti ma è comunque giusto o sbaglio?
grazie
Non ho specificato che non sono errati ma semi corretti
Scegliere in questo modo non garantisce che la tua soluzione preveda il minor numero possibile di gruppi, prova ad esempio con questo input 
6
2 5 3 1 0 4
La complessità non è ottimale. E l’algoritmo non è corretto: come garantisci che il numero di gruppi creato con il tuo metodo è minimo?
Parti con un approccio inverso che ti ho indicato nel testo sfocato.
grazie ad entrambi, ora provo un altra soluzione
filippos, sai indicarmi l’output corretto al tuo input?
0 5 3
4 1 2
Ricordati l’osservazione di prima.
sisi grazie mille,
ho trovato una soluzione usando i grafi