Ordinamento del pane#6828

Ordinamento del pane (Editoriale)

Il trucco con la paletta esegue la seguente permutazione dei pani:

(a & b & c c & a & b)

\begin{pmatrix} a \& b \& c \\ c \& a \& b \end{pmatrix}

Può essere rappresentata come due permutazioni di elementi adiacenti:

(a, b, c) \to (a, c, b) \to (c, a, b)

(a, b, c) → (a, c, b) → (c, a, b)

Ogni permutazione di elementi adiacenti cambia la parità della permutazione. Di conseguenza, l'operazione indicata sui pani conserva la parità della permutazione.

Ordinare il pane come richiesto dal capo di Michael è possibile solo se le parità delle permutazioni coincidono.

La soluzione lineare del problema si basa sul fatto che due permutazioni hanno la stessa parità se e solo se la parità del numero di cicli in cui si decompongono coincide.

Lemma. Consideriamo il seguente fatto della teoria delle permutazioni:

p a r i t a ˋ d e l l a p er m u t a z i o n e = (n - n u m er o d i c i c l i) m o d 2

parità~della~permutazione = (n - numero~di~cicli)~mod~2

Pertanto, per verificare la parità si può:

decomporre la permutazione in cicli;
contarne il numero.

Se due permutazioni hanno la stessa parità del numero di cicli, allora le loro parità coincidono.

Intuitivamente, ciò deriva dal fatto che ogni ciclo di lunghezza $k$ può essere composto da $k - 1$ k - 1 scambi di elementi, quindi il numero totale di scambi è pari a

n - n u m er o d i c i c l i

n - numero~di~cicli

Esempio

Nel primo esempio la prima permutazione contiene $2$ inversioni, la seconda — $6$ inversioni. Il numero di inversioni in entrambe le permutazioni ha la stessa parità.

Decomponiamo le permutazioni in cicli:

$(1, 3, 4, 2) = (1) (3, 4, 2)$ (1, 3, 4, 2) = (1) (3, 4, 2);
$(4, 3, 2, 1) = (4, 1) (3, 2)$ (4, 3, 2, 1) = (4, 1) (3, 2);

Entrambe le permutazioni sono costituite da due cicli, cioè anche il numero di cicli in esse ha la stessa parità.

Nel secondo esempio la prima permutazione contiene $0$ inversioni, mentre la seconda — $15$ inversioni. Il numero di inversioni in queste permutazioni ha parità diversa.

Decomponiamo le permutazioni in cicli:

$(1, 2, 3, 4, 5, 6) = (1) (2) (3) (4) (5) (6)$ (1, 2, 3, 4, 5, 6) = (1) (2) (3) (4) (5) (6);
$(6, 5, 4, 3, 2, 1) = (6, 1) (5, 2) (4, 3)$ (6, 5, 4, 3, 2, 1) = (6, 1) (5, 2) (4, 3);

La prima permutazione è costituita da $6$ cicli, mentre la seconda — da $3$ cicli. Pertanto, la parità del numero di cicli in queste permutazioni è diversa.

Implementazione dell'algoritmo

Dichiariamo un array per memorizzare la permutazione.

#define MAX 100010
int a[MAX];

La funzione run percorre un ciclo della permutazione, iniziando dall'indice $p os$ . Ad ogni passo, passa all'elemento successivo del ciclo secondo la regola $p os \to a [p os]$ pos \to a[pos]. Gli elementi visitati vengono contrassegnati con il valore $- 1$ , per non elaborarli nuovamente. In questo modo, la funzione percorre completamente un ciclo della permutazione e contrassegna tutti i suoi elementi come già visitati.

void run(int pos)
{
  int v;
  while (a[pos] != -1)
  {
    v = a[pos];
    a[pos] = -1;
    pos = v;
  }
}

C++

La funzione parity calcola la parità del numero di cicli nella permutazione $a$ , cioè restituisce il numero di cicli modulo $2$ . La funzione esamina in sequenza tutte le posizioni dell'array.

int parity(int *a)
{
  int res = 0;

Esaminiamo in sequenza tutte le posizioni dell'array.

  for (int i = 0; i < n; i++)

Se l'elemento non è ancora stato visitato $(a [i] \neq = - 1)$ (a[i] \ne -1), ciò significa l'inizio di un nuovo ciclo. In questo caso viene chiamata la funzione $r u n (i)$ , che percorre l'intero ciclo e contrassegna i suoi elementi con il valore $- 1$ .

    if (a[i] != -1) 
    {
      run(i);

Dopo aver percorso il ciclo, il contatore $r es$ viene incrementato di $1$ .

      res++;
    }

Restituiamo la parità del numero di cicli.

  return res % 2;
}

Parte principale del programma. Leggiamo la prima permutazione. Durante la lettura, ogni valore viene decrementato di $1 (a [i] - -)$ 1~(a[i]--), per passare dalla numerazione degli elementi da $1.. n$ a quella più comoda per il lavoro $0.. n - 1$ 0 .. n - 1.

scanf("%d",&n);
for (i = 0; i < n; i++)
  scanf("%d",&a[i]), a[i]--;

Nella variabile $p 1$ calcoliamo la parità del numero di cicli nella permutazione $a$ .

p1 = parity(a);

Leggiamo la seconda permutazione. Nella variabile $p 2$ calcoliamo la parità del numero di cicli nella permutazione $a$ .

for (i = 0; i < n; i++)
  scanf("%d",&a[i]), a[i]--;
p2 = parity(a);

Confrontiamo le parità del numero di cicli nelle due permutazioni e stampiamo la risposta.

if (p1 == p2) printf("Possible\n");
else printf("Impossible\n");