Захваљујући интересантној особини низа, задатак ефикасно може бити решен применом алгоритма бинарне претраге. У питању је варијанта алгоритма бинарне претраге у ком се уместо позиције конкретне вредности у сортираном низу захтева проналажење прве позиције на којој се налази елемент који задовољава неки услов. Наиме, под претпоставком да се у низу прво налазе елементи који не задовољавају тај услов, а затим елементи који задовољавају тај услов, преломну тачку (тренутак када се из једне прелази у другу групу елемената) можемо наћи бинарном претрагом. Дакле, ако је низ облика -------+++++++, бинарном претрагом можемо пронаћи позицију последњег минуса, првог плуса, број минуса или број плусева, где смо са - означили оне елементе који не задовољавају, а са + оне елементе који задовољавају дати услов.
Током рада алгоритма, одржавамо две променљиве \(l\) и \(d\) такве да важи инваријанта да је \(0 \leq l \leq d+1 \leq n\) и да су
У интервалу позиција \([l, d]\) налазе се елементи чији статус још није познат. На почетку су сви елементи непознати, па је јасно да интервал \([l, d]\) треба иницијализовати на \([0, n-1]\), тј. променљиву \(l\) треба иницијализовати на нулу, а \(d\) на вредност \(n-1\). Интервали \([0, l)\) и \((d, n)\) су празни, па је инваријанта очувана (услов \(l \leq d+1\) се своди на \(0 \leq n\), што је тривијално испуњено).
Ако интервал позиција \([l, d]\) није празан тј. ако је \(l \leq d\), проналазимо му средину \(s = l + \left\lfloor{\frac{d-l}{2}}\right\rfloor\).
Ако елемент на позицији \(s\) задовољава услов, тада на основу монотоности услов задовољавају и сви елементи десно од \(s\). Зато померамо \(d\) за једно место лево од средине тј. вредност променљиве \(d\) постављамо на \(s-1\).
Ако елемент на позицији \(s\) не задовољава услов, тада на основу монотоности услов не задовољавају ни сви елементи лево од \(s\). Зато померамо \(l\) за једно место десно од средине тј. вредност променљиве \(l\) постављамо на \(s+1\).
Претрага траје све док се интервал \([l, d]\) не испразни, тј. док је \(l \leq d\). Тада је \(l=d+1\) и елементи који не задовољавају услов се налазе на позицијама \([0, l) = [0, d]\), док се елементи који задовољавају услов налазе на позицијама \((d, n) = [d+1, n) = [l, n)\). Дакле, први елемент који задовољава услов је на позицији \(l\), а последњи који не задовољва услов на позицији \(d\).
Пример. Прикажимо рад алгоритма на једном примеру.
l d 1 7 3 5 9 11 2 8 6 s l d 1 7 3 5 9 11 2 8 6 s ld 1 7 3 5 9 11 2 8 6 s d l 1 7 3 5 9 11 2 8 6
Имплементација се може направити на следећи начин.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int prviKojiNijeDeljiv(const vector<long long>& a, long long k) {
int n = a.size();
int l = 0, d = n-1;
while (l <= d) {
int s = l + (d - l) / 2;
if (a[s] % k != 0)
d = s - 1;
else
l = s + 1;
}
return l;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
long long k;
while (cin >> k)
cout << prviKojiNijeDeljiv(a, k) << '\n';
return 0;
}Доказ коректности. Докажимо формално коректност овог алгоритма. Уз поменуте услове инваријанта је и да важи \(0 \leq l \leq d+1 \leq n\).
Након иницијализације \(l=0\), \(d=n-1\), услови су испуњени (интервали \([0, l)\) и \((d, n)\) су празни, док је услов \(0 \leq l \leq d+1 \leq n\) еквивалентан услову \(0 \leq 0 \leq n \leq n\) и тривијално је испуњен.
Ако интервал позиција \([l, d]\) није празан тј. ако је \(l \leq d\), проналазимо му средину \(s = l + \left\lfloor{\frac{d-l}{2}}\right\rfloor\). Пошто је \(l \leq d\), важи и да је \(l \leq s \leq d\).
Ако елемент на позицији \(s\) задовољава услов, тада на основу монотоности услов задовољавају и сви елементи десно од \(s\). Зато вредност променљиве \(d\) постављамо на \(s-1\) (нове вредности променљивих су \(l'=l\) и \(d' = s-1\)). Тиме инваријанта остаје на снази (посебно, сви елементи у интервалу позиција \((s-1, n) = [s, n)\) задовољавају услов). Важи и услов \(0 \leq l' \leq d'+1 \leq n\), јер је он еквивалентан услову \(0 \leq l \leq s \leq n\).
Ако елемент на позицији \(s\) не задовољава услов, тада на основу монотоности услов не задовољавају ни сви елементи лево од \(s\). Зато вредност променљиве \(l\) постављамо на \(s+1\) (нове вредности променљивих су \(l'=s+1\) и \(d'=d\)). Тиме инваријанта остаје одржана (посебно, ниједан елемент у интервалу позиција \((0, l) = [0, s]\) не задовољава услов). Важи и услов \(0 \leq l' \leq d'+1 \leq n\) који је еквивалентан услову \(0 \leq s+1 \leq d+1 \leq n\).
Када се интервал испразни, тада је \(l > d\), па пошто важи \(0 \leq l \leq d+1 \leq n\), важи и \(l = d+1\). На основу инваријанте знамо да су елементи који задовољавају услов на позицијама \((d, n) = [l, n]\). Зато је први елемент који задовољава услов је на позицији \(l\) (што је уједно и број елемената који не задовољавају услов). Елементи који не задовољавају услов су на позицијама \([0, l) = [0, d+1) = [0, d]\), па је последњи елемент који не задовољава на позицији \(d\).
Заустављање се лако доказује тако што се доказује да се у сваком кораку петље интервал \([l, d]\) тј. његова дужина \(d - l + 1\) смањује, што је прилично очигледно и када је \(l'=l\) и \(d'=s-1 < d\) и када је \(l < l'=s+1\) и \(d'=d\).
Сложеност. Пошто се у сваком кораку претраге ширина интервала \([l, d]\) преполови, пошто се иницијално креће од интервала \([0, n-1]\) који има \(n\) елемената и пошто се алгоритам завршава када се интервал испразни, сложеност алгоритма је \(O(\log{n})\). Наиме, дужина интервала после \(k\) корака је \(\left\lfloor{\frac{n}{2^k}}\right\rfloor\) и важи да је \(\left\lfloor{\frac{n}{2^k}}\right\rfloor < 1\) када је \(k > \log_2{n}\).
Када је кôд коректан, доказ је обично неинформативан. Помаже нам да “мирно спавамо”, али ништа више од тога. Много интересантнија ситуација се дешава у случају када нам формално резоновање о коду помаже да детектујемо и исправимо грешке у програму (тзв. багове). Погледајмо наредни покушај имплементације алгоритма.
int l = 0, d = n;
while (l < d) {
int s = l + (d - l) / 2;
if (a[s] % k != 0)
d = s-1;
else
l = s+1;
}
cout << d+1 << '\n';На основу инцијализације делује да покушавамо да претражимо полузатворени интервал \([l, d)\). Пошто је у питању бинарна претрага, изгледа да се намеће инваријанта да је \(0 \leq l \leq d \leq n\) и да су:
На почетку су оба та интервала празна, па инваријанта за сада добро функционише. Ако погледамо услов петље, делује да петља ради док се интервал непознатих елемената \([l, d)\) не испразни (заиста, када је \(l \geq d\), тај интервал је празан). За сада све ради како треба. Покушамо сада да проверимо да ли извршавање тела петље одржава инваријанту.
Ако \(a_s\) није дељив са \(k\), тада се променљива d поставља на вредност \(d' = s-1\). На основу инваријанте треба да важи да ниједан елемент у интервалу \([d', n)\) није дељив са \(k\). Међутим, ми то не знамо, јер само знамо да је \(a_s\) није дељив са \(k\), али не знамо да \(a_{s-1}\) није дељив са \(k\). Дакле, овде се сигурно крије грешка у коду. Ако доделу d = s-1 заменимо са d = s, тада ће инваријанта бити одржана (јер знамо да \(a_s\) није дељив са \(k\), па са \(k\) неће бити дељив ниједан елемент иза њега).
Ако \(a_s\) јесте дељив са \(k\), тада се променљива l поставља на вредност \(l' = s+1\). На основу инваријанте треба да важи да су сви елементи у интервалу \([0, l')\) дељиви са \(k\), међутим, то ће овде бити испуњено, јер је \(a_s\) дељив са \(k\), па су са \(k\) дељиви и сви елементи испред њега. Дакле, у овом случају је кôд коректан и инваријанта остаје одржана.
На крају, када се петља заврши можемо закључити да важи да је \(l = d\) (јер све време важи да је \(l \leq d\), а након петље не важи да је \(l < d\)). У коду се за позицију првог елемента који није дељив са \(k\) проглашава позиција \(d+1\). Иако је у оригиналној варијанти кода l могло без проблема да се замени са d+1, у овој варијанти то није могуће. Наиме, ми на основу инваријанте овог кода знамо да се на позицији \(l = d\) налази елемент који није дељив са \(k\), а да се на позицији \(l-1\) налази елемент који јесте дељив са \(k\) (осим када је \(l = 0\) и тада нема елемената дељивих са \(k\)). Зато крајњи резултат није коректан и потребно га је заменити са d, јер се први елемент који није дељив са \(k\) налази на позицији \(d\) (осим када су сви елементи дељиви са \(k\), када је \(d=n\), но и тада је \(d\) исправна повратна вредност). Дакле, формалном анализом смо открили и исправили две грешке.
Програмери често програм исправљају тако што насумице покушавају да помере индексе за 1 лево или десно, да замене мање са мање или једнако и слично. Већ на овако кратким програмима се види да је простор могућих комбинација велики, а да је могућност за грешку приликом таквог експерименталног приступа веома велика. Стога је увек боље застати, формално анализирати шта је потребно да кôд ради и исправити га на основу резултата формалне анализе.
На крају, скренимо пажњу на још један детаљ исправљеног програма. Парцијална коректност је јасна на основу анализе коју смо спровели, међутим, заустављање може бити доведено у питање, с обзиром на наредбу d = s. Заустављање доказујемо тако што показујемо да се у сваком корају смањује број непознатих елемената, тј. да дужина интервала \([l, d)\) која је једнака \(d-l\) у сваком кораку петље опада. Пошто је \(l \leq d\) инваријанта, смањивање не може трајати довека, па се у неком тренутку програм зауставља. Поставља се питање да ли се \(d-l\) смањује и у измењеном коду у коме се јавља наредба d=s. Одговор је потрврдан, а образложење је суптилно. Прво, на основу услова петље важи да је \(l < d\). Даље, вредност \(s\) се израчунава наредбом s = l + (d - l) / 2 што нам да је \(s = \left\lfloor{\frac{l + d}{2}}\right\rfloor\). Због заокруживања наниже, важи да је \(s < d\) и зато се након одређивања \(d' = s\), \(l' = l\) вредност \(d' - l'\) смањује у односу на \(d - l\). Важи и да је \(l \leq s\), али пошто је у другој грани \(l' = s+1\) и \(d' = d\), вредност \(d' - l'\) се опет смањује у односу на \(d-l\). Да је заокруживање којим случајем вршено навише (нпр. s = l + (d - l + 1) / 2), програм би могао упасти у бесконачну петљу.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int prviKojiNijeDeljiv(const vector<long long>& a, long long k) {
int n = a.size();
int l = 0, d = n;
while (l < d) {
int s = l + (d - l) / 2;
if (a[s] % k != 0)
d = s;
else
l = s + 1;
}
return d;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
long long k;
while (cin >> k)
cout << prviKojiNijeDeljiv(a, k) << '\n';
return 0;
}