Послован човек
Ускоро!
Архитекта
Аутор: Алекса Милисављевић
Текст и тест примери: Алекса Милисављевић
Тестирање: Алекса Плавшић
Анализа решења: Младен Пузић
Решење када M = N-1
У овом подзадатку морамо одабрати све путеви да бисмо конструисали одговарајући план. Нађимо битовску дисјункцију цена свих грана. Временска и меморијска сложеност је O(N).
Решење када скуп путева прави циклус
У овом подзадатку, морамо одабрати све путеве сем једног, где можемо било који изоставити. Можемо пребацити овај граф у низ дужине N, где чувамо цене путева редом. Да бисмо ефикасно нашли битовску дисјункцију свих путева сем једног, чуваћемо префиксну и суфиксну битовску дисјункцију тог низа. Решење је онда битовска дисјункција одговарајућег префикса и суфикса. Од свих могућих опција, бирамо ону која даје најјефтинији план. Временска и меморијска сложеност је O(N).
Решење када 0 \leq w_i \leq 1
Битовска дисјункција бројева из скупа \{0, 1\} може бити 0 само ако су сви бројеви 0. У супротном она је 1. Зато, проверимо да ли када узмемо све путеве цене 0 добијемо државу у којој је сваки град повезан са сваким другим. Уколико да, решење је 0, у супротном, решење је 1. Ово можемо проверити на пример DFS алгоритмом. Временска и меморијска сложеност је O(N+M).
Решење када 1 \leq M, w_i \leq 10^3
Пошто су цене путева до 1000, онда је највећи могући резултат 1023. Проверићемо све могуће укупне цене једну по једну од најмање ка највећој. Рецимо да проверавамо резултат x. Прођимо редом кроз све гране и додајмо само оне које можемо, тако да x остане могућ резултат. У овом случају, то значи да ни на једној позицији у бинарном запису нема цифру 1, а да је у броју x та цифра 0. Када додамо све те гране, као у претходном подзадатку проверимо да ли је могуће стићи од сваког града до сваког другог користећи те гране. Ако да, и то је најмање такво x, то је решење. Временска сложеност је O(M\cdot \max(w_i)), а меморијска O(N+M).
Главно решење
Уместо да фиксирамо могући резултат као у претходном задатку, градићемо резултат бит по бит, кренувши од највреднијег бита. Пошто важи да је 2^{0} + 2^{1} + \ldots + 2^{i} \leq 2^{i+1}, у интересу нам је да највреднији бит буде што мањи. Покушајмо прво да избегнемо највреднији бит. Додајмо све гране у чијим тежинама је та цифра 0. Уколико можемо да направимо план само са тим гранама, стављамо 0 на ту цифру резултата, а избацујемо из скупа грана све гране чијој цени је та цифра 1, јер су непотребне. Уколико не можемо, онда стављамо 1 на ту цифру, али одржавамо исти скуп грана (неопходне су нам обе врсте). У оба случаја, прелазимо на следећи бит на исти начин. На крају, имаћемо конструисани резултат. Временска сложеност је O(M\log(w_i)), а меморијска O(N+M).
1 Like
Заграде
Аутор: Павле Мартиновић
Текст и тест примери: Павле Мартиновић
Тестирање: Алекса Милисављевић
Анализа решења: Младен Пузић
Решење када N, Q \leq 500
Након сваке промене, пребацујмо једну по једну заграду са почетка на крај, док не наиђемо на први пут када имамо валидан низ заграда. Решење је број пребачених заграда. Проверавамо да ли је низ заграда валидан тако што идемо слева надесно и одржавамо број неупарених отворених заграда. Уколико наиђемо на отворену заграду, повећавамо тај број. Уколико наиђемо на затворену заграду, а број неупарених отворених заграда је већи од 0, онда упарујемо једну отворену заграду са том затвореном заградом, па смањујемо тај број. Уколико немамо неупарених отворених заграда, а наиђемо на затворену заграду, низ заграда није валидан. Он такође није валидан ако завршимо процес са неупареним отвореним заградама. Временска сложеност је O(QN^2), а меморијска O(N).
Решење када N, Q \leq 5000
У овом подзадатку ћемо применити сваку промену и покушати да нађемо решење у O(N). Посматрајмо следећи низ:
p_0 = 0
p_i = \begin{cases}
p_{i-1} + 1, & i\text{-та заграда је отворена} \\
p_{i-1} - 1, & i\text{-та заграда је затворена}
\end{cases}
Приметимо да је услов да низ заграда буде валидан да важи p_i \leq 0 за свако 1 \leq i \leq N и p_N = 0 (ово је еквивалентно томе да ниједан префикс нема више затворених него отворених заграда и да укупно имамо једнако отворених и затворених заграда).
Посматрајмо сад шта се деси када првих i заграда пребацимо на крај. Можемо приметити да ће се првих i елемената низа p_i пребацити на крај и онда ће се цео низ повећати за -p_i. Пошто желимо да сви елементи буду већи или једнаки 0, онда морамо да га повећамо за што више, што значи да ћемо узети што мање p_i. Дакле, решење је i за које је p_i најмање. Уколико има изједначења, онда узимамо најмање такво i. Након сваке промене само поново израчунамо низ p_i. Временска сложеност је O(QN), а меморијска O(N).
Решење када све промене мењају затворене заграде у отворене
Приметимо да, како би низ заграда био валидан, морамо имати једнак број отворених и затворених заграда. Рецимо да на почетку имамо l отворених, а r затворених заграда. Уколико r < l онда очигледно никад не можемо добити валидан низ заграда. У супротном, моћи ћемо да имамо валидан низ заграда само након што \frac{r-l}{2} затворених заграда претворимо у отворене. Уколико \frac{r-l}{2} > Q, онда опет никад нећемо имати решење. У супротном, довољно је да применимо решење из претходног подзадатка након \frac{r-l}{2} промена (сви остали резултати су -1). Временска сложеност је O(N+Q), а меморијска O(N).
Главно решење
Овај подзадатак се ради слично као други подзадатак, само због ефикасне промене низа p_i потребно је да одржавамо сегментно стабло са лењом пропагацијом над њим. Промена која је потребна је додавање +1 или -1 на неки суфикс, и налажење минимума целог низа. Да бисмо узели најлевљи минимум целог низа, сегментно стабло градимо над низом парова \{p_i, i\}, па ћемо упитом минимума добити онај пар са најмањим p_i, а најмањим индексом у случају изједначења. Временска сложеност је O(Q\log N), а меморијска O(N).
1 Like
Послован човек
Аутор: Павле Мартиновић
Текст и тест примери: Алекса Плавшић
Тестирање: Павле Мартиновић
Анализа решења: Младен Пузић
Решење када N \leq 20
Пошто за сваки дан постоји две могућности, отићи на први или други посао, укупно постоји 2^N могућности. Можемо пробати сваку могућност, симулирати зараду новца и одабрати оптимални одабир послова.
Временска сложеност је O(N\cdot 2^N), а меморијска O(N).
Решење када C = 0
Пошто је од почетка испунио квоту за дуплирану плату на другом послу, потребно је i-тог дана отићи на први посао уколико је A \leq 2\cdot B_i, у супротном отићи на други посао.
Временска и меморијска сложеност је O(N).
Решење када B_i = B_j
Пошто је плата на другом послу иста сваког дана, назовимо је B. Фиксирајмо k као први дан када је испуњена квота (први дан кад би плата на другом послу била 2\cdot B), испробајмо све бројеве од 1 до N, тим редом.
Како би дан k био први кад је плата дуплирана, потребно је да Хуан у првих k-1 дана тачно \lceil \frac{C}{B} \rceil дана оде на други посао (уколико \lceil \frac{C}{B} \rceil > k-1, та вредност за k није могућа). Самим тим резултат за фиксно k jе \lceil \frac{C}{B} \rceil \cdot B + (k-1-\lceil \frac{C}{B} \rceil) \cdot A + (N-k+1) \cdot \max(A, 2\cdot B), што се може лако израчунати.
Временска и меморијска сложеност је O(N).
Решење када B_i \leq B_{i+1}
Слично претходном решењу, фиксирајмо k. У првих k-1 дана, на други посао ће сигурно отићи када важи B_i \geq A. Уколико са тим данима није испунио квоту, потребно је да на други посао оде још неколико дана док не испуни квоту, увек идући данима када је највеће B_i. Пошто му се већ не исплати, жели да што мање дана потроши на то.
Пошто је низ B неопадајући, можемо приметити да ће за неко 0 \leq t_1 \leq k-1 првих t_1 дана отићи на први посао, а данима [t_1+1, k-1] отићи на други посао.
Сем тога, постоји неко k \leq t_2 \leq N, такво да се данима [t_2, N] више исплати отићи на други посао (ако k-тог дана испунимо квоту). Дакле, резултат за фиксно k је:
t_1 \cdot A +\sum_{i = t_1+1}^{k-1} B_i + (t_2-k)\cdot A + 2\cdot \sum_{i = t_2}^{N} B_i
Бројеве t_1 и t_2 можемо наћи бинарном претрагом, док резултат можемо ефикасно израчунати префиксном сумом над низом B. Поново морамо пазити да је могуће да нам фиксирана вредност може бити k.
Временска сложеност је O(NlogN), а меморијска O(N).
Решење када N, A, C, B_i \leq 2000
Ово решење је веома слично претходном - пошто је N мало, за свако k можемо изнова сортирати низ B на интервалима [1, k-1] и [k, N] и применити претходно решење.
Временска сложеност је O(N^2logN), а меморијска O(N).
Главно решење
Поново фиксирамо k и идемо слева надесно, одвојено решавамо интервале [1, k-1] и [k, N]. За десни интервал, једноставно ћемо израчунати суфиксне суме suf_i = suf_{i+1} + \max(A, 2\cdot B_j) које ћемо касније користити у крајњем решењу.
Што се тиче левог интервала, споменули смо да постоје они дани када се Хуану увек исплати да оде на други посао (B_i \geq A) и они кад иде на други посао само како би испунио квоту. За први тип, довољно је одржавати њихову суму Bsum како мењамо k. За други тип је компликованије, јер може да се деси да за једно k оде на други посао, а за следеће k истог дана оде на први посао.
Зато ћемо одржавати мин хип (priority_queue) са највећим вредностима B који нису првог типа (дакле, за које важи B_i < A). Чуваћемо у њему све вредности које су нам потребне да, заједно са данима првог типа, испуни квоту. Назовимо суму елемената у хипу Hsum. Одржавамо хип тако да у њему имамо што мање елемената, а важи Bsum + Hsum \geq C. Када се k премести са i-1 на i, уколико је B_i \leq A онда увећавамо Bsum и потенцијално бришемо неке најмање елементе из хипа, уколико нам више нису потребни, смањујући Hsum. Уколико важи B_i < A, онда ћемо прво додати B_i у хип и повећати Hsum, а онда потенцијално обрисати најмање елементе који су вишак (то може бити и елемент који смо управо додали) и смањујемо Hsum.
Резултат за фиксно k је онда Hsum + Bsum + suf_i.
Временска сложеност је O(NlogN), а меморијска O(N).