Планине
Аутор: Никола Милосављевић
Текст и тест примери: Никола Милосављевић
Анализа решења: Никола Милосављевић
Тестер: Александар Златески
Анализа
Потребно је у квадратној матрици A пронаћи елемент који је строго највећи у својој врсти и строго најмањи у својој колони – назовимо такав елемент (уколико постоји) седло (то је, иначе, стандарни термин). За почетак приметимо да уколико седло постоји, онда је јединствено; заиста, претпоставимо да су A_{i,j} и A_{k,l} седла. Очигледно, i \neq k и j \neq l. Уколико је A_{i,j} \leq A_{k,l}, тада, због дефиниције седла, A_{i,j} > A_{i,l} > A_{k,l} што је контрадикција; за A_{i,j} > A_{k,l} поново добијамо контрадикцију преко A_{i,j} < A_{k,j} < A_{k,l} па је немогуће да постоје два или више седла.
Из претходног разматрања следи: уколико су нам познате вредности нека два поља (нпр. A_{i,j} и A_{k,l}), можемо елиминасти бар једно од њих као потенцијалног кандидата за седло упитом над највише једним додатним пољем (A_{i,l} или A_{k,j}). Дакле, произвољних M потенцијалних кандидата за седло (за које знамо вредности) можемо свести на само 1 уз не више од M-1 питања коритећи овај метод који ћемо једноставно звати Елиминација.
Подзадаци 1 и 2: Овде је K = N^2 па једноставно можемо питати за вредности свих поља и наћи седло у познатој матрици у сложености O(N^3) уколико за свако поље пролазимо целу његову врсту и колону или у сложености O(N^2) уколико прекалкулишемо максимуме по врстама и минимуме по колонама.
Подзадатак 3: Како су вредности из скупа \{1,2,3\}, јасно је да елемент A_{i,j} може бити седло ако и само ако је A_{i,j} = 2, сви остали елементи у његовој врсти су 1 и сви остали елементи у његовој колони су 3. Према томе, уколико упитамо за вредност A_{i,j} и добијемо вредност 1, елиминисали смо целу j-ту колону (тамо не може бити седло), ако добијемо вредност 3 – елиминисали смо целу i-ту врсту, а ако добијемо вредност 2 - елиминисали смо целу i-ту врсту и j-ту колону осим потенцијално баш елемента A_{i,j}. Упите можемо постављати тако да у сваком упиту елиминишемо бар једну врсту или колону па ћемо након највише 2N упита елиминисати све врсте и колоне и остаће нам највише N поља која могу бити потенцијална седла. Сада применимо Елиминацију (највише још N упита) и још највише 2N упита за проверу да ли је преостали елемент заиста седло (може се показати да је за овај метод горња граница за број упита заправо 4N уместо 5N).
Подзадатак 4: Поставимо упите за све елементе са главне дијагонале и пермутујмо врсте и колоне тако да важи A_{1,1} \leq A_{2,2} \leq \ldots \leq A_{N,N} (ово није проблем, довољно је само запамтити те пермутације и за свако наредно Pitaj(i,j) заправо постављати Pitaj(row[i], col[j])). У новодобијеној матрици, ниједан елемент испод главне дијагонале не може бити седло (немогуће да за i > j важи A_{i,j} > A_{i,i} и A_{i,j} < A_{j,j} јер A_{j,j} \leq A_{i,i}) па седло можемо тражити само на главној дијагонали и изнад, питајући за вредности све кандидате (њих \frac{N(N+1)}{2}) и примењујући Елиминацију (показати да нам приликом Елиминације никада неће требати вредности елемената испод главне дијагонале јер можемо користити поредак на њој!). Овај део можемо и једноставније, налазећи седло као у Подзадатку 2 не користећи елементе испод главне дијагонале (показати да ћемо и у случају “полу-матрице” са соритраном дијагоналом добити највише једног кандидата!). Када добијемо јединственог кандидата, довољно је још N-1 упита за проверу јер је највише толико поља из његове врсте и колоне (од њих 2N-1) испод главне дијагонале. Дакле, треба нам \frac{N(N+1)}{2} + N - 1 упита, што се уклапа у ограничења.
Подзадатак 5: У претходном подзадатку, уместо да питамо за сва поља изнад главне дијагонале, можемо нпр. рекурзивно применити логику за горњи-десни квадрат (и опет питати само око половину свих елемената у њему). Прецизније, радимо следеће
- Уколико је тренутни квадрат димензија 1 \times 1 питамо и вратимо то поље као потенцијалног кандидата; иначе
- Питамо за све елементе главне дијагонале тренутног квадрата и пермутујемо врсте/колоне тако да важи поредак као у претходном подзадатку
- Рекурзивно поновимо поступак за горњи-леви, доњи-десни и горњи-десни подквадрат (за прва два поставимо маркер да не морамо питати/сортирати дијагоналу јер је већ сортирана као део оригиналне) и од 3 добијена кандидата Елиминацијом вратимо само један.
Ако је T(N) број позива Pitaj овог алгоритма за квадрат димензије N \times N, није тешко закључити да важи T(1) = 1 и Т(N) = 3T(\lceil \frac{N}{2} \rceil) за N > 1 (како има пуно “преклапања” дијагонала, можемо замислити да заправо не питамо за поља осим ако је квадрат 1 \times 1) па је T(N) = 3^{\log_2 N} = N^{\log_2 3} (поља која питамо образују неку врсту фрактала а имплементација је благо згоднија јер је N степен двојке). За Елиминацију нам у најгорем случају треба још толико упита (а у пракси много мање због преклапања) и рачунајући коначну проверу то је највише 2\cdot N^{\log_2 3} + 2N упита, што се уклапа у ограничења.
Подзадаци 6 и 7: Назовимо скуп поља S (матрице) добрим уколико никоја два поља из S нису у истој врсти или колони и уколико се седло (уколико постоји) целе матрице налази у пресеку врсте у којој је неки елемент из S и колоне у којој је неки елемент из S. Нпр. један добар скуп је D = \{(1,1), (2,2), \ldots, (N,N)\}.
(*) Приметимо да ако је S добар скуп, тада седло не сме бити веће од највећег елемента из S и не сме бити мање од најмањег елемента из S. Заиста, како седло припада некој колони из S, оно је мање или једнако од бар једног елемента из S па и од максимума; слично и за минимум.
Нека је S произвољан добар скуп и нека је (i, j) \in S такво да је A_{i,j} најмања вредност од свих вредности из S a (k, l) \in S такво да је A_{k,l} највећа вредност од свих вредности из S. Од доброг скупа S можемо добити добар скуп са једним елементом мање на следећи начин: питамо за вредност елемента A_{i,l} и разликујемо 3 случаја:
-
A_{i,l} \leq A_{i,j}: Ако је седло у колони l онда је оно мање од A_{i,l} а самим тим и од A_{i,j} тј. од свих елемената скупа S што је немогуће због (*) . Дакле, у колони l нема седла. Са друге стране, у врсти k је једини кандидат за седло А_{k,l} (иначе би седло морало бити веће од свих елемената из S што је немогуће због (*) ) али већ смо закључили да у колони l нема седла па седло није ни у врсти k. Дакле, избацивањем елемента (k, l) из S опет добијамо добар скуп.
-
A_{k,l} \leq A_{i,l}: Аналогним разматрањем као у претходном случају, добијамо да се избацивањем елемента (i, j) из S опет добија добар скуп.
-
A_{i,j} < A_{i,l} < A_{k,l}: Користећи (*) као у претходним случајевима, добијамо да је A_{i,j} једини кандидат за седло у колони j и да је A_{k,l} једини кандидат за седло у врсти k. Међутим, A_{i,j} и A_{k,l} не могу бити седла због, редом, A_{i,j} < A_{i,l} и A_{i,l} < A_{k,l} па следи да седло није ни у врсти k ни у колони j. Ову врсту и колону можемо избацити тако што из скупа S избацимо елементе (i, j) и (k, l) али убацимо елемент (i, l) (јер морамо задржати i-ту врсту и l-ту колону). Новодобијени скуп је добар и садржи елемент мање.
Када добијемо добар скуп са једним елементом, он је једини кандидат за седло. Дакле, алгоритам је следећи: кренемо од нпр. доброг скупа са дијагоналним елементима D (N упита), сведемо га на добар скуп са једним елементом помоћу додатних N-1 упита и на крају потрошимо још највише 2N упита за проверу. У зависности да ли минимум/максимум у сваком кораку тражимо у O(N) (тривијално) или у O(\log N) (уз помоћ неке структуре), ово пролази за првих 6 или за свих 7 подзадатака.
Решење са очекиваним бројем упита реда O(N): Приметимо да уколико знамо вредности нека два поља (нпр. A_{i,j} и A_{k,l}) можемо елиминисати бар једно од поља A_{i,j}, A_{k,l}, A_{i, l}, A_{k,j} као потенцијалног кандидата за седло без икаквих додатних упита (нпр. ако је A_{i,j} \leq A_{k,l}, можемо закључити да A_{j,k} не може бити седло иако му можда не знамо вредност). Према томе, уколико смо поставили X упита, теоретски можемо елиминисати \frac{X(X-1)}{2} поља гледајући сваки пар упита. Наравно, овде може доћи до пуно преклапања (различити парови упита елиминишу исто поље) али се може показати (а и интуитивно је јасно) да је очекивани број упита (ако их постављамо рандом) потребан за елиминацију свих N^2 поља (осим евентуално једног) реда величине O(N). Додатно, упити не морају бити постављани било како већ у сваком кораку питати само неко тренутно не-елиминисано поље (и помоћу њега и претходних упита радити поменуту елминацију); уколико остане O(N) не-елиминисаних поља у неком тренутку, можда је боље пребацити се на стандардну Елиминацију итд.
Овај приступ, уз евентуалну рандомизацију или боље одабрани редослед упита, пролази за Подзадатке 1, 2, 4 и 5 а често и за 3 (због специфичних вредности и мало веће константе за дозвољени број упита у односу на Подзадатке 6 и 7). Са друге стране ово (вероватно) не може решити Подзадатак 6 (због строжег ограничења у броју упита и евентуално меморијског ограничења) као ни Подзадатак 7 (јер је сложеност O(N^2)).