Module 1: Trie

БОР

Module 2: Sparse Table

Ҷадвали пароканда

Module 3: Segment Tree

Дарахти порчаҳо
Максимумии суммаи зерпорча дар порчаи додашуда

Module 4: Segment Tree Lazy propagation

Дарахти сегментӣ бо паҳнкунии танбалона

Module 5: More on trees

Эйлер тартиби боздиди қуллаҳо
DP дар дарахт (Tree DP)

Module 6: Binary jumping

Бардоштҳои дуӣ (ҷаҳишҳо)
Падари умумии хурдтарин

Module 7: Cyclic Games

Бозиҳо дар графҳои даврӣ

Module 8: Divide & Conquer

Ҷудо кун ва ҳукмронӣ кун

Module 9: SQRT Techniques

Декомпозитсияи SQRT
Эвристикаҳои решавӣ
Алгоритми Мо

Эвристикаҳои решавӣ - Course 4

Асосӣ Курсҳо Манбаъҳо Масъалаҳо Олимпиадаи миллӣ Мусобиқаҳо Ҷадвали роҳбарон

...

Асосӣ/Courses/Course 4/Module 9: SQRT Techniques/Эвристикаҳои решавӣ

Эвристикаҳои решавӣ

Эвристикаҳои решавӣ

Эвристикаҳои решагӣ — номи умумии усулҳо ва сохторҳои додаҳо мебошанд, ки ба ин факт такя мекунанд:

агар маҷмӯаро аз $n$ элемент ба блокҳо бо $\sqrt{n}$ элемент ҷудо кунем, пас шумораи блокҳо аз $\sqrt{n}$ зиёд намешавад.

Up next

Алгоритми Мо

Алгоритми Мо

Идеяи калидӣ:
«объектҳои хурд бисёранд, аммо онҳо хурданд; объектҳои калон каманд»

Тақсим ба объектҳои вазнин ва сабук

Мисоли классикӣ — факторизатсия бо реша.

Агар $d \ge \sqrt{n}$ — тақсимкунандаи «калон»-и адади $n$ бошад, пас ба он тақсимкунандаи «хурд» мувофиқ меояд:

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

Яъне тақсимкунандаҳои калон каманд, зеро ба ҳар як калон як хурд мувофиқ аст.

Ин гуна мантиқро аксар вақт ба объектҳои дигар мегузаронанд: сатрҳо, қуллаҳои граф, навъҳои дархостҳо, вазнҳои ашё ва ғ.

Сатрҳои дароз ва кӯтоҳ

Масъала

Лозим аст онлайн маҷмӯи сатрҳоро нигоҳ дорем ва амалиётҳоро коркард кунем:

Илова кардани сатр ба маҷмӯа
Ҳазф кардани сатр аз маҷмӯа
Барои сатри додашуда ҳисоб кардан, ки чанд маротиба он ҳамчун зерсатр дар байни ҳамаи сатрҳои маҷмӯа во мехӯрад

Идея

Сатрҳоро ҷудо мекунем ба:

кӯтоҳ: $|s| < L$
дароз: $|s| \ge L$

Дар ин ҷо $L$ ҳамчун $\sqrt{S}$ интихоб мешавад, ки $S$ — дарозии ҷамъии ҳамаи сатрҳост.

Он гоҳ сатрҳои дароз каманд: на бештар аз $\frac{S}{L} = O(\sqrt{S})$ .

Чӣ гуна ба дархостҳо ҷавоб додан

Барои илова/ҳазф:
- ҳамаи зерсатрҳои кӯтоҳи сатрро мегардонем
- хешҳои онҳоро ҳисоб мекунем ва ҷадвали хешро (ҳисобкунакро) нав мекунем
Дархости навъи 3:
- агар сатр кӯтоҳ бошад — танҳо хеши онро дар ҷадвал мебинем
- агар сатр дароз бошад — метавонем иҷозат диҳем, ки онро аз рӯйи ҳамаи сатрҳои маҷмӯа санҷем (зеро дархостҳои дароз кам хоҳанд буд)

Секунҷаҳо дар граф

Масъала

Граф аз $n$ қулла ва $m \approx n$ канор дода шудааст. Лозим аст шумораи даврҳои дарозии 3 (секунҷаҳо)-ро ҳисоб кунем.

Таърифи қуллаи вазнин

Қулла вазнин аст, агар дараҷаи он аз $\frac{S}{L} = O(\sqrt{S})$ зиёд бошад, вагарна сабук.

Қуллаҳои вазнин каманд: онҳо на бештар аз $O(\sqrt{n})$ мебошанд.

Баҳодиҳии шумораи секунҷаҳо

Аз рӯйи шумораи қуллаҳои вазнин дар секунҷа ҷудо мекунем:

Қуллаи вазнин нест
Дар секунҷа канори $(a,b)$ ҳаст, қуллаи сеюм $c$ дар буриш/иттиҳоди ҳамсояҳо ҷойгир аст.
Азбаски дараҷаҳо хурданд, маҳдудияти тартиби $m \approx n$ мегирем.
Як қуллаи вазнин
Монанд: як канори «сабук» ҳаст → баҳодиҳӣ ҳам $O(m\sqrt{n})$ .
Ду қуллаи вазнин
Канори $(a,c)$ -ро муқаррар мекунем, роҳҳо $O(m)$ .
Қуллаҳои вазнин ҳамагӣ $O(\sqrt{n})$ → боз .
Се қуллаи вазнин
Қуллаҳои вазнин каманд, баррасии ҳамаи ҳолатҳо низ ҷо мегирад.

Дар натиҷа секунҷаҳо «он қадар зиёд нестанд»: тартибан $O(m\sqrt{n})$ .

Ҳалли содда (идея)

Қуллаҳоро аз рӯйи (дараҷа, рақам) тартиб медиҳем.
Баъд роҳҳои намуди $v \to u \to w$ -ро бо тартиби дуруст мегардонем ва мавҷудияти канори $v \to w$ -ро месанҷем.

Рюкзак бо $O(S\sqrt{S})$ ва тезтар

Шарт

$n$ ашё бо вазнҳои $w_1, \dots, w_n$ ҳастанд, ва:

$\sum w_i = S.$

Динамикаи стандартӣ бо $O(S \cdot n)$ кор мекунад.

Эзоҳ: вазнҳои гуногун каманд

Агар $k$ вазни гуногуни мусбат бо суммаи $S$ бошад, пас:

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

аз ин ҷо:

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

Яъне вазнҳои гуногун на бештар аз $O(\sqrt{S})$ мебошанд.

Фишурдани кратностҳо (таҷзия ба дараҷаҳои ду)

Агар вазни $x$ $k$ маротиба вохӯрад, $k$ -ро ба суммаҳои дараҷаҳои ду таҷзия мекунем ва ин $k$ ашёро ба ашёҳои вазнҳои зерин иваз мекунем:

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

Ҳамин тавр ҳамаи суммаҳои намуди $q \cdot x$ барои $q \le k$ нигоҳ дошта мешаванд.

Пас аз чунин табдил шумораи ашёҳо тартибан $O(шумораи\_вазнҳо \cdot \log S)$ мешавад, ва баъд динамикаи стандартиро ба кор меандозем.

Эзоҳ: ҳалли рюкзакро метавон бо ёрии bitset хеле тез кард.

)

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;
}