[Решења задатака] 2024/2025 Квалификационо такмичење за Изборно

Karte 3

Аутор: Павле Мартиновић

Текст и тест примери: Алекса Милисављевић

Анализа решења: Павле Мартиновић

Тестирање: Димитрије Ердељан и Александар Вишњић

Решење када N\leq 3

У овом случају се задатак може решити простим посматрањем случајева:

  • Уколико је шпил већ сортиран одговор је очигледно 0
  • Уколико је шпил обрнуто сортиран (3,2,1) тада је одоговор јасно 2 (нпр у првом потезу разбијемо на 2,1 и 3, а затим сортирамо први део са још једним потезом).
  • У свим осталим случајевима је одговор 1, јер увек могуће поделити или на (1 и 2,3 или 1,2 и 3).
    Сада лако можемо решити задатак тако што у сваком тренутку проверимо све ове могућности.

Решење када је N\leq20

Посматрајмо шпилове које добијамо као “листове” овог процеса (односно оне које добијемо у неком кораку и одлучимо да не промешамо). Да бисмо решили задатак, сваки од тих шпилова мора да буде неки низ узастопних бројева. Међутим, по конструкцији, сваки од тих шпилова је подсеквенца оригиналног шпила. Тако да минималан број таквих “лист” шпилова можемо одредити следећим алгоритмом:
Идемо редом кроз шпил и издвојимо најмањи број који нисмо до сад извадили када наиђемо на њега. Сваки пролзак кроз шпил ће нам издвојити један такав “лист” шпил највеће могуће дужине. Тако смо нашли најмању могућу поделу на “лист” шпилове. Нека означимо тај број са k.
Приметимо да за сваки боливијан ми правимо један нови шпил. На почетку имамо само 1 шпил, а на крају k, тако да нам је било потребно барем k-1 боливијана. Докажимо да нам је толико и довољно.
Узимо растући подшпил који смо добили првим проласком кроз низ у алгоритму описаном горе. У првом потезу поделимо шпил на тај подшпил и остатак. По индукцији, други подшпил ћемо моћи сортирати са k-2 боливијана, а када га спојимо са првим шпилом добијамо сортиран цео шпил за k-1 боливијан.
Сада можемо само да симулирамо горњи алгоритам у O(N^2) те решавамо задатак у O(QN^2).

Решење када је N,Q\leq2000

Задатак смо свели на брзо налажење k из претходног решења. Посматрајмо позиције карата x i x+1 у шпилу. Уколико x долази пре x+1 онда ћемо их сигурно покупити у истом пролазу. Ако пак долази после, онда их сигурно нећемо покупити у истом проласку. Ово нам даје да је k-1 заправо број елемената x тако да је x+1 пре x у низу.
Са овим знањем, лако сваки упит можемо решити у O(N): запамтимо позицију сваког елемента у првом пролазу (назовемо овај низ P) и онда избројимо број елемената тако да је P[x]>P[x+1].

Решење када размењујемо само суседне

Приметимо по претходном подзадатаку да лако следи да када размењујемо суседне решење се мења само уколико мењамо x и x+1 (тад се повећава за 1), односно x+1 и x (тад се смањује за 1). Стога можемо у O(N) наћи иницијално решење као у претходном подзадатку, и затим сваки упит решити у O(1) једноставном провером.

Главно решење

Вратимо се на низ P из трећег подзадатка. Приметимо да уколико заменимо вредности x и y, тада заправо заменимо P[x] и P[y]. Када извршимо ову промену, можемо да видимо да се свако 4 пара која нас интересују променило: (x-1,x), (x,x+1), (y-1,y) и (y,y+1). Проверимо за ова 4 пара који су променили распоред и онда ажурирамо решење на одговарајући начин. Иницијално решење можемо да нађемо у O(N), те решавамо цео задатак у O(N+Q).

Највећа појава

Аутор: Немања Мајски

Текст: Марко Миленковић

Тест примери: Немања Мајски

Анализа решења: Димитрије Ердељан

Тестирање: Павле Мартиновић

Решење када N\leq 100

У овом случају, можемо испитати све поднизове низа а_i, за сваки од
њих израчунати суму, и ако је сума 0 пронаћи највећи елемент.
Да би нашли највећи елемент, потребно је да избројимо колико пута се
појављује сваки број у низу. Пошто су бројеви велики, неопходно је да
не трошимо меморију на појављивања бројева којих нема у низу – ово
можемо урадити или коришћењем прикладне структуре (нпр. std::map из
стандардне библиотеке), или тако што на почетку извршавања заменимо
најмањи број у низу са 0, следећи најмањи са 1, и тако даље.

Укупно испитујемо \mathcal{O}(N^2) поднизова, и за сваки нам је
потребно \mathcal{O}(N \log N) ако користимо std::map (могуће је и
mathcal{O}(N) са другим структурама), за укупну временску сложеност
\mathcal{O}(N^3 \log N).

Решење када N\leq 2000

За веће N, неопходно је да не испитујемо сваки подниз. Приметимо да
је од легитимних поднизова који почињу са a_i, најбалансиранији
најдужи, односно онај који се завршава са a_j где је j највеће.
Са овом оптимизацијом, испитујемо \mathcal{O}(N) низова, по један за
свако i, и укупна временска сложеност (користећи приступ из прошлог
подзадатка) је \mathcal{O}(N^2 \log N).

У овом подзадатку, највеће j за које је a_i, a_{i+1}, \dots, a_j
балансиран можемо наћи тако што кренемо од a_i и памтимо суму свих
елемената до j. За комплетан задатак ће нам требати ефикаснији
алгоритам: израчунамо префиксне суме

$$ p_i = a_1 + a_2 + \dots + a_i $$

у једном пролазу кроз низ користећи p_1 = a_1, p_{i+1} = p_i + a_{i+1}, и тражимо крај низа j као највећи индекс где p_j = p_i.

Главно решење

Решење из прошлог подзадатка нам даје N кандидата за легитимне
поднизове који могу бити најбалансиранији. Применићемо још једну
оптимизацију: ако је један од кандидата потпуно садржан у другом,
сигурно није најбалансиранији. Назовимо почетке и крајеве преосталих
поднизова (i_1, j_1), (i_2, j_2), \dots, и сортирајмо их тако да
i_1 < i_2 < \dots. Због ове оптимизације, такође важи j_1 < j_2 < \dots.

Сада можемо користити технику два показивача да их све испитамо.
Потребна нам је ефикасна структура у којој ћемо пратити елементе
тренутног подниза, која подржава додавање, избацивање, и упит за
најчешћи елемент. Када пређемо на k+1-ви подниз, избацимо елементе у
а од i_k до i_{k+1}-1, и додамо оне од j_k+1 до j_{k+1}.
Сваки елемент ћемо убацити и избацити по једном, тако да нам треба
укупно \mathcal{O}(N) операција над структуром.

Један начин да имплементирамо ову структуру је да бројимо елементе
подниза на исти начин као раније (\mathcal{O}(\log N) по упиту са
std::map), и да бројеве појављивања чувамо у std::set, који нам
даје \mathcal{O}(\log N) убацивање, избацивање, и упит за највећу
вредност. Када се број појављивања неког елемента промени, из set-a
само избацимо стари број појављивања и убацимо нови.

Са \mathcal{O}(N) map и set операција сложености
\mathcal{O}(\log N), укупна сложеност је \mathcal{O}(N \log N).

Напомена

Задатак је могуће решити и Моовим алгоритмом уз пажљиву имплементацију.

Радоје

Аутор: Марко Миленковић

Текст: и тест примери: Марко Миленковић

Анализа решења: Марко Миленковић

Тестирање: Јован Бенгин

Напомена

За потребе лакшег изражавања, лишће репрезентације Србије називаћемо плавим тачкама, а остала лишћа црвеним тачкама.

1. Сво лишће туђих репрезентација се налази у троуглу који формирају листови репрезентације Србије.

У овом подзадатку, оптималан круг биће описани круг око три плаве тачке. Ипак, како су све црвене тачке унутар троугла, можемо да закључимо да ће све црвене тачке и бити у описаном кругу. Тако да је решење у овом позадатку једноставно n.

2. Постоји неки максимални скуп S лишћа који Радоје може да украде и који се налази у кругу који формирају листови репрезентације Србије.

У овом подзадатку, потребно је пронаћи описани круг плавих тачака и проверити које тачке се налазе у њему. Центар круга налазимо као пресек симетрала неке две странице троугла. Затим, полупречник као растојање од центра до произвољне плаве тачке. За више детаља: Program to find Circumcenter of a Triangle | GeeksforGeeks

3. n, T <= 10

У овом подзадатку можемо проверити за сваки подскуп црвених тачака, да ли најмањи круг који их садржи, садржи и неку плаву тачку. За решење бирамо највећи подскуп за који се то не дешава.

Нека је неки S максимални скуп лишћа који Радоје може да украде. Постоји права којој је са једне стране скуп S, а са друге стране лишће репрезентације Србије.

Уочимо сценарио из описа овог подзадатка. Поменуту праву можемо да померамо ка плавом троуглу, док не “ударимо” у теме троугла. На овај начин дефинитивно нисмо смањили број црвених тачака у полуравни коју ова права дефинише.

Круг је једнозначно дефинисан својим полупречником и тангентом на тачки на ободу. Можемо као тачку на ободу да фиксирамо као теме плавог троугла и поменуту праву од раније као тангенту. Затим ако центар круга померамо у супротном смеру од плавог троугла (формално нормално у односу на тангенту), круг ће расти и у једном тренутку покупиће све црвене тачке које се налазе са друге стране праве. По услову подзадатка, ово је највећи скуп који можемо да покупимо.

Како бисмо пронашли овај скуп у пракси, за сваку плаву тачку сортирамо црвене тачке у циркуларном редоследу. Помоћу клизајућег прозора тражимо скуп црвених тачака где прва и последња формирају угао са плавом тачком мањи од 180 степени. Ово можемо замислити као да ротирамо праву око плаве тачке и гледамо које црвене се налазе са супротне стране у односу на троугао. И све те тачке смо показали да можемо да покупимо кругом.

Сложеност овог приступа је \mathcal{O}(n\log n).

4. n <= 100, T <= 5

За сваку тројку црвених тачака можемо да пронађемо описани круг. Ако овај круг садржи плаву тачку, игноришемо га. У супротном, избројимо колико црвених тачака је у њему и решење ће бити круг са најбише црвених тачака унутра.

5. Без додатних ограничења

Посматрајмо оптималан круг. Постоји неколико могућих сценарија:

Оптималан круг садржи три плаве тачке на ободу

Ово је други подзадатак. Потребно је пронаћи описани круг плавог троугла.

Оптимални круг садржи две плаве тачке на ободу

Центар круга се онда налази на симетрали ове две тачке. Идеја нам је да померамо центар круга (када фиксирамо центар и две тачке на ободу, јасно је да је круг јединствен) од центра описаног круга па ка бесконачности (у супротном смеру од треће плаве тачке). Међу свим овим опцијама бирамо круг са највише црвених тачака. Међутим, проблем настаје што имамо сувише опција.

Претпоставимо да је симетрала наше две плаве тачке део x-осе. Ово смемо да претпоставимо јер увек можемо да потирамо и транслирамо раван тако да важи. Знамо тачну вредност x-координате која представља границу до описаног круга (ако прекорачимо ову вредност, ухватићемо трећу плаву тачку унутар круга, што није дозвољено). За сваку црвену тачку желимо да нађемо интервал на x-оси за који важи да када је центар круга у њему, црвена тачка ће бити у кругу. Уколико се црвена тачка налази лево (супротно од треће плаве тачке) од странице троугла коју формирају наше две плаве тачке, онда ће црвена тачка бити у кругу од минус бесконачности до неке вредности x_o. Уколико је црвена тачка с десне стране, онда ће тачка бити у кругу од неке вредности x_o до центра описаног круга.

Нека су координате црвене тачке (x,y). Нека су координате једне од две плаве тачке (x_p, y_p) Желимо да израчунамо вредност x_o. Нека је r полупречник тренутног круга. Онда важи:
\begin{eqnarray*} (x-x_o)^2 + (y-y_o)^2 &\leq& r^2\\ (x-x_o)^2 + (y-0)^2 &\leq& (x_p - x_o)^2 + (y_p - 0)^2\\ x^2 - 2xx_o + x_o^2 + y^2 &\leq& x_p^2 -2x_px_o + x_o^2 + y_p^2\\ 2x_px_o - 2xx_o &\leq& x_p^2 + y_p^2 - x^2 -y^2\\ x_o\cdot2(x_p-x) &\leq& x_p^2 + y_p^2 - x^2 -y^2\\ \end{eqnarray*}
Сада разликујемо три случаја, да ли је x_p - x позитивно, негативно или нула:

  1. Ако је x_p - x = 0, то значи да је (x,y) колинеарно са две плаве тачке. По тексту задатка знамо да су све тачке у општем положају, тако да овај случај није могућ

  2. Ако је x_p - x > 0, то значи да је (x,y) “лево” од двеју плавих тачака. Онда сваки круг чији је центар у (x_o, 0) где важи x_o \leq \frac{x_p^2 + y_p^2 - x^2 -y^2}{2(x_p-x)}, садржи црвену тачку (x,y). За остале центре, чија је x-координата већа од овог разломка, тачка (x,y) није у њима.

  3. Ако је x_p - x < 0, то значи да је (x,y) “десно” од двеју плавих тачака. Онда сваки круг чији је центар у (x_o, 0) где важи x_o \geq \frac{x_p^2 + y_p^2 - x^2 -y^2}{2(x_p-x)}, садржи црвену тачку (x,y). За све остале центре, чија је x-координата мања од овог разломка, тачка (x,y) није у њима.

Сада можемо да применимо технику клизајућег прозора. Сортирамо тачке по вредности x_o (само оне тачке које не пробијају границу за центар описаног круга). У почетку све тачке које су лево од двеју плавих тачака бивају у почетном кругу (замишљамо да је центар круга у минус бесконачности). Онда померамо центар круга на следећу вредност x_o. Уколико је ово вредност за црвену тачку лево од плавих тачака, онда смањујемо бројач. Уколико је ово вредност за црвену тачку десно од плавих тачака, онда повећавамо бројач. Решење је највећи бројач у било ком тренутку.

Временска сложеност овог решења је \mathcal{O}(n\log n)

Оптимални круг садржи једну плаву тачку на ободу

Уколико померамо центар круга у супротном смеру од плаве тачке, круг ће расти и увек бити надскуп почетног круга. Уколико у било ком тренутку круг “удари” у другу плаву тачку, налазимо се у претходном случају, који смо већ покрили и не морамо ништа да решавамо.

Уколико круг може бесконачно да расте, падамо у четврти подзадатак, који смо већ видели како можемо да решимо.

Оптимални круг не садржи ниједну плаву тачку на ободу

Фиксирамо центар и повећавамо полупречник. У једном тренутку морамо да “ударимо” у плаву тачку и онда упадамо у претходни случај.

Дакле, укупна сложеност целог решења је \mathcal{O}(n\log n)

Писма из Сукреа

Аутор: Милош Милутиновић

Текст и тест примери: Милош Милутиновић

Анализа решења: Милош Милутиновић

Тестирање: Драган Урошевић

Решење када се S састоји само од нула

Приметимо да никако не можемо добити јединицу, а можемо добити било који стринг који се састоји од нула дужине од 1 до N тако да је решење N.

Решење када је |S| \leq 25

У овом и претходном подзадатку можемо симулирати сва брисања на разне начине тако што пробамо одабир свих могућих сегмената за операцију, на пример BFS алгоритмом.

Решење када се S састоји само од јединица

Посматрајмо финални стринг који желимо да добијемо. Потребан нам је алгоритам да проверимо да ли је могуће добити га. Испоставља се да грамзивим алгоритмом можемо увек узети најмањи префикс чији је xor једнак првом карактеру, избришемо тај префикс и даље решавамо на исти начин. Уколико се xor вредности почетног и финалног стринга разликује свакако није могуће, а у суптоном уколико је за сваки карактер финалног стринга изабран неки сегмент карактера, онда је могуће. Сада можемо радити динамичко програмирање где ће стање бити DP[дужина финалног стринга][позиција докле је гриди алгоритам стигао]. Са сваке позиције можемо додати или нулу или јединицу, и пошто су све јединице у почетном стрингу, интервал који нас занима ће бити дужине највише 2.

Решење када је |S| \leq 5000

Приметимо да можемо радити исти DP алгоритам, само нам је потребно да брзо нађемо први сегмент чији је xor једнак нула или један. То се лако може наћи преко префиксних xor-ова.

Решење за све поене

Можемо избацити димензију за дужину финалног стринга, јер је могуће итерирати по позицији докле је грамзиви алгоритам стигао, пошто је могуће “залепити” све након последњег узетог сегмента, где не долази до пребројавања истог стринга више пута.

lepo takmicenje, dobri su zadaci.