Ruutjuurelised võtted

Sections 1 and 2 in English

"Ruutjuureliseks võtteks" võib nimetada misiganes algoritmi, kus ruutjuur kuidagi figureerib. Programmeerimisvõistlustel on ilmnenud mõned ruutjuure algoritmis kasutamise tüüpilisemad mustrid. Neid mustreid on väga erinevaid, aga mõned tüüpilisemad on:

Massiivi tükeldamine
Päringute loetelu tükeldamine
Mingisuguste "asjade" suurteks ja väikeseks jagamine
Mo algoritm

Käesolevas materjalis proovime näidete abil osa neist mustritest näidete varal selgitada, et lugeja suudaks tulevikus ülesannetele selliseid lahendusi välja mõelda.

Vaata ka 2021. aasta materjali.

1. Massiivi tükeldamine

1.1. Massiivi alalõikude summa

Järgmist ülesannet on kindlasti paljud lugejad juba lahendanud ja oskavad lahendada ka keerukusega, mis on parem, kui $O(q \sqrt{n})$. Kuna see on aga kõige lihtsam seda tüüpi ülesanne, siis toome illustratiivsuse mõttes siiski lahenduse välja.

Ülesanne 1. Olgu antud massiiv $A$ pikkusega $n$, kus alguses on kõik elemendid nullid. On $q$ päringut, kaht tüüpi:

Antud $i$ ja $v$. Lisa $A[i]$ väärtusele $v$.
Antud $l$ ja $r$. Leia $A[l] + A[l + 1] + \cdots + A[r]$.

$1 \le n, q \le 10^5$.

Jagame massiivi plokkideks suurusega $B$. Igas plokis hoiame meeles selle ploki elementide summa. Päringute täitmine näeb siis välja nii:

Kui tuleb esimene päring, siis liidame $A[i]$ väärtusele $v$ ja vastava ploki väärtusele samuti $v$.
Kui tuleb teist tüüpi päring, siis liidame vastusele kõik plokid, mis on täielikult vahemiku $l \ldots r$ sees. Seejärel liidame vastusele need elemendid, mis on vahemiku sees, mille plokid aga mitte.

1 / 3

Iga esimest tüüpi päringu täitmine võtab alati $O(1)$ aega. Teist tüüpi päringu korral on meil vaja läbi käia ülimalt $O(\frac{n}{B})$ plokki ja ülimalt $O(B)$ plokivälist elementi. Kokku on iga päringu täitmise keerukus $O(\frac{n}{B} + B)$. See tuleb kõige väikesem, kui võtta $B = \sqrt{n}$. Siis on kogu lahenduse keerukus $O(q \sqrt{B})$.

Selline lahendus on kontseptuaalselt ehk lihtsam, kui lahendus Fenwicki või lõikude puuga. See on ka põhjus, miks ruutjuurelised võtted kasulikud on. Keerukamate päringute puhul võib olla lihtsam ruutjuurelist lahendust välja mõelda.

1.2. Vastikumad arvutused massiivi alamlõikudel

Ülesanne 2. On antud massiiv $A$ pikkusega $n$, kus alguses on kõik elemendid nullid. On $q$ päringut, nelja tüüpi:

Antud $l$ ja $r$. Asendame kõik elemendid $A[l], A[l + 1], \ldots, A[r]$ ühtedega.
Antud $l$ ja $r$. Asendame kõik elemendid $A[l], A[l + 1], \ldots, A[r]$ nullidega.
Antud $l$ ja $r$. Asendame elementide $A[l], \ldots, A[r]$ seas kõik ühed nullidega ja vastupidi.
Antud $l$ ja $r$. Leia vähim $i$ nii, et $l \le i \le r$ ja $A[i] = 0$.

$1 \le n, q \le 10^5$.

Lahenduse üldskeem on sarnane. Kui meil on antud vahemik $l \ldots r$ (ükskõik, mis päringu korral), uuendame iga vahemikku täielikult kuuluvat plokki $O(1)$ ajas ja seejärel elemente, mis on vahemiku sees, mille plokid aga mitte.

Selleks peaksime meeles hoidma iga ploki kohta järgmisi asju:

Kas plokis on kõik elemendid nullideks tehtud?
Kas plokis on kõik elemendid ümber pööratud?

Lisaks hoiame meeles $A[i]$ väärtust iga $i$ korral kahe erandiga:

Kui oleme märkinud, et mingis plokis on kõik elemendid nullitud, siis kohtleme $A[i]$ kui nulli sõltumata sinna tegelikult kirjutatud arvust.
Kui oleme märkinud, et mingis plokis on kõik elemendid pööratud, siis kohtleme $A[i]$ kui tema pöördväärtust.

1.3. Augud

Ülesanne 3. Reas on $n$ auku, nummerdatud $1 \ldots n$. Iga auku iseloomustab tema "jõud" ehk arv $A[k]$. Kui pall satub auku $k$, põrkab ta otsekohe edasi auku $k + A[k]$. Kui sellise numbriga auku pole, väljub pall reast. On $q$ päringut, kaht tüüpi:

Antud $k$ ja $x$. Sea augu number $k$ jõuks $x$.
Antud $k$. Viska pall auku number $k$ ja väljasta, mis on viimane auk, mida pall külastab enne reast väljumist.

$1 \le n, q \le 10^5$.

Sarnaselt eelmistele jagame aukude rea plokkideks suurusega $\sqrt{n}$. Iga augu $k$ kohta hoiame meeles kaks järgmist auku:

$B[k]$: See, kuhu pall august $k$ järgmiseks põrkab.
$C[k]$: Esimene auk, kuhu pall august $k$ jõuab, mis ei ole selle auguga samas plokis.

Nüüd tuleb läbi mõelda, kuidas seda informatsiooni teist tüüpi päringutele vastamiseks kasutada ja kuidas seda informatsiooni esimest tüüpi päringute korral kiirest uuendada.

Teist tüüpi päringutega on asi lihtsam. Siin tuleb lihtsalt olukorda simuleerida, kasutades $C[k]$ nii palju kui võimalik. Nii teeb pall ülimalt $\sqrt{n}$ hüpet.

Oletame nüüd, et meil palutakse augu $k$ jõudu uuendada. Esiteks uuendame muidugi ära $B[k]$. See tähendab, et üle tuleb arvutada $C[k]$, mis on alati kas $B[k]$ või $C[B[k]]$.

Lisaks tuleb uuendada mõndade teiste aukude $C[\cdot]$, kust teekond läbi $k$ läheb. Selleks piisab uuendada (paremalt vasakule!) august $k$ vasakule jäävate, aga samas plokis olevate aukude $C[\cdot]$: muude aukude $C[\cdot]$ muutuda ei saa.

Originaalülesandes tuleb lisaks viimasele augule välja trükkida ka tehtud hüpete arv. Selleks piisab iga $C[k]$ juures meeles pidada, mitmest august see üle hüppab. Neid väärtusi saab uuendada samal ajal ja samamoodi.

2. Päringute tükeldamine

Ülesanne 4. Olgu antud $n \times m$ ruudustik, mille iga ruut võib olla must või valge. Esialgu on kõik ruudud valged. Meile antakse $q$ päringut, neist igaüks on ühel kahest kujust:

Antud $x, y$. Värvi ruut $(x, y)$ mustaks.
Antud $x, y$. Leia ruudu $(x, y)$ kaugus lähimast mustast ruudust.

Ruutude $x_1, y_1$ ja $x_2, y_2$ kauguseks nimetame antud juhul arvu $\left|x_1 - x_2\right| + \left|y_1 - y_2\right|$. (Seda nimetatakse nn. Manhattani kauguseks).

$1 \le nm \le 2 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$.

Kirjeldame esiteks kaht erinevat liiga aeglast meetodit ülesande lahendamiseks:

Hoiame meeles mustade ruutude loetelu. Esimest tüüpi päringu korral lisame uue ruudu loetellu; teist tüüpi päringu korral käime läbi kõik mustad ruudud ja arvutame lähima.
Hoiame igas ruudus meeles lähima musta ruudu asukoha. Esimest tüüpi päringu korral käivitame lisatud ruudust laiuti läbimise, mis uuendab kõikide ruutude kaugusi lähimast mustast ruudust. Teist tüüpi päringu korral võime vastuse lihtsalt tabelist järgi vaadata.

Need meetodid on üsna erinevad, aga mõlemad on liiga aeglased.

Esimese meetodi korral võtab iga esimest tüüpi päring $O(1)$ aega, aga iga teist tüüpi päringu korral tuleb kõik varasemad päringud läbi vaadata: iga teist tüüpi päring võtab $O(q)$ aega. Kokku saame keerukuse $O(q^2)$. Halvimal juhul $q^2 = 4 \cdot 10^{10}$, mis on liiga aeglane.
Teise meetodi korral võib iga esimest tüüpi päringu korral olla vaja uuendada peaaegu kõikide ruutude kaugust, seega esimest tüüpi päringud võtavad igaüks $O(mn)$ aega. Teist tüüpi päringud võtavad $O(1)$ aega. Kokku saame keerukuse $O(nmq)$. Halvimal juhul $nmq = 4 \cdot 10^{10}$, mis on liiga aeglane.

Lahendusidee on need kaks meetodit kombineerida, näiteks järgneval viisil:

Iga esimest tüüpi päringu korral lisame ruudu $(x, y)$ puhvrisse.
Kui puhver saab täis (puhvri suuus ületab arvu $B$), siis käivitame kõikidest puhvri ruutudest samaaegse BFS, mis uuendab kauguste tabelit. Seejärel tühjendame puhvri.
Teist tüüpi päringule vastamiseks vaatame esiteks vastuse kauguste tabelist järgi. Seejärel käime läbi kõik puhvri ruudud ja arvutame nende kauguse ruudust $(x, y)$. Kõikidest saadud vastustest valime minimaalse.

Analüüsime selle keerukust.

Esimest tüüpi päringu töötlemine võtab $O(1)$ aega, v.a. siis, kui puhver saab täis.
Kui puhver saab täis, siis kulub meil $O(nm)$ aega. Puhver saab täis $O(\frac{q}{B})$ korda.
Teist tüüpi päringu töötlemine võtab $O(B)$ aega.

Kokku on keerukus seega $O(\frac{qnm}{B} + qB)$. Saab näidata, et minimaalne on keerukus siis, kui $B = \sqrt{nm}$. Seega saame keerukuse $O(\frac{qnm}{\sqrt{nm}} + q\sqrt{mn}) = O(q \sqrt{mn})$. Halvimal juhul $q \sqrt{mn} \approx 2 \cdot 10^5 \cdot 450 = 9 \cdot 10^7$, mis on piisavalt kiire.

Samamoodi iga $O(\sqrt{n})$ päringu järel andmestruktuuri ümber arvutamise teel on võimalik lahendada ka järgmine ülesane.

Ülesanne 5. Antud massiiv $A$ pikkusega $n$. On $q$ päringut, kaht tüüpi:

Antud $l$ ja $r$. Liida iga $i$, $l \le i \le r$ korral elemendile $A[i]$ arv $F_{i - l + 1}$, kus $F_k$ on $k$-s Fibonacci arv.
Antud $l$ ja $r$. Leia summa $A[l] + A[l + 1] + \cdots + A[r]$ mooduli $10^9 + 9$ järgi.

$1 \le n, m \le 3 \cdot 10^5$.

3. Mo algoritm

3.1. Unikaalsete elementide loendamine

Ülesanne 6. On antud massiiv $A$ pikkusega $n$, mis koosneb arvudest $A[1], A[2], \ldots, A[n]$, mis kõik on vahemikus $1 \ldots 10^5$. Meile antakse $q$ päringut kujul:

Antakse arvud $l$ ja $r$. Arvutada, mitu erinevat arvu on arvude $A[l], A[l + 1], \ldots, A[r]$ seas.

$1 \le n, q \le 10^5$.

Seejuures on oluline märkida, et meile antakse kõik päringud korraga kätte. See tähendab, et me ei pea päringutele vastama samas järjekorras, milles nad meile antakse. Võime neid ümber järjestada kuidas soovime, pärast paneme algsesse järjekorda tagasi. Mo algoritm põhinebki sellel, et üks teatud "naiivne" algoritm muutub väga kiireks, kui päringud on "heas" järjekorras.

"Algoritm otspunktide nihutamisega"

Vaatleme igal hetkel ühte vahemikku meie massiivis; teises massiivis hoiame iga arvu kohta meeles, mitu tükki seda arvu vahemikus on. Vahemiku otspunkte ühe võrra ``nihutades'' liigume päringult päringule.

Kui massiiv on $[3, 5, 5, 6, 5, 2, 3]$ ja päringud on $(2, 5)$, $(3, 7)$ ning $(1, 4)$, siis võib algoritm välja näha midagi sellist:

1 / 9

"Loendamismassiivi" ja vastust saame uuendada iga nihutuse järel keerukusega $O(1)$.

See algoritm ise aga väga hea veel ei ole. Võib ju olla, et iga kahe päringu vahel tuleb nihutada mõlemat pointerit peaaegu $n$ sammu. Nii et halvimal juhul on keerukuseks lausa $O(nq)$. Et $nq$ võib olla kuni $10^{10}$, on algoritm liiga aeglane. Järgmine samm on järjestada päringud ümber kavalal moel nii, et see algoritm muutuks mitu suurusjärku kiiremaks.

Mo järjestus

Järjestame päringud ümber järgmisel moel. Kõigepealt jaotame päringud "plokkidesse":

esimesse plokki lähevad need päringud, mille vasakpoolsed otspunktid jäävad vahemikku $1 \ldots \sqrt{n}$;
teise plokki lähevad need päringud, mille vasakpoolsed otspunktid jäävad vahemikku $\sqrt{n} \ldots 2 \sqrt{n}$;
kolmandasse plokki lähevad need päringud, mille vasakpoolsed otspunktid jäävad vahemikku $2 \sqrt{n} \ldots 3 \sqrt{n}$;
jne.

Nii jaotuvad päringud $\approx \sqrt{n}$ plokki.

Pärast plokkidesse jaotamist sorteerime igas plokis päringud ära parempoolse otspunkti järgi.

1 / 3

Võrdlejafunktsioonid

Mugav viis Mo algoritmi implementeerida on kasutada nn võrdlejafunktsioone. Oletame, et oleme C++ keeles lugenud sisse päringud ja tahame nad Mo järjestusse panna. Näiteks on meil olemasolev kood midagi niisugust:

struct Query {
  int l, r, id;     
};

int main () {
  int n, q;
  cin >> n >> q;

  vector<Query> queries;
  for (int i = 0; i < q; i++) {
    cin >> queries[i].l >> queries[i].r;
    queries[i].id = i;
  }
}

Tahaksime, et saaksime selle päringute vektori panna Mo järjestusse lihtsalt sisseehitatud sorteerimismeetodi abil. Selleks implementeerime funktsiooni comp_mo, mis võtab sisse kaks päringut $p$ ja $q$. Funktsioon peab tagastama true, kui päring $p$ peab tulema järjekorras enne päringut $q$. Üks võimalik implementatsioon on järgmine:

bool comp_mo (Query p, Query q) {
  if (p.l / BLOCK_SIZE != q.l / BLOCK_SIZE) { // kui p ja q kuuluvad erinevatesse plokkidesse
    return p.l / BLOCK_SIZE &lt; q.l / BLOCK_SIZE; // tagastame true, kui p kuulub väikesemasse
  }
  return p.r &lt; q.r; // vastasel juhul sorteerime parempoolse otspunkti järgi
}

Nüüd võime päringute vektori sorteerida sisseehitatud funktsiooni sort abil.

sort(queries.begin(), queries.end(), comp_mo);

Keerukus

Kujutame nüüd ette, et me panime päringud ümber Mo järjestusse ja jooksutame oma otspunktide nihutamise algoritmi selle peal. Paneme tähele, et:

vasakpoolne pointer liigub kahe päringu vahel kõige rohkem $2 \sqrt{n}$ sammu, kokku ei tee ta rohkem, kui $O(q \sqrt{n})$.
parempoolne pointer liigub $\sqrt{n}$ korda vasakult paremale ja tagasi, kokku teeb $O(n \sqrt{n})$ sammu.

Seega keerukus on $O((q + n) \sqrt{n})$. Kui $n = q = 10^5$, siis $(q + n) \sqrt{n} = (10^5 + 10^5) \sqrt{10^5} \approx 6.32 \cdot 10^7,$ mis on piisavalt kiire.

Ja see võimaldabki meil ülesande ära lahendada! Kokkuvõttes:

loeme sisendi sisse ja paneme päringud ümber Mo järjestusse;
kasutame oma otspunktide nihutamisega algoritmi, et saada teada kõigi päringute vastused;
prindime päringute vastused (esialgses järjestuses!) välja.

3.2. Massiivi võimsus

Mo algoritmi saab sageli rakendada ülesannetes, kus on antud päringud, millel on vasak- ja parempoolne otspunkt. Meil piisab vaid kirjeldada otspunktide nihutamisega algoritmi. Siinkohal üks näide.

Ülesanne 7. On antud massiiv $A$ pikkusega $n$. Kõik massiivi elemendid on vahemikust $1 \ldots 10^6$.

Vaatleme selle mingit alammassiivi $A[l], A[l + 1], \ldots, A[r]$. Defineerime alammassiivi $l \ldots r$ võimsuse järgnevalt. Iga $i$ korral tähistagu $K_i$ arvu $i$ esinemiste arvu selles alammassiivis. Alammassiivi $l \ldots r$ võimus arvutatakse siis valemiga $$ 1 \cdot K_1^2 + 2 \cdot K_2^2 + \cdots + 10^6 \cdot K_{10^6}^2.$$ Meile antakse $q$ päringut kujul:

Antud $l$ ja $r$. Leia alammassiivi $l \ldots r$ võimsus.

Vastata kõikidele päringutele. $1 \le n, q \le 10^5$.

Piisab sellest, kui kirjeldame otspunktide nihutamisega algoritmi.

Hoiame meeles mingi vahemiku võimsust ja seda, kui palju on antud vahemikus iga arvu. Hakkame otspunkte nihutama. Kujutame ette, et vahemikku lisandub arv $i$. Enne lisandumist oli vahemiku võimsus

\[ 1 \cdot K_1^2 + 2 \cdot K_2^2 + \cdots + i \cdot (K_i - 1)^2 + \cdots + 10^6 \cdot K_{10^6}^2. \]

Pärast on võimsus

\[ 1 \cdot K_1^2 + 2 \cdot K_2^2 + \cdots + i \cdot K_i^2 + \cdots + 10^6 \cdot K_{10^6}^2. \]

Võimsuse muut on

\[ iK_i^2 - i(K_i - 1)^2= 2i K_i - i. \]

Analoogilise valemi võime tuletada ka siis, kui vahemikust eemaldub arv $i$. Sellest teadmisest piisab, et lahendada ülesanne Mo algoritmi abil.

4. Uuendustega Mo algoritm*

Ülesanne 8. On antud massiiv $A$ pikkusega $n$, mis koosneb arvudest $A[1], A[2], \ldots, A[n]$, mis kõik on vahemikus $1 \ldots 10^5$. Meile antakse $q$ päringut kujul:

Antakse arvud $l$ ja $r$. Arvutada, mitu erinevat arvu on arvude $A[l], A[l + 1], \ldots, A[r]$ seas.
Antakse arvud $i$ ja $x$. Seada $A[i]$ uueks väärtuseks $x$.

$1 \le n, q \le 10^5$.

Nüüd me enam ei saa päringuid ümber järjestada nii, nagu vanasti. Seda seetõttu, et kui uuendustega päringud näiteks vahetavad järjekorda, siis muutuvad sellest ka kõik vastused.

Kuid kõik pole veel kadunud! Me võime kujutada ette, et meilt küsitakse hoopis selliseid päringuid:

Antakse arvud $l$, $r$ ja $t$. Arvutada, mitu erinevat arvu oli arvude $A[l], A[l + 1], \ldots, A[r]$ seas pärast $t$-ndat uuendust (ehk ajahetkel $t$).

Ja selliseid päringuid me võime jälle suvaliselt ümber järjestada ilma, et vastus sellest muutuks.

Vaatleme sisendit:

\[ A = [3, 5, 5, 7, 5, 2, 3]. \]

Päringud:

$l = 2, r = 5$;
$i = 3, x = 1$;
$l = 2, r = 5$;
$l = 3, r = 7$;
$i = 5, x = 6$;
$l = 1, r = 4$.

Teisendatud päringud on siis:

$l = 2, r = 5, t = 0$;
$l = 2, r = 5, t = 1$;
$l = 3, r = 7, t = 1$;
$l = 1, r = 4, t = 2$;

Proovime, kas saame uuele olukorrale kohandada ka Mo järjestuse ja otspunktide nihutamise algoritmi.

"Algoritm otspunktide nihutamisega"

Sarnaselt klassikalisele juhule vaatleme igal hetkel ühte vahemikku meie massiivis ühel kindlal ajahetkel $t$. Vahemiku otspunkte ja ajahetke ühe võrra "nihutades" liigume päringult päringule.

Teeme algoritmi läbi ülaloleval sisendil, kus päringute järjestus on

$l = 2, r = 5, t = 0$;
$l = 2, r = 5, t = 1$;
$l = 1, r = 4, t = 2$;
$l = 3, r = 7, t = 1$;

ja uuendused on $3: 5 \to 1$, $5: 5 \to 6$.

1 / 11

Mo järjestus

Kui vanasti oli meil kaks pointerit (vasak- ja parempoolne), siis nüüd on meil kolm pointerit: vasakpoolne otspunkt $l$, parempoolne otspunkt $r$ ja ajahetk $t$.

Kõigepealt jaotame päringud plokkidesse vasakpoolse pointeri järgi:

esimesse plokki lähevad need päringud, mille vasakpoolsed otspunktid jäävad vahemikku $1 \ldots n^{2/3}$;
teise plokki lähevad need päringud, mille vasakpoolsed otspunktid jäävad vahemikku $n^{2/3} \ldots 2 n^{2/3}$;
kolmandasse plokki lähevad need päringud, mille vasakpoolsed otspunktid jäävad vahemikku $2 n^{2/3} \ldots 3 n^{2/3}$;
jne.

Nii jaotuvad päringud $\approx n^{1/3} = \sqrt[3]{n}$ plokki. Iga ploki siseselt jaotame päringud omakorda gruppidesse parempoolse pointeri järgi:

esimesse gruppi lähevad need päringud, mille parempoolsed otspunktid jäävad vahemikku $1 \ldots n^{2/3}$;
teisse gruppi lähevad need päringud, mille parempoolsed otspunktid jäävad vahemikku $n^{2/3} \ldots 2 n^{2/3}$;
kolmandasse gruppi lähevad need päringud, mille parempoolsed otspunktid jäävad vahemikku $2 n^{2/3} \ldots 3 n^{2/3}$.
jne.

Seega: meil on $\approx n^{1/3}$ plokki, igas plokis $\approx n^{1/3}$ gruppi: kokku $\approx n^{2/3}$ gruppi. Lõppeks sorteerime igas grupis olevad päringud ajahetke järgi ära.

1 / 4

Analoogiliselt klassikalise Mo algoritmiga on mugav ja kompaktne kirjeldada seda järgmise võrdlejaga.

bool compare (Query p, Query q) {
  if (p.l / BLOCK_SIZE != q.l / BLOCK_SIZE) {
    return p.l < q.l;
  } else if (p.r / BLOCK_SIZE != q.r / BLOCK_SIZE) {
    return p.r < q.r;
  } else {
    return p.t < q.t;
  }
}

Keerukus

Arvutame keerukuse nii, nagu varemgi. Paneme tähele, et:

vasakpoolne pointer ei liigu kahe päringu vahel rohkem, kui $2 n^{2/3}$ sammu. Seega vasakpoolne pointer teeb $O(q n^{2/3})$ sammu.
ühe ploki piires ei liigu parempoolne pointer kahe päringu vahel rohkem, kui $2 n^{2/3}$ sammu. Lisaks liigub parempoolne pointer iga kahe ploki vahel paremalt vasakule, tehes nii lisaks $n \cdot n^{1/3}$ sammu. Kokku teeb parempoolne pointer $O(q n^{2/3} + n^{4/3})$ sammu.
ajapointer liigub igas grupis vasakult paremale, seega liigub ta $n^{2/3}$ korda vasakult paremale ehk teeb $n^{5/3}$ sammu.

Kokku on niisiis keerukus $O(q n^{2/3} + q n^{2/3} + n^{4/3} + n^{5/3}) = O(q n^{2/3} + n^{5/3})$. Kui eeldada, et $n \approx q$, siis on sammude arv $O(n^{5/3}) = O(n \sqrt[3]{n^2})$. Kui $n = 10^5$, siis

\[ n^{5/3} = (10^5)^{5/3} \approx 2.15 \cdot 10^{8}. \]

See on päris piiripealne, aga natuke kõrgema ajalimiidi korral läheb läbi.