infoarena informatica de performanta

Dusman

Desi la o prima vedere limitele ar putea parea prea mari, problema se rezolva folosind tehnica backtracking. Pur si simplu se genereaza in ordine lexicografica primele K permutari indeplinind conditiile din enunt.

Urmatorul cod reprezinta o implementare simplista si intuitiva a problemei:

void dusman ( int l ) {
    if ( K < 0 ) {
       return ;
    }

    if ( l > N ) {
       if ( --K == 0 ) afis () ;
       return ;
    }

    for ( int i = 1; i <= N; ++i ) {
       if ( X[i] == 0 && A[ sol[l - 1] ][ i ] == 0 ) { // A[x][y] == 1 daca intre x si y exista o relatie de dusmanie
          sol[ l ] = i; 
          X[ i ] = true;
          dusman (l + 1) ;
          X[ i ] = false;
       }
}

Algoritmul merge repede si furnizeaza solutie repede datorita restrictiei ca fiecare vecin are cel mult 3 dusmani.

Ca o optimizare la acest algoritm ca de altfel la majoritatea problemelor care implica generarea permtarilor se pot folosi dancing links, dar acest lucru nu era necesar pentru obtinerea punctajului maxim.