Stavo provando a risolvere sieve con una tecnica che definirei brute force 
Mantengo tutti i multipli e sottomulitpli di ogni numero e iterativamente cancello quello che ne possiede di più.
Mi da solo 35 punti, stavo pensando a qualcosa con i grafi ma non mi viene in mente niente, consigli?
Se la risoluzione del problema consistesse in un grafo, quale sarebbe il criterio con cui i nodi sono collegati tra loro? (ti potro’ aiutare solo fino a 50/100 perche’ non sono riuscito a fare l’ultimo step di ottimizzazione)
Ciao, il problema può essere espresso come un grafo i cui i nodi sono gli interi da 0 a N-1 e gli archi le coppie (i, j) tali che V_i | V_j o V_j | V_i. Ti viene chiesto quanti nodi al minimo devi colorare se vuoi che ogni nodo sia colorato o abbia un vicino colorato.
Puoi esplorare ricorsivamente l’albero delle soluzioni possibili, tagliando un ramo quando la risposta corrente è \geq della migliore trovata o poco prima di raggiungere il Time Limit.
Per trovare la risposta in tempo è necessario lamerare applicare alcune ottimizzazioni, ad esempio provare ogni volta a prendere o non prendere il nodo con più vicini o rappresentare il grafo in un modo conveniente. Puoi anche calcolare la risposta separatamente per ogni componente connessa.
Un arco rappresenterebbe un legame di moltemplicità o divisibilità tra due nodi, nella mia idea.
Non ho capito qual è l’approcio che devo usare per capire quali nodi colorare e quali no, questa tecninca ha un nome, così me la studio senza continuare a fare domande.
Questo problema si puo risolvere con una tecnica chiamata branch&bound, che e’ una tecnica molto generale che in pratica consiste in fare una brute force ma cercando di tagliare lo spazio di ricerca il piu possibile (eg se la soluzione ottima che hai trovato fino a un certo punto e’ k, in un certo branch sai con qualche euristica che non potrai avere soluzioni migliori di k, allora puoi evitare di continuare la brute force su quel branch).
Nota che comunque e’ una soluzione esponenziale, quindi se non fai branching, bounding e ordine di esplorazione bene adatti al problema puoi facilmente andare fuori tempo prima di essere sicuro della soluzione. (ma comunque se killi il programma entro il limite di tempo, probabilmente hai comunque trovato gia la soluzione ottima se usi un ordine di esplorazione sensato)