Miglior algoritmo per "ACM ICPC Team"

Question

Miglior algoritmo per "ACM ICPC Team"

#1 da (2 voti)

0

Ho questo problema (descrizione completa) :
C'è un elenco di argomenti N e M .
Devo scoprire il numero massimo di argomenti che una squadra di 2 persone può conoscere. E scopri anche quanti team possono conoscere il numero massimo di argomenti.

2 < = N < = 500
1 < = M < = 500

Ex.
Le righe sono persone, le colonne sono argomenti.
Se c'è 1 la persona conosce quell'argomento, 0 altrimenti.

Il risultato è 5,2

Il mio algoritmo è un'implementazione bruteforce, penso che la complessità sia O (n ^ 3)

vector<bitset<501>> v;
int nMax = 0;
int nMaxCounter = 0;
for(int i=0; i<N; i++) {
    for(int j=i+1; j<N; j++){
        bitset<501> t = v[i] | v[j];
        if(t.count() > nMax) {//t.count() -> returns the number of bits set to true
            nMax = t.count();
            nMaxCounter = 1;
        } else {
            if(t.count() == nMax)
                nMaxCounter++;
        }
    }
}

cout<<nMax<<endl;
cout<<nMaxCounter<<endl;

Prima domanda: La complessità è O (n ^ 3)?

Seconda domanda Sei in grado di trovare un algoritmo migliore?

c++ algorithms c++11

posta user72708 10.03.2015 - 19:57

fonte

1 risposta

Leggi altre domande sui tag c++ algorithms c++11

Windows Firewall singola regola con più indirizzi IP rispetto a più regole con un singolo indirizzo IP [chiuso] Imposta sempre la lunghezza massima dell'inserimento del modulo?

score 2 · Accepted Answer

1) Supponiamo che t.count () sia un'operazione di tempo lineare rispetto alla dimensione del bitset (probabilmente non è sull'hardware reale, ma lo ignora). Quindi sarebbe corretto dire che l'algoritmo è O(M*N^2) , per l'ovvia ragione che si ha un ciclo di iterazione M (t.count ()) all'interno di un ciclo di ripetizione N all'interno di un ciclo di ripetizione N. Questo potrebbe essere equivalente a O(n^3) se scegli una definizione un po 'imbarazzante di n , ma dal momento che la dimensione del problema è già definita in termini di due variabili diverse, non c'è molto da fare per cercare di eliminarle in una sola.

2) In generale, è possibile battere la soluzione della forza bruta su un algoritmo solo se il controllo di una o più soluzioni consente di "escludere" altre soluzioni non ancora verificate. Ad esempio, la ricerca binaria supera la ricerca lineare perché dopo aver controllato l'elemento intermedio, puoi escludere la metà dell'elenco senza controllare tutti gli elementi singolarmente. Con questo problema, a meno che il tuo input sia in qualche modo "pre-ordinato", non vedo alcun modo di aggirare la necessità di controllare ogni singola coppia, quindi no non riesco a trovare un algoritmo migliore (in termini di classe di complessità temporale ).