[Rešenja zadataka] Kvalifikacije 2019 - Drugi krug


#1

Надовезивање

Аутор: Душан Здравковић
Текст и тест примери: Димитрије Ердељан
Анализа решења: Алекса Милисављевић
Тестер: Алекса Милисављевић

Задатак решавамо једноставном провером случајева, направимо свих 6 пермутација и проверимо која има највећу вредност. Приметимо да су бројеви превелики да би стали у тип int у C++, али можемо користити тип long long. Међутим, најпогодније је да бројеве учитамо као string. Тада се операција спајања три броја у неком редоследу своди на конкатенирање стрингова. У C++ конкатенирање два стринга A и B реализујемо са A+B. Функција max у C++ враћа лексикографски већи стринг, ако су јој аргументи стрингови. У нашем случају, пошто ће свих 6 пермутација (A+B+C, A+C+B, B+A+C, B+C+A, C+A+B и C+B+A) имати исту дужину, лексикографски највећа пермутација је и највећи број који можемо добити при спајању бројева A, B и C.


#2

Добри правоугаоници

Аутор: Никола Милосављевић
Текст и тест примери: Момчило Топаловић
Анализа решења: Владимир Миленковић
Тестер: Владимир Миленковић

Приметимо да је K <= 1000000, па уколико ми можемо да у О(1) проверимо да ли су сви бројеви једнаки неком броју у истом правоугаонику, ми можемо решити задатак у О(К), што је сложеност која је довољно добра. Уколико посматрамо све вредности које су једнаке неком броју А, једини кандидат за добар правоугаоник који садржи само бројеве А је најмањи правоугаоник који садржи све њих (уколико би био неки већи, сигурно би постојао број који није једнак том броју, уколико би био неки мањи, постојао би број једнак том броју који није у њему). Сада, провера да ли је тај правоуганик добар је еквивалентна провери да ли је површина тог правоугаоника једнака броју појављивања броја А у матрици (зато што свако појављивање тог броја мора бити у том правоугаонику).

Смернице за алгоритам

Прво, желимо да унапред израчунамо, за сваки број, који је његов одговорајући правоугаоник. Он ће се простирати од најмањег реда у ком постоји тај број до највећег, и од најмање колоне у којој постоји тај број, до највеће. Такође, можемо израчунати и број појављивања сваког броја. Онда, једном петљом, идемо по свих бројевима од 1 до К и проверавамо да ли је кандидат правоуганик добар, у О(1).
Што се тиче сложености, треба нам О(N^2) за препроцесирање, и О(К) за све провере, тако да је укупна сложеност О(N^2 + K).


#3

Рокада

Аутор: Душко Обрадовић
Текст и тест примери: Никола Спасић
Анализа решења: Драган Урошевић
Тестер: Момчило Топаловић

Овај проблем се може решити применом бектрека (backtracking). Али да би се бектрек убрзао (тј. био ефикаснији), на почетку се уради препроцесирање у коме се за свако поље на коме се налаѕи коцкица одреди колико у његовом суседству има слободних поља или поља на која је већ постављен топ и ако се тај број поклапа са бројем на коцкици, онда се и на преостала слободна поља поставе топови. При постављању топова маркирају се сва слободна поља до којих може стићи тај топ (то ће нам касније омогућити ефикасну проверу да ли до сваког слободног поља може стићи неки топ). Након тога се провери да ли постоји поље на коме се налази коцкица такво да је број суседних поља која су слободна или се на њима налази топ мањи од броја на коцкици. Ако такво поље постоји онда није могуће распоредити топове на ту таблу тако да задовољавају сва ограничења, исписује број -1 и прекида извршавање програма.
После ове припремне фазе започиње се распоређивање преосталих топова. То се изводи тако што се обрађује једно по једно поље табле (на пример, врста по врста). Обрада наредног поља се обавља позивом функције, која као аргументе добија врсту и колону у којој се налази то поље, а као резултат враћа информацију да ли је остатак табле успешно обрађен/попуњен. Ако је поље које тренутно обрађујемо заузето или се на њега не може поставити топ зато што би онда око неке коцкице било превише топова, прелази се на следеће поље (тј. позива функција за обраду следећег поља). У супротном се за то поље пробају две варијанте. Прва варијанта је да се на то поље постави топ, маркирају поља до којих може стићи тај топ и настави са обрадом следећег поља на табли. Та обрада се обавља тако што се рекурзивно позива функција за обраду поља која као аргументе добија координате (врсту и колону) поља које се обрађује. Ако је остатак табле успешно попуњен, друга варијанта се не разматра већ се прекида извршавање и враћа информација да је успешно попуњена табла. У супротном, ако остатак табле није успешно попуњен, разматра се друга варијанта, у којој се на то поље не распоређује топ, већ се прелази на наредно поље табле, тј. рекурзивно позива функција за решавање следећег поља. Ако се решавање остатка табле успешно заврши, онда функција враћа информацију да је остатак табле успешно решен, у супротном, враћа информацију да остатак табле није успешно решен.
Када се обраде сва поља табле, тј. позове функција за обраду поља које се налаи врсти број M+1 и колони број 1, проверава се да ли је попуњавање коректно/исправно: број топова око сваке коцкице се поклапа са бројем на коцкици и до сваког слободног поља може стићи неки од топова. Ако је попуњавање табле исправно функција враћа информацију да је табла попуњена исправно, у супротном, враћа информацију да табла није успешно попуњена.
Да би се додтно убрзао поступак, може се при сваком позиву функције за обраду поља проверавати да ли постоји коцкица таква да је збир броја постављених топова на суседним пољима и броја слободних суседних поља мањи од броја на коцкици. Ако таква коцкица постоји, није могуће распоредити топове према захтевима, па се прекида обрада тог поља и враћа назад (тј. на обраду претходног поља).


#4

Бојење

Аутор: Димитрије Ердељан
Текст и тест примери: Филип Ћосовић
Анализа решења: Димитрије Ердељан
Тестер: Марко Савић

Доказаћемо да оптимално решење сигурно има следећи облик: број белих
поља у колони опада до неке тачке, а затим расте до краја, или расте
до неке тачке па опада до краја. Ово значи да, ако сортирамо редове по
позицији где им се мења боја, првих K редова бојимо бело-црно, а
остале црно-бело.

Да би доказ био једноставнији, уместо да бирамо боје за редове,
бираћемо функцију f, где је f(i) број белих поља у колони између
“промена” i-1 и i. За валидна бојења зида важе следеће особине
f, и обрнуто, ако особине важе можемо направити бојење:

  • f(0) + f(n) = n (сви редови промене боју)
  • За свако i, |f(i) - f(i-1)| = 1 (сваки пут се мења тачно један
    ред)

Доказ овога остављамо читаоцу.

Прво, сигурно постоји тачно један “тренутак” (део зида између две
промене) када имамо по \frac{N}{2} црних и белих поља (за непарно
N, сличним аргументом доказујемо да се тачно једном број мења са
“више белих” на “више црних”), тј. постоји тачно једно x за које
f(x) = \frac{n}{2}. Када ово не би било тачно, могли бисмо да
побољшамо решење:

  • Нађемо x такво да је f(x) = \frac{n}{2} и f(x-1) = f(x+1) = \frac{n}{2} + 1 (или слично за -1) – ако не постоји, можемо
    одабрати неки интервал између две тачке где f(i) = \frac{n}{2} и
    “обрнути” их (поставити f(i) = n - f(i)) тако да се не промени
    вредност решења.
  • Поставимо f(x) = \frac{n}{2} - 2.

Без губитка општости претпоставићемо да f(0) < \frac{n}{2} (почињемо
са мање белих него црних поља). На сличан начин можемо доказати да на
интервалу од 0 то тачке где имамо исти број црних и белих поља
функција f опада до неке тачке па расте, а од те тачке расте па
опада.

Дакле, оптимално f мора имати облик “опада, па расте, па
опада”. Сада ћемо доказати да не можемо имати оба опадајућа дела: ако
постоје, можемо смањити f(0) за 2 и повећати f(n) за 2 и
добити боље решење.

Сада смо доказали да је оптимално решење или да број белих поља расте
до неке тачке па опада до краја, или обрнуто. Како за сваки избор
броја белих поља на почетку постоји тачно једна тачка где можемо прећи
са растућег на опадајуће, или са опадајућег на растуће (када су сва
поља исте боје), имамо \mathcal{O}(n) опција које треба проверити.

Сада још остаје да нађемо начин да израчунамо колико бојење вреди, ако
је дат број белих поља K на почетку, и знамо да тај број опада првих
x колона а затим расте до N-K.

Смернице за алгоритам

Израчунаћемо само вредност бојења од почетка до колоне x. Од те
колоне до краја метод је идентичан.

Вредност коју треба израчунати је:

\sum_{i = 0}^{x} (A_i - A_{i-1}) \cdot (K - i) = K \sum_{i=0}^x (A_i - A_{i-1}) - \sum_{i=0}^x i \cdot (A_i - A_{i-1})

Да бисмо ово рачунали у константном времену, на почетку програма је
довољно да израчунамо низове префиксних сума које нам дају ове две
“мале” суме за свако x.


#5

Вредност доделе

Аутор: Иван Стошић
Текст и тест примери: Никола Спасић
Анализа решења: Никола Спасић
Тестери: Алекса Милисављевић, Иван Стошић

Означимо скуп \{1, 2, \ldots, N\} са [[N]].
Посматрајмо доделе вредности за i = 0 и дефинишимо две функције

  • f : [[N]] \rightarrow [[N]], таква да је a'_j = f(a_j), где је a'_j вредност на позицији j у низу A након извршавања додела вредности за i = 0 а a_j је та вредност пре извршавања додела.
  • g : [[N]] \rightarrow [[N]], g(N) := 1; g(x) := x + 1, x \neq N циклично померање за једно место улево.

Сада ћемо операцију коју треба извршити на низу A (за свако i \in \{0, 1, \ldots, N-M \} и за свако j \in \{0, 1, \ldots, M-1\}) означити са z, где је z : [[N]] \rightarrow [[N]]. Означимо са z_i : [[N]] \rightarrow [[N]] операцију на низу A која одговара извршавању унутрашње фор-петље (по j) за дато фиксно i. Јасно је да важи: z = z_{N-M} \circ z_{N-M-1} \circ \ldots \circ z_0. Кључна идеја је то што z_i можемо записати у облику z_i = g^{-i} \circ f \circ g^i. Ово важи зато што пресликавањем g^i “ротирамо” низ у такву позицију да елемент који је био на позицији i је сада на позицији 0. Након тога примењујемо доделу вредности са f и поново ротирамо низ у контра смеру за i места.

Ако затим проширимо израз за z и скратимо суседне парове \ldots g^{i} \circ g^{-(i-1)} \ldots остаје нам z = g^{-(N-M)} \circ (f \circ g)^{N-M} \circ f, односно, краће z = g^{-k} \circ (g \circ f)^k, где смо увели ознаку k := N-M+1. Како се g^{-k} лако рачуна као десна ротација за k места, ако уведемо ознаку h := g \circ f остаје нам да израчунамо k-ти степен ове функције.

Да бисмо за свако i пронашли вредност h^k(i) конструишемо граф са чворовима \{1 \ldots N\} и усмереним гранама \{x \rightarrow h(x), x \in [[N]]\}. Како је усмерен, коначан и из сваког чвора излази тачно једна грана, компоненте повезаности (посматрајући граф као неусмерен) изгледају као циклуси са стаблима чији је тачно један чвор део циклуса (приметити да како је могуће да h(i) = i постоји могућност да циклус садржи само један чвор). Усмерење грана у циклусу мора бити такво да је циклус и у усмереном графу, док усмерење грана у стаблима мора бити такво да је улазни чвор ближи циклусу од излазног.

Обилазећи сваку компоненту повезаности (посматрајући граф као неусмерен) у њој проналазимо циклус за чији сваки чвор налазимо h^k(i) као c((id(i) + k) \mod d) где је d дужина циклуса који садржи чвор i, idx(x) даје редни број чвора x у циклусу док c(x) означава x-ти чвор на том циклусу. За “почетак” циклуса можемо изабрати произвољан чвор. Затим dfs обиласком, кроз стабла повезана са тим циклусом, уназад (супротно усмерењу грана) за сваки чвор i чији је отац у стаблу обиласка o_i рачунамо h^k(i) или као претходника чвора h^k(o_i) у циклусу уколико је i на растојању од циклуса мањем од k или као сина чвора h^k(o(i)) у стаблу обиласка у чијем подстаблу се налази чвор i. Овог сина можемо наћи тако што одржавамо низ који одговара стеку чворова током dfs-а и узимањем k-тог претходника тренутног чвора.

На крају потребно је само израчунати тражену вредност, знајући вредности низа A након свих додела вредности.

  • Временска сложеност алгоритма O(n)
  • Просторна сложеност алгоритма O(n)