Ildiz evristikalari - Course 4

Modul 1: Trie

Trie

Modul 2: Sparse Table

Sparse table

Modul 3: Oraliqlar daraxti

Oralilar daraxti
Berilgan oraliqda eng katta qism oraliq yig‘indisi

Modul 4: Oraliqlar daraxtida erinchoq yangilanishlar

Oraliqlar daraxtida erinchoq yangilashlar

Modul 6: Daraxtlarga oid texnikalar

Eyler sayri - cho‘qqilarga tashrif buyurish tartibi
Daraxtda DP (Tree DP)

Modul 5: Ikkilik sakrashlar

Ikkilik ko‘tarilishlar (sakrashlar)
Eng kichik umumiy ajdod

Modul 8: Sikllik o'yinlar

Siklik graflarda o‘yinlar

Modul 8: Bo'l va Boshqar

Bo‘l va boshqar

Module 9: SQRT texnikalar

SQRT dekompozitsiyasi
Ildiz evristikalari
Mo algoritmi

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Courses/Course 4/Module 9: SQRT texnikalar/Ildiz evristikalari

Ildiz evristikalari

Ildiz evristikalari

Ildizli evristikalar — bu quyidagi faktga tayanadigan usullar va ma’lumotlar tuzilmalarining umumlashtirilgan nomi:

agar $n$ ta elementdan iborat to‘plamni $\sqrt{n}$ tadan elementli bloklarga bo‘lsak, bloklar soni $\sqrt{n}$ dan oshmaydi.

Up next

Mo algoritmi

Mo algoritmi

Asosiy g‘oya:
«kichik obyektlar ko‘p, lekin ular kichik; katta obyektlar kam»

Og‘ir va yengil obyektlarga bo‘lish

Klassik misol — ildiz bo‘yicha faktorizatsiya.

Agar $d \ge \sqrt{n}$ — $n$ sonining «katta» bo‘luvchisi bo‘lsa, unga «kichik» bo‘luvchi mos keladi:

$\frac{n}{d} \le \sqrt{n}.$

Ya’ni katta bo‘luvchilar kam, chunki har bir kattasiga kichigi mos keladi.

Bunday mantiq ko‘pincha boshqa obyektlarga ham ko‘chiriladi: satrlar, graf cho‘qqilari, so‘rov turlari, buyum og‘irliklari va h.k.

Uzun va qisqa satrlar

Masala

Onlayn tarzda satrlar to‘plamini qo‘llab-quvvatlash va amallarni bajarish kerak:

Satrni to‘plamga qo‘shish
Satrni to‘plamdan o‘chirish
Berilgan satr uchun u to‘plamdagi barcha satrlar orasida nechta marta ostsatr sifatida uchrashini hisoblash

G‘oya

Satrlarni quyidagilarga ajratamiz:

qisqa: $|s| < L$
uzun: $|s| \ge L$

Bu yerda $L$ $\sqrt{S}$ sifatida tanlanadi, bu yerda $S$ — barcha satrlarning umumiy uzunligi.

Shunda uzun satrlar kam: $\frac{S}{L} = O(\sqrt{S})$ dan ko‘p emas.

So‘rovlarga qanday javob berish

Qo‘shish/o‘chirish uchun:
- satrning barcha qisqa ostsatrlarini ko‘rib chiqamiz
- ularning xeshlarini hisoblaymiz va xesh-jadvalni (hisoblagichni) yangilaymiz
3-tur so‘rov:
- agar satr qisqa bo‘lsa — shunchaki jadvaldan uning xeshini ko‘ramiz
- agar satr uzun bo‘lsa — uni to‘plamdagi barcha satrlar bo‘yicha tekshirishga ruxsat beramiz (chunki uzun so‘rovlar kam bo‘ladi)

Grafdagi uchburchaklar

Masala

$\sqrt{S}$ ta cho‘qqi va $m \approx n$ ta qirrali graf berilgan. Uzunligi 3 bo‘lgan sikllar (uchburchaklar) sonini hisoblash kerak.

Og‘ir cho‘qqi ta’rifi

Cho‘qqi og‘ir, agar uning darajasi $\sqrt{n}$ dan katta bo‘lsa, aks holda yengil.

Og‘ir cho‘qqilar kam: ularning soni $O(\sqrt{n})$ dan ko‘p emas.

Uchburchaklar sonini baholash

Uchburchakdagi og‘ir cho‘qqilar soniga qarab ajratamiz:

Og‘ir cho‘qqilar yo‘q
Uchburchakda $(a,b)$ qirrasi bor, uchinchi cho‘qqi $c$ qo‘shnilar kesishmasi/birlashmasida yotadi.
Darajalar kichik bo‘lgani uchun $m \approx n$ tartibidagi cheklovga ega bo‘lamiz.
Bitta og‘ir
Xuddi shunday: «yengil» qirra bor → baho ham $O(m\sqrt{n})$ .
Ikkita og‘ir
$(a,c)$ qirrani fiksatsiya qilamiz, usullar $O(m)$ .
Og‘ir cho‘qqilar jami $O(\sqrt{n})$ → yana .
Uchta og‘ir
Og‘ir cho‘qqilar kam, ko‘rib chiqish ham sig‘adi.

Natijada uchburchaklar «unchalik ko‘p emas»: $O(m\sqrt{n})$ tartibida.

Oddiy yechim (g‘oya)

Cho‘qqilarni (daraja, raqam) bo‘yicha saralaymiz.
Keyin to‘g‘ri tartibda $v \to u \to w$ ko‘rinishidagi yo‘llarni ko‘rib chiqamiz va $v \to w$ qirrasi borligini tekshiramiz.

$O(S\sqrt{S})$ va tezroq ryukzak

Shart

Og‘irliklari $w_1, \dots, w_n$ bo‘lgan $n$ ta buyum bor, bunda:

$\sum w_i = S.$

Standart dinamika $O(S \cdot n)$ da ishlaydi.

Eslatma: turli og‘irliklar kam

Agar yig‘indisi $S$ bo‘lgan $k$ ta turli musbat og‘irlik bo‘lsa, unda:

$S \ge 1 + 2 + \dots + k = \frac{k(k+1)}{2}$

bundan:

$k \le O(\sqrt{S}).$

Ya’ni turli og‘irliklar $O(\sqrt{S})$ dan ko‘p emas.

Karraliklarni siqish (ikkilik darajalar bo‘yicha ajratish)

Agar $x$ og‘irlik $k$ marta uchrasa, $k$ ni ikkilik darajalar yig‘indisiga ajratamiz va bu $k$ ta buyumni quyidagi og‘irlikdagi buyumlarga almashtiramiz:

$x,\ 2x,\ 4x,\ \dots$

Shu tariqa $q \le k$ uchun $q \cdot x$ ko‘rinishidagi barcha yig‘indilar saqlanadi.

Bunday o‘zgartirishdan so‘ng buyumlar soni $O(og‘irliklar\_soni \cdot \log S)$ tartibida bo‘ladi, so‘ng standart dinamikani ishga tushiramiz.

Eslatma: ryukzak yechimini bitset yordamida ancha tezlashtirish mumkin.

)

O(m\sqrt{n})

long long count_triangles(int n, vector<vector<int>> &g) {
    vector<int> deg(n);
    for (int v = 0; v < n; v++) deg[v] = (int)g[v].size();

    auto better = [&](int a, int b) {
        if (deg[a] != deg[b]) return deg[a] < deg[b];
        return a < b;
    };

    // sort vertices by (degree, id)
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), better);

    // sort adjacency lists in the same order
    for (int v = 0; v < n; v++) {
        sort(g[v].begin(), g[v].end(), better);
    }

    vector<int> cnt(n, 0);
    long long ans = 0;

    for (int v : order) {
        // mark all "forward" neighbors of v
        for (int u : g[v]) {
            if (!better(v, u)) break;
            cnt[u] = 1;
        }

        // count triangles v - u - w where v<u<w in this order
        for (int u : g[v]) {
            if (!better(v, u)) break;
            for (int w : g[u]) {
                if (!better(u, w)) break;
                ans += cnt[w];
            }
        }

        // unmark
        for (int u : g[v]) {
            if (!better(v, u)) break;
            cnt[u] = 0;
        }
    }

    return ans;
}