Möhtəşəm hiylə#11320

Möhtəşəm hiylə (Həll təhlili)

Qarışdırmadan sonra soldan $i$ -ci kart $a [p [q [i]]]$ a[p[q[i]]] kartı olur. Trik uğurlu olur, əgər bütün $i$ üçün aşağıdakı bərabərlik ödənirsə:

a [p [q [i]]] = i .

a[p[q[i]]] = i.

Permutasiyaların kompozisiyasını $p \circ q$ p \circ q ilə işarə edək: $(p \circ q) [i] = p [q [i]]$ (p \circ q)[i] = p[q[i]], yəni əvvəlcə $q$ , sonra isə $p$ tətbiq olunur. $I$ ilə tərs permutasiyanı işarə edək. Onda trikin şərti belə yazıla bilər: $a \circ p \circ q = I$ a \circ p \circ q = I.

Bərabərliyin hər iki tərəfinə soldan əvvəlcə tərs permutasiya $a^{- 1}$ a^{-1}-i, sonra isə $p^{- 1}$ p^{-1}-i tətbiq edək:

p \circ q = a^{- 1}, q = p^{- 1} \circ a^{- 1} .

p \circ q = a^{-1}, \qquad q = p^{-1} \circ a^{-1}.

Beləliklə, $p$ permutasiyası ixtiyari seçilə bilər, sonra isə $q$ birmənalı şəkildə müəyyən olunur: $q [i] = p^{- 1} [a^{- 1} [i]]$ q[i] = p^{-1}[a^{-1}[i]]. Sabit nöqtəsi olmayan permutasiyaya deranjman deyilir. Məsələ elə bir $p$ deranjmanının tapılmasına gətirilir ki, $q = p^{- 1} \circ a^{- 1}$ q = p^{-1} \circ a^{-1} permutasiyası da deranjman olsun.

Təsadüfi seçim. Bütün $n!$ permutasiyanı $p$ üçün yoxlamaq mümkün deyil, ona görə $p$ -ni təsadüfi seçirik:

təsadüfi permutasiya $p$ generasiya edirik; əgər onun sabit nöqtəsi varsa, növbəti cəhdə keçirik;
$q = p^{- 1} \circ a^{- 1}$ q = p^{-1} \circ a^{-1} hesablayırıq;
əgər $q$ -nun sabit nöqtəsi yoxdursa, $(p, q)$ cütü cavabdır.

Ən çoxu $1000$ cəhd edirik. Əgər onlardan heç biri cavab vermirsə, "Impossible" çap edirik.

Niyə işləyir. Cavab yalnız kiçik $n$ üçün bəzi hallarda mövcud deyil:

$n = 1$ n = 1 — sabit nöqtəsi olmayan permutasiya ümumiyyətlə yoxdur;
$n = 2$ n = 2 və $a = (2, 1)$ a = (2, 1) — yeganə deranjman $p = (2, 1)$ p = (2, 1) $q = (1, 2)$ q = (1, 2) verir;
$n = 3$ n = 3 və $a$ tam olaraq iki elementi dəyişir. Uzunluğu $3$ olan yeganə deranjmanlar dairəvi sürüşmələrdir: $(2, 3, 1)$ (2, 3, 1) və $(3, 1, 2)$ (3, 1, 2). İki dairəvi sürüşmənin kompozisiyası yenə dairəvi sürüşmə və ya tərs permutasiya olur, ona görə iki elementi dəyişən permutasiya əldə edilə bilməz.

$n \geq 4$ n \ge 4 üçün cavab həmişə mövcuddur. Üstəlik, kiçik $n$ üçün tam axtarış göstərir ki, bütün $n!$ permutasiya arasında uyğun $p$ permutasiyalarının payı ən azı $1/12$ -dir (minimum $n = 4$ n = 4-də əldə olunur), və $n$ artdıqca bu pay $1/ e^{2} \approx 0.135$ 1/e^2 \approx 0.135-ə yaxınlaşır. Deməli, $1000$ cəhddə cavab tapılmaması ehtimalı $(11/12)^{1000} < 1 0^{- 37}$ (11/12)^{1000} < 10^{-37}-dan çox deyil, bu isə praktiki olaraq sıfırdır. Əgər cavab mövcud deyilsə, heç bir cəhd uğurlu olmayacaq və proqram düzgün olaraq "Impossible" çap edəcək.

Nümunə

Dördüncü testə baxaq: $a = (5, 1, 4, 2, 3)$ a = (5, 1, 4, 2, 3).

Tərs permutasiyanı tapaq: əgər $a [i] = x$ a[i] = x olarsa, onda $a^{- 1} [x] = i$ a^{-1}[x] = i. $a [1] = 5$ a[1] = 5, $a [2] = 1$ a[2] = 1, $a [3] = 4$ a[3] = 4, $a [4] = 2$ a[4] = 2, $a [5] = 3$ a[5] = 3 olduğundan, $a^{- 1} = (2, 4, 5, 3, 1)$ a^{-1} = (2, 4, 5, 3, 1) alırıq. Şəkildə solda $a$ permutasiyası, sağda isə onun tərsi göstərilib: bütün oxlar tərsinə çevrilib.

Sabit nöqtəsi olmayan təsadüfi $p$ permutasiyası generasiya edək. Tutaq ki, $p = (4, 1, 2, 5, 3)$ p = (4, 1, 2, 5, 3). Onun tərsi $p^{- 1} = (2, 3, 5, 1, 4)$ p^{-1} = (2, 3, 5, 1, 4)-dir.

$q [i] = p^{- 1} [a^{- 1} [i]]$ q[i] = p^{-1}[a^{-1}[i]] hesablayaq:

q [1] = p^{- 1} [2] = 3, q [2] = p^{- 1} [4] = 1, q [3] = p^{- 1} [5] = 4, q [4] = p^{- 1} [3] = 5, q [5] = p^{- 1} [1] = 2

q[1] = p^{-1}[2] = 3, \quad q[2] = p^{-1}[4] = 1, \quad q[3] = p^{-1}[5] = 4, \\ q[4] = p^{-1}[3] = 5, \quad q[5] = p^{-1}[1] = 2

$q = (3, 1, 4, 5, 2)$ q = (3, 1, 4, 5, 2) alırıq. $q$ permutasiyasının sabit nöqtəsi yoxdur, ona görə $(p, q)$ cütü cavabdır. Bu, nümunədəki cavabla üst-üstə düşür.

Trikin uğurlu olduğunu yoxlayaq, yəni $a [p [q [i]]] = i$ a[p[q[i]]] = i:

a [p [3]] = a [2] = 1, a [p [1]] = a [4] = 2, a [p [4]] = a [5] = 3, a [p [5]] = a [3] = 4, a [p [2]] = a [1] = 5

a[p[3]] = a[2] = 1, \quad a[p[1]] = a[4] = 2, \quad a[p[4]] = a[5] = 3, \\ a[p[5]] = a[3] = 4, \quad a[p[2]] = a[1] = 5

Birinci testdə $n = 2$ n = 2 və $a = (2, 1)$ a = (2, 1), ona görə $a^{- 1} = (2, 1)$ a^{-1} = (2, 1). Uzunluğu $2$ olan sabit nöqtəsiz yeganə permutasiya $p = (2, 1)$ p = (2, 1)-dir, və $p^{- 1} = (2, 1)$ p^{-1} = (2, 1). Onda $q = p^{- 1} \circ a^{- 1} = (1, 2)$ q = p^{-1} \circ a^{-1} = (1, 2) tərs permutasiyadır, onun bütün nöqtələri sabitdir. Cavab "Impossible"-dır.

Alqoritmin realizasiyası

print funksiyası $a$ massivinin elementlərini birincidən başlayaraq çap edir.

void print(vector<int>& a)
{
  for (int i = 1; i < a.size(); i++)
    printf("%d ", a[i]);
  printf("\n");
}

is_valid funksiyası $v$ permutasiyasının sabit nöqtəsi olub-olmadığını yoxlayır.

bool is_valid(vector<int>& v)
{
  for (int i = 1; i < v.size(); i++)
    if (v[i] == i) return false;
  return true;
}

Massivləri elan edirik.

vector<int> a, p, p1, q;

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d", &tests);
while (tests--)
{
  scanf("%d", &n);

Massivləri ilkinləşdiririk.

  a.resize(n + 1);
  p1.resize(n + 1);
  p.resize(n + 1);
  q.resize(n + 1);

Giriş $a$ permutasiyasını oxuyuruq və dərhal onun tərsini $a$ massivində saxlayırıq. Yəni $a$ massivi $a^{- 1}$ a^{-1} permutasiyasını saxlayır, burada $a$ giriş permutasiyasıdır.

  for (i = 1; i <= n; i++)
  {
    scanf("%d", &x);
    a[x] = i;
  }

mt19937 C++-da standart psevdo-təsadüfi ədəd generatorlarından biridir (period uzunluğu $19937$ olan Mersenne Twister). O, çox sürətlidir və yaxşı statistik xüsusiyyətlərə malikdir, bu da onu təsadüfi ədəd generasiyası tələb edən əksər tapşırıqlar üçün əla seçim edir.

  mt19937 gen(random_device{}());

$f o u n d$ dəyişənində cari test üçün həllin tapılıb-tapılmadığını qeyd edəcəyik.

  found = false;

$1000$ təkrar yerinə yetiririk.

  for (it = 0; it < 1000; it++)
  {

Təsadüfi permutasiya generasiya edirik. Bunun üçün $p$ massivini $0, 1, 2, ...$ 0, 1, 2, ... ədədləri ilə doldururuq, sonra shuffle funksiyasından istifadə edərək birinci (sıfır olmayan) elementdən başlayaraq elementləri qarışdırırıq. Biz $1$ -dən $n$ -ə qədər olan permutasiyalarla işləyirik.

    iota(p.begin(), p.end(), 0);
    shuffle(p.begin() + 1, p.end(), gen);

$p$ permutasiyasının düzgün olub-olmadığını (yəni sabit nöqtəsinin olmadığını) yoxlayırıq.

    if (!is_valid(p)) continue;

$p_{1} = p^{- 1}$ p_1 = p^{-1} permutasiyasını hesablayırıq.

    for (i = 1; i <= n; i++)
      p1[p[i]] = i;

$q = p_{1} ° a^{- 1} = p^{- 1} ° a^{- 1}$ q = p_1 ° a^{-1} = p^{-1} ° a^{-1} permutasiyasını hesablayırıq.

    for (i = 1; i <= n; i++)
      q[i] = p1[a[i]];

Əgər $q$ permutasiyası düzgündürsə, nəticəni çap edirik.

    if (is_valid(q))
    {
      puts("Possible");
      print(p);
      print(q);
      found = true;
      break;
    }
  }

C++

Əgər $1000$ təkrardan sonra həll tapılmazsa, deməli həll mövcud deyil.

  if (!found) puts("Impossible");
}