Lecție-punte: cum alegi tehnica avansată după semnalele problemei

De ce contează?

E zi de olimpiadă. Deschizi enunțul și, înainte să citești povestea, ochii îți fug la linia cu restricții: „n cel mult 40". Un concurent neantrenat trece mai departe; unul antrenat tocmai a aflat jumătate din soluție — la un asemenea n, autorul se așteaptă la ceva exponențial, dar nu pe tot șirul, ci pe jumătăți. Limitele nu sunt o formalitate de la finalul enunțului: sunt un mesaj de la autor despre soluția pe care o are în minte. Capitolul acesta ți-a pus în trusă scule foarte diferite; lecția de față te învață să citești din enunț care dintre ele se cere.

Ideea-cheie

Ai învățat în acest capitol tehnici care nu seamănă deloc între ele: Sqrt Decomposition, algoritmul lui Mo, Meet in the Middle, exponentierea matricilor, includerea-excluderea și funcția Möbius. La concurs însă nimeni nu-ți spune „aici se aplică Mo". Vestea bună: alegerea aproape nu ține de inspirație. Tehnica se citește din două locuri — limitele problemei și forma cerinței.

Observația-cheie

Limitele sunt un mesaj de la autor. Restricțiile sunt alese exact cât să pice soluția naivă și să intre cea intenționată. Câteva „strigăte" clasice:

n în jur de 40 țipă meet in the middle: $2^{40}$ e imposibil, dar $2^{20} + 2^{20}$ e instant;
n până la 10^18 țipă logaritm: nici măcar nu poți parcurge termenii, deci exponentiere de matrice în $O(\log n)$ ;
q de ordinul 10^5 interogări pe intervale, toate cunoscute de la început și fără update-uri, țipă Mo;
o operație pe intervale prea ciudată pentru un arbore țipă sqrt decomposition.

A doua axă e forma cerinței: interogări pe intervale? al n-lea termen al unei recurențe? o submulțime optimă? o numărare cu condiții care se suprapun? Fiecare formă are familia ei de tehnici; limitele aleg apoi membrul potrivit din familie.

Cum decodezi mesajul, concret: într-o secundă de concurs încap în jur de $10^8$ operații simple. Iei soluția naivă, îi estimezi numărul de operații direct din limite și compari. 2^n la n = 40 înseamnă cam $10^{12}$ — pică, dar $2^{20} \approx 10^6$ intră lejer. n * q la n = q = 10^5 înseamnă $10^{10}$ — pică, dar $(n+q)\sqrt{n} \approx 6 \cdot 10^7$ intră. Aritmetica asta de două rânduri e primul lucru pe care îl faci la orice problemă — înainte de orice idee de algoritm.

Ideea-cheie

Observația-cheie

Limitele sunt un mesaj de la autor. Restricțiile sunt alese exact cât să pice soluția naivă și să intre cea intenționată. Câteva „strigăte" clasice:

n în jur de 40 țipă meet in the middle: $2^{40}$ e imposibil, dar $2^{20} + 2^{20}$ e instant;
n până la 10^18 țipă logaritm: nici măcar nu poți parcurge termenii, deci exponentiere de matrice în $O(\log n)$ ;
q de ordinul 10^5 interogări pe intervale, toate cunoscute de la început și fără update-uri, țipă Mo;
o operație pe intervale prea ciudată pentru un arbore țipă sqrt decomposition.

Cum decodezi mesajul, concret: într-o secundă de concurs încap în jur de

10^8

operații simple. Iei soluția naivă, îi estimezi numărul de operații direct din limite și compari. 2^n la n = 40 înseamnă cam

10^{12}

— pică, dar

2^{20} \approx 10^6

intră lejer. n * q la n = q = 10^5 înseamnă

10^{10}

— pică, dar

(n+q)\sqrt{n} \approx 6 \cdot 10^7

intră. Aritmetica asta de două rânduri e primul lucru pe care îl faci la orice problemă — înainte de orice idee de algoritm.

Lecție-punte: cum alegi tehnica avansată după semnalele problemei

Ideea-cheie

Probleme de exersat

Lecție-punte: cum alegi tehnica avansată după semnalele problemei

Ideea-cheie

Probleme de exersat