[Rešenja zadataka] Kvalifikacije 2020 - Treći krug

Algoritam
1

Упознавање

Аутор: Никола Пешић
Текст и тест примери: Лазар Миленковић
Анализа решења: Драган Урошевић
Тестер: Владимир Миленковић

Анализа

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

Покажимо да Милош у оптималном поступку (редоследу) упознавања са пријатељима не може проћи два или више пута “поред” своје куће. Нека су комшије сортиране према својој позицији, тј. тако да је

a_1 \leqslant a_2 \leqslant a_3 \leqslant \dotsb \leqslant a_n.

Нека је у оптималном поступку упознавања, Милош ишао на десно до комшије {r_1}, затим се “вратио” до кoмшије l, а потом од комшије {l} поново кренуо удесно до комшије {r_2} (r_2 > r_1).
Тада је време упознавања тих комшија износило

(a_{r_1} – x) + (a_{r_1} – a_l) + (a_{r_2} – a_{l}).

Међутим, ако би Милош ишао прво улево до комшије l, а након тога удесно до комшије {r_2}, упознао би исти скуп комшија, али би време упознавања износило

(x – a_l) + (a_{r_2} – a_{l}).

Лако се показује да важи:

(a_{r_1} – x) + (a_{r_1} – a_l) + (a_{r_2} – a_{l}) > (a_{r_1} – a_l) + (a_{r_2} – a_{r_1}) > (x – a_l) + (a_{r_2} – a_{r_1}).

На сличан начин би се поступило да је ишао улево до комшије {l_1}, затим удесно до r и након тога поново улево до комшије {l_2} (l_2 < l_1). Тај распоред би се могао заменити распоредом у коме би ишао удесно до комшије r, а затим улево до комшије {l_2} (а време упознавања за тај распоред је мање).

Према томе, ако постоји бар један комшија лево и бар један комшија десно, издвајају се два редоследа за упознавање комшија:

  • Милош може ићи улево до крајње левог комшије, а затим удесно до крајње десног комшије, или
  • Милош може ићи удесно до крајње десног комшије, а затим улево до крајње левог комшије.

Време упознавања у првој варијанти је

x-a_1 + a_n – a_1,

а у другој варијанти је

a_n – x + a_n – a_1.

Минимално време упознавања је

\min\{ x-a_1 + a_n – a_1, a_n-x + a_n – a_1,\} = a_n – a_1 + \min\{x-a_1, a_n – x\}.

За крај приметимо да низ a није неопходно сортирати јер је су нам потребне само вредности првог и последњег елемента сортираног низа, а то су заправо најмањи и највећи елемент низа.
Временска сложеност овог решења је O(n).

5 Likes
2

Лубенице

Аутор: Алекса Плавшић
Текст и тест примери: Алекса Плавшић
Анализа решења: Никола Јовановић
Тестер: Никола Јовановић

Анализа

Приметимо да за свако k и свако N важи \lceil\frac{N}{k}\rceil \geq \frac{N}{k}, из чега следи неједнакост \lceil\frac{N}{p}\rceil + \lceil\frac{N}{q}\rceil + \lceil\frac{N}{r}\rceil \geq \frac{N}{p} +\frac{N}{q}+\frac{N}{r}. У складу са овим, раздвајамо проблем на три случаја у зависности од вредности p,q,r:

Први случај: \frac{N}{p} +\frac{N}{q}+\frac{N}{r}>N \Leftrightarrow pq+pr+qr > pqr

  • Из горње неједнакости имамо \lceil\frac{N}{p}\rceil + \lceil\frac{N}{q}\rceil + \lceil\frac{N}{r}\rceil > N, па услов тражен у задатку не може бити испуњен ни за једно N, те је коначно решење 0, независно од вредности L и R.

Други случај: \frac{N}{p} +\frac{N}{q}+\frac{N}{r}=N \Leftrightarrow pq+pr+qr = pqr

  • У овом случају имамо да је услов тражен у задатку испуњен само ако је \lceil\frac{N}{p}\rceil + \lceil\frac{N}{q}\rceil + \lceil\frac{N}{r}\rceil = \frac{N}{p} +\frac{N}{q}+\frac{N}{r}, што је могуће само ако p|N и q|N и r|N, што је еквивалентно томе да d | N, где је d=NZS(p,q,r). Дакле, треба наћи број природних бројева дељивих са d у интервалу [L,R]. Ово добијамо рачунањем броја таквих бројева у [1,R] и одузимањем броја таквих бројева у [1,L-1]: \frac{R}{d} - \frac{L-1}{d}.

Трећи случај: \frac{N}{p} +\frac{N}{q}+\frac{N}{r}<N \Leftrightarrow pq+pr+qr < pqr

  • Последњи случај је најсложенији јер нас првобитна неједнакост не доводи директно до закључка, тј. да ли је подела могућа за неко N зависи на нетривијалан начин од дељивости са p,q,r.
  • Иако нас ограничења за L и R одвраћају од brute-force решења (пролазак кроз све бројеве од L и R и провера да ли је тражени израз тачан), често је у оваквим ситуацијама, када је потребно пронаћи шаблон, добра идеја генерисање и посматрање вредности које brute-force произведе. Уколико то овде урадимо за нпр. (p,q,r)=(2,3,7) (други подзадатак) и (L,R)=(1,300) можемо приметити да је подела могућа за свако N \in [50, 300], из чега природно претпостављамо да је могућа за свако N \geq 50. У ову претпоставку се можемо додатно убедити повећавањем R.
  • Уколико је ово тачно за (p,q,r)=(2,3,7), тачно је и за свако друго (p' \leq q' \leq r') које спада у трећи случај, јер мора да важи p'>p, q'>q, r'>r (проверити!) па је стога (ако је наша претпоставка тачна) за свако N > 50: \lceil\frac{N}{p'}\rceil + \lceil\frac{N}{q'}\rceil + \lceil\frac{N}{r'}\rceil \leq \lceil\frac{N}{p}\rceil + \lceil\frac{N}{q}\rceil + \lceil\frac{N}{r}\rceil \leq N.
  • Ово нас доводи до ефикасног решења за трећи случај: за свако N < 50 у [L,R] проверимо услов “ручно”, док за N \geq 50 претпоставимо да сигурно важи. Ово се испоставља као тачно, а уколико желимо да будемо у потпуности сигурни могуће је тврдњу сличну нашој претпоставци и мало форманије доказати (хинт: посматрати понашање израза \lceil\frac{N}{p}\rceil + \lceil\frac{N}{q}\rceil + \lceil\frac{N}{r}\rceil за nzs(p,q,r)|N).
3 Likes
3

Сазвежђа

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

Анализа

Уколико имамо x тачака и све леже на истој правој, свака тројка је колинеарна, па је број таквих тројки једнак \binom{x}{3}. Једно решење је да се направи низ бројева b_1, b_2, \ldots, b_m такав да важи \binom{b_1}{3} + \binom{b_1}{3} + \ldots + \binom{b_m}{3} = K и да се изгенерише m правих, да се на i-ту праву нанесе b_i тачака, и да се све ово уради на такав начин да ниједне три тачке не буду колинеарне осим уколико потичу са исте праве.

Овај низ бројева се може наћи грабљивим поступком - докле год је K > 0, бирамо највеће x такво да је \binom{x}{3} \leq K, додајемо x на низ и смањујемо K за \binom{x}{3}. Може се показати (на пример, применом грубе силе) да овај поступак резултира у не више од 1049 тачака, и то у не више од 10 корака.

За праве можемо изабрати узастопне различите праве које су паралелне x-оси, односно праве y=1, y=2, \ldots. Тачке можемо ређати почев од координате q_i = i^2 \times 10^6 за i-ту праву, односно, на правој са редним бројем i биће тачке {(q_i, i)}, {(q_i+1, i)}, \ldots, {(q_i+b_i-1, i)}. Ова “конвексност” обезбеђује да ниједне три тачке са различитих правих не буду колинеарне.

Подзадаци се могу решити применом грубе силе или неког једноставнијег поступка постављања правих.

4 Likes
4

Боје

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

Анализа

Лако је видети да се овај задатак може свести на тражење броја повезаних компоненти међу пољима која нису обојена. Сваку такву компоненту можемо обојити новом обојом. У остатку решења ћемо описати како се број повезаних компоненти може ефикасно наћи под ограничењима датим у овом задатку.

Решење у O(N \cdot M)

Да бисмо пронашли број компоненти, једноставно можемо да применимо Depth First Search (DFS) алгоритам од сваког необојеног поља које нисмо до сада овим алгоритмом посетили. Пошто број чворова и грана у графу који представљају необојена поља има сложеност O(N \cdot M), овај приступ би био врло спор за највеће тест примере.

Посматрајмо пример где је N = M = 10^9 и K = 10^5. У том примеру постоје “велики” делови табле који су необојени а повезани. Интуитивно, уместо да свако поље тих “великих” делова посматрамо као чвор, било би згодно ако бисмо цео “велики” део посматрали као један чвор. У том случају би горе описани DFS-приступ имао далеко мању сложеност. Наравно, главно питање овде је како изабрати велике делове тако да је згодно са њима радити, а успут свести број чворова које посматрамо на мали број. У остатку решења ћемо се фокусирати на ово питање.

“Велики” делови табле и решење у O(К \cdot \log{K})

Сада ћемо објаснити како да од улаза направимо граф који има O(K) чворова и O(K) грана.

Чворови

Најпре, узастопне колоне који немају иједно црно поље ћемо посматрати као један чвор. Пошто је, сем првог и последњег, сваки такав чвор ограничен колонама које имају бар једно црно поље, број таквих чворова је највише K + 1.

Посматрајмо сада колону која има бар једно црно поље. Ако колона има t црних поља тада се она може изделити у t + 1 или мање низова узасотпних необојених поља. Сваки од тих низова ћемо посматрати као посебан чвор. Таквих чворова има највише 2 K.

Гране

Да бисмо излистали гране, посматраћемо по две суседне колоне и чворове које оне дефинишу, под условом да бар једна од колона има бар једно црно поље. (Две суседне колоне које немају црна поља су део истог чвора.) Нека је C_1 листа чворова прве, а нека је C_2 листа чворова друге колоне. Сваки чвор v је представљен као пар (a, b), што значи да је v подниз узастопних необојених поља који се у одговарајућој колони пружају између редова a и b. Претпоставимо да су чворови у C_1 и C_2 сортирани у растућем поретку по првој координати. Тада, се следећи алгоритам може применити да се нађу све гране између чворова у C_1 и C_2.

Нека је v_1 = (a_1, b_1) \in C_1 тренутни чвор који обрађујемо у C_1, а v_2 = (a_2, b_2) \in C_2 тренутни чвор који обрађујемо у C_2. На почетку, v_1 је први чвор из C_1, а v_2 је први чвор из C_2. Примењујемо следеће све док нисмо прошли све чворове из бар C_1 или C_2:

  • Ако b_1 < a_2, поставимо v_1 да буде следећи чвор у C_1.
  • Ако b_2 < a_1, поставимо v_2 да буде следећи чвор у C_2.
  • Иначе, додамо грану између v_1 и v_2. Ако је b_1 < b_2, онда поставимо v_1 да буде следећи чвор у C_1, а иначе поставимо v_2 да буде следећи чвор у C_2.

Није тешко проверити да се на овај начин заиста дефинишу све гране између чворова у C_1 и C_2. Поред тога, сваки пут кад се дода грана чвор v_1 или чвор v_2 се помере за један место. То значи да се у овом процесу дода највише |C_1| + |C_2| грана. Пошто је свака колона суседна са највише две друге колоне и пошто смо рекли да је укупан број чворова K + 1 + 2 K, овим процесом се дода највише 2 (3K + 1) грана.

Да бисмо пронашли број повезаних компоненти над оваквим графом можемо да применимо DFS; алтернативно, уместо DFS-а можемо искористити union-find структуру. Cортирање чворова у колони C се може урадити у времену O(|C| \log{|C|}), тако да је укупна сложеност целог алгоритма O(K \log{K}).

Алтернативно решење

Овај задатак са такође може решити применом Ојлерове формуле за планарне графове. Наиме, ако нам је дат планаран граф G на n чворова, са m грана, f повезаних области и c компоненти, тада важи n - m + f = 1 + c. Ову формулу можемо искористити да решимо задатак на следећи начин.

За четири поља која имају координате (x, y), (x, y + 1), (x + 1, y), (x + 1, y + 1) кажемо да чине 2x2 квадрат.

Замислићемо да је табла оивичена траком црне боје. Целу ту траку ћемо посматрати као један чвор. Потом, у центар сваког црног поља ћемо ставити чвор. Повезаћемо два чвора граном ако одговарајућа црна поља деле макар једно теме, и поред тога избацићемо гране које спајају наспрамна поља у 2x2 црном квадрату (грану која спаја поља (x, y) и (x + 1, y + 1), и грану која спаја поља (x + 1, y), (x, y + 1)). Ове гране избацујемо да бисмо очували планарност. Приметимо да је ова дефиниција суседних црних поља другачија него она у поставци задатка. Такође ћемо повезати траку која оивичава таблу са сваким чвором који додирује ивицу табле, тј., са сваким чвором који се налази у првом или у последњем реду или у првој или у последњој колони. Овај граф је планаран. Поред тога, граф има O(K) грана, тако да вредност c можемо лако наћи, на пример, DFS алгоритмом.

Користећи наведену формулу можемо да израчунамо f. Али шта представља f? Најпре, свака четири чвора која чине 2x2 квадрат ће у овој дефиницији планарног графа формирати једну повезану област. Такође ће и свака три чвора у “Г облику” (тј. имају координате (x, y), (x, y + 1), (x + 1, y)) и ротацијама ове конфигурације чинити повезане области. Поред ових области, f броји повезане области које одговарају необојеним пољима, што је управо број оних области које су решење овог проблема. Дакле, да бисмо решили овај проблем, потребно је да од f одузмемо 2x2 црне квадрате.

За имплементирање DFS-а можемо сместити сва црна поља у hash мапу, или на пример у структуру map у C++. Приступом овој мапи је онда лако наћи које суседе има дати чвор.

Да резимирамо, да бисмо решили проблем, потребно је да: (1) направимо граф као што је то описано; (2) израчунамо c; (3) пребројимо 2x2 црне квадрате, и пребројимо црне квадрате који чине “Г облик” и његове ротације; и (4) користећи наведену формулу израчунамо решење овог проблема.

3 Likes
6

К-тачне секвенце заграда

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

Анализа

Идеја за динамичко програмирање

За решавање проблема користићемо динамичко програмирање.
Нека dp[i][v][k] прставља број начина на који можемо да поставимо још i заграда ако је тренутна префиксна сума постављених заграда v (ако узмемо да је ( једнако 1 а ) једнако -1) и можемо да обришемо још k заграда.
За прелазе имамо 2 опције: Постави ( као следећу заграду или постави ) као следећу заграду.
Ако постављамо (, из стања dp[i][v][k] ћемо прећи у стање dp[i-1][v+1][k].
Ако постављамо ) имамо 2 опције:

  • v=0, ако је k>0, из стања dp[i][0][k] ћемо прећи у стање dp[i-1][0][k-1].
  • v>0, из стања dp[i][v][k] ћемо прећи у стање dp[i-1][v-1][k].

На почетку треба да иницијализујемо dp[0][v][k] на 1 ако је v<=k, а на 0 у осталим случајевима.
Такође треба пазити на overflow, вредности у dp-у веома брзо могу да премаше long long, тако да је потребно ограничити их да не могу да буду веће од 2^{61} или неке сличне вредности. 2^{61} је добра вредност јер 2\cdot 2^{61} идаље стаје у long~long, док је 2^{61} веће од највеће могуће вредности за t.
Уз помоћ овог dp-а, можемо да одговоримо на упите. За упит n,k,t ћемо кренути од стања dp[n][0][k] и након тога ћемо радити следеће док n не постане 0 :

  • Ако је dp[n-1][v+1][k]\geq t, прећи ћемо у то стање и на одговор додати (.
  • У супротном ћемо од t одузети dp[n-1][v+1][k], на одговор додати ) и прећи у стање dp[i-1][0][k-1] ако је v=0 или dp[i-1][v-1][k] ако је v>0.

Са овим решењем се могло добити 40 бодова, док се са мало модификованим решењем (за случај када је k=0), могло добити још 10 бодова.
Главни проблем овог решења је меморија, тако да ћемо се у следећем делу фокусирати на смањење меморије.
Биће описана 3 решења, у редоследу од најлакшег до најтежег за имплементацију. Прво решење је алтернативно решење за проблем, друго користи идеју коју је Тадија Шебез користио да реши проблем, и треће је замишљено решење.

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

Решење 1

Ово решење користи чињеницу да у нашем dp-у има мало вредности које нису 0, а мање су од 2^{61}. Штавише, има тачно 2,358,736 таквих вредности.
Постоје 2 случаја када је dp[i][v][k]=0:

  • i+k-v<0
  • k=0 и i\not\equiv v\ (\textrm{mod}\ 2)

Треба нам још добар начин да сачувамо ове вредности. Можемо да направимо матрицу где за све вредности i и v чувамо све вредности k (листу вредности) и вредности одговарајућег dp стања.
Међутим, како вредности i и v могу бити до 1000, ова матрица ће користити превише меморије. Да би смањили меморију, можемо да приметимо да за неку вредности параметра i, вредност параметра v ће бити у интервалу [i-100,i+100] за сва поља чија је вредност у траженом интервалу. Тиме можемо да смањимо матрицу на димензије 1000\times 200.
Што се тиче, проналажења одговарајуће вредности за k из листе, довољно је само да прођемо кроз целу листу ако нам треба нека вредност из ње. Ово је могуће урадити и у О(\log{k}) али нема потребе како сложеност програма остаје иста.
Сложеност: Време: O(n^2\cdot k), Меморија: Број поља чија је вредност у интервалу (0,2^{61}).

Решење 2

У овом и следећем решењу решаваћемо упите офлајн, тј. решићемо их све једним пролазом кроз dp табелу у редоследу опадајућих дужина. За ово решење дефинисаћемо константу S и у одвојену табелу ћемо запамтити сваки S-ти ред, тј. dp[0][v][k], dp[S][v][k], dp[2\cdot S][v][k],…
Након тога, пролазимо кроз све дужине у опадајућем редоследу, и за сваку дужину i ћемо да добијемо ред који који нам треба, тј. dp[i][v][k] тако што ћемо кренути од најближег запамћеног реда, у овом случају то је dp[\lfloor\frac{i}{S}\rfloor\cdot S][v][k], и померити се i-\lfloor\frac{i}{S}\rfloor\cdot S корака до i-тог реда.
Одабир константе S=20 је довољно велик да решење прође меморијско ограничење, а довољно мали да прође временско ограничење.
Сложеност: Време: O(n^2\cdot k\cdot S), Меморија: O(\frac{n^2}{S}\cdot k).

Решење 3

Ово решење се своди на меморијску оптимизацију прве димензије dp табеле. Ако знамо све вредности за дужину i+1 и прва 2 реда за тренутну дужину тј. dp[i][0][k] и dp[i][1][k], можемо да израчунамо све вредности за дужину i. Ово је могуће урадити тако што конструишемо граф свих прелаза и ако знамо неку вредност у реду i, одузећемо ту вредност од свих стања (из реда i+1) са којима је то стање повезано, а ако имамо неко стање у реду i+1 које је повезано са тачно једним стањем (из реда i) за које не знамо вредност, можемо да закључимо која је вредност тог стања.
Како би ово радило, морамо да рачунамо вредности по модулу, модуо 2^{61} ради из истих разлога као у решењу 1. Сад нам још треба начин да кажемо да ли је вредност у неком пољу заправо већа од модула или не. За ово ћемо дефинисати вредност p=i+k-v, поље kada[p][k] ће нам чувати најмање i за које је неко стање dp[i][v][k] чија је вредност параметра p одговарајућа, постало веће од модула. Приметимо да кад једном постане веће од модула за неко i, вредност за свако веће i и истом вредношћу параметра p ће такође бити већа од модула.
Ово је све што нам треба да решимо проблем, решаваћемо уптите офлајн, прво израчунамо вредности у предоследу растућих дужина, попунимо табелу kada и сачувамо dp вредности за v=0 и v=1, и одговоримо на упите за које је решење “Ne postoji”. Након тога ћемо да израчунамо вредности у редоследу опадајућих дужина и одговоримо на остале упите.
Сложеност: Време: O(n^2\cdot k), Меморија: O(n\cdot k).