Удаан, хурдан хоёр заагчаар дарааллын cycle-ыг нэмэлт санах ойгүйгээр олдог Floyd-ын арга.

IntermediateХугацаа: O(mu + lam)Санах ой: O(1)
HackerRank дээр бодох

Эхлээд жижиг бодлого

f = [1, 2, 3, 4, 5, 6, 3] бол 0-ээс эхлээд x = f[x] гэж үсэрье: 0 → 1 → 2 → 3 → 4 → 5 → 6 → 3 → 4 → …

3 алхмын дараа 3-т ирээд, тэндээс 3 → 4 → 5 → 6 → 3 гэж эргэлдэнэ. Тэгэхээр mu = 3, cycle-ын урт lam = 4. Хариу: 3 4.

Энгийн аргаас санаа руу

Энгийн арга: очсон node бүрээ visited array-д бичнэ. Анх удаа давтагдсан node бол cycle-ын эхлэл. Энэ O(n) санах ой шаардана. Тоонууд 10¹⁸ хүртэл байвал, жишээ нь x = (x² + 1) mod m, ийм array багтахгүй.

Floyd-ын санаа: хоёр заагч явуулна. 🐢 t нэг, 🐇 h хоёр алхмаар явна. Хоёулаа cycle-д орсны дараа тэдний хоорондох зай алхам бүрт нэгээр багасна. Тиймээс заавал уулзана. Дараа нь бас хоёр энгийн шат хийгээд mu, lam-ыг олно. Хэдхэн хувьсагч л хэрэгтэй.

Нэр томьёо ба тэмдэглэгээ

f[x]
x-ээс дараа нь очих node. Node бүрээс яг нэг сум гарна.
t, h
🐢 удаан (tortoise), 🐇 хурдан (hare) заагч.
mu
0-ээс cycle-ын эхлэл хүртэлх алхмын тоо, өөрөөр хэлбэл tail-ын урт.
lam
Cycle-ын урт: cycle-ын нэг node-оос гараад буцаж ирэх алхмын тоо.
0123456

x = 0-ээс эхлээд x = f[x] гэж үсэрсээр байвал хэзээ нэгэн цагт cycle-д орно. Cycle хаанаас эхэлж, хэр урт вэ? 🐢 нэг, 🐇 хоёр алхмаар уралдана.

Алхам 1 / 14
Хурд
  • 🐢 t
  • 🐇 h
  • Уулзсан газар / cycle-ын эхлэл
  • Cycle
  • 0-ээс хүрэхгүй node
Слайд 1 / 6

Үсрэх тоглоом

0-ээс эхлээд x = f[x] гэж үсэрнэ: 0, 1, 2, 3, 4, 5, 6, 3, 4, … Хэзээ нэгэн цагт cycle-д орно. Cycle хаанаас эхэлж, хэр урт вэ?

tortoise-hare.cpp
#include <bits/stdc++.h>
using namespace std;
int n, f[100005];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> f[i];
int t = f[0], h = f[f[0]];
while (t != h) {
t = f[t], h = f[f[h]];
}
t = 0;
int mu = 0;
while (t != h) {
t = f[t], h = f[h], mu++;
}
int lam = 1;
h = f[t];
while (h != t) {
h = f[h], lam++;
}
cout << mu << ' ' << lam << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

x = f(x) гэж давтахад cycle хаанаас эхэлж, хэр урт болохыг олно. Linked list дахь cycle, давтагдах тоо олох бодлогод хэрэглэнэ.

Яаж ажилладаг вэ?

1. 🐢 t нэг, 🐇 h хоёр алхмаар явна. Cycle-д орсны дараа h заавал t-г гүйцэж уулзана. 2. t = 0 болгож эхлэл рүү буцаана. Хоёулаа нэг нэг алхана. Тэдний уулзах газар нь cycle-ын эхлэл, алхмын тоо нь mu. 3. t зогсоно. h cycle-ыг нэг нэг алхмаар тойрч, буцаж иртэл тоолно. Энэ бол cycle-ын урт lam. Нэмэлт array огт хэрэглэхгүй. Оролт: n, дараа нь f[0] … f[n − 1]. 0-ээс эхэлнэ. Гаралт: mu ба lam.

Яагаад зөв, хэр хурдан бэ?

Уулзах үед хурдан заагч удаанаасаа яг хоёр дахин их алхсан байна. Илүү алхсан алхмуудын тоо нь lam-ын үржвэр. Үүнээс гарах дүгнэлт: 0-ээс ба уулзсан газраас зэрэг нэг нэг алхвал яг mu алхмын дараа cycle-ын эхэнд зэрэг ирнэ. Тэгээд эхлэлээс h-г нэг тойруулж lam-ыг тоолно.

Гурван шат тус бүр O(mu + lam) алхам, нэмэлт санах ой O(1). Сая node-той бол хэдэн сая л алхам.

Түгээмэл алдаа

  • Эхлэлийг буруу тавих: t = f[0], h = f[f[0]] гэж эхлүүлэх ёстой. Хоёуланг нь 0 дээр эхлүүлбэл while (t != h) шууд дуусна.
  • Хоёр дахь шатанд h-г ч бас 0 болгох. Зөвхөн t буцна, h уулзсан газраа үлдэнэ.
  • lam-ыг 0-ээс эхлүүлэх. Код lam = 1, h = f[t] гэж эхэлдэг. Үгүй бол хариу нэгээр дутуу гарна.
  • f[x] нь 0-ээс n − 1 хүртэл байгаа эсэхийг шалгахгүй орхих. Хэтэрвэл array-гээс гарна.

Хязгаарын тохиолдол

  • 0 өөрөө cycle дотор, жишээ нь f = [1, 2, 0]: mu = 0, lam = 3.
  • Өөр рүүгээ заасан node, жишээ нь f = [1, 1]: 0 → 1 → 1 → …, mu = 1, lam = 1.
  • Урт tail, богино cycle: f = [1, 2, 3, 4, 4] бол mu = 4, lam = 1.
  • 0-ээс хүрэхгүй node-ууд хариунд нөлөөлөхгүй. Заагчид тэнд хэзээ ч очихгүй.

Өөрийгөө шалга

  1. f = [2, 0, 3, 3] бол mu, lam хэд вэ?

    Хариу харах

    2 1. 0 → 2 → 3 → 3 → …

  2. Уулзсны дараа яагаад t-г 0 рүү буцаадаг вэ?

    Хариу харах

    0-ээс ба уулзсан газраас зэрэг нэг нэг алхвал яг cycle-ын эхэнд уулздаг. Ингэж mu-г олно.

  3. f = [1, 2, 0] бол mu хэд вэ?

    Хариу харах

    0. 0 өөрөө cycle дотор байна.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.f = [1, 2, 3, 4, 2] дээр mu, lam-ыг ол.

    Hint харах

    0-ээс эхлээд дарааллыг бич: 0, 1, 2, …

    Хариу ба тайлбар

    0 → 1 → 2 → 3 → 4 → 2 → … mu = 2, lam = 3. Хариу: 2 3.

  2. 2.n + 1 урттай array-д 1-ээс n хүртэлх тоо байна, нэг тоо давтагдана. Floyd-ын аргаар давтагдсан тоог ол.

    Hint харах

    i → a[i] гэж үсэрвэл давтагдсан тоо руу хоёр сум ирнэ.

    Хариу ба тайлбар

    f[x] = a[x] гэж үзээд 0-ээс эхэлнэ. Давтагдсан тоо руу хоёр өөр index-ээс сум ирдэг тул тэр нь cycle-ын эхлэл. Кодын хоёр дахь шатны дараах t бол хариу.

  3. 3.x = (x · x + 1) mod m дарааллын cycle-ын уртыг ол. m нь 10¹² хүртэл.

    Hint харах

    f[x]-ийн оронд function бичээд, array огт хэрэглэхгүй.

    Хариу ба тайлбар

    Array-н оронд long long f(long long x) { return ((__int128)x * x + 1) % m; } гэж бичнэ. Кодын f[t] бүрийг f(t) болгоход хангалттай. Санах ой O(1) хэвээр.

Жишээ

Оролт

7
1 2 3 4 5 6 3

Гаралт

3 4

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.