[Rešenja zadataka] 2021/2022 Okružno

Algoritam
1

Одбијање

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

Решење за 30 поена

Довољна је проста симулација овог кретања: док год куглица има апсолутну вредност своје позиције не већу од 100, свака секунда кретања се симулира. Води се рачуна о тренутној позицији x, времену од почетка t, брзини \mathit{dx} (која је или 1 или -1) и тренутку најскоријег судара T. У сваком кораку се ажурира позиција (x := x + \mathit{dx}) и провери да ли позиција одговара некој од препрека – а у том случају се ажурирају отпорност препреке, брзина и време најскоријег судара. Ово решење даје тачан одговор у временској сложености O(N \cdot \max_i S_i \cdot \max_i |X_i|).

Решење за 50 поена

Реч је о једноставној оптимизација претходног приступа. Уместо да се у сваком кораку позиција промени за 1, довољно је водити рачуна о наредној удареној препреци са леве и са десне стране. Време између два судара је тада једнако апсолутној вредности разлике између позиција те две препреке. Најпре треба поделити препреке у два низа: препреке са негативном позицијом и препреке са позитивном позицијом. У та два низа се затим одреде препреке најближе куглици и врши се симулација кретања. Када отпорност неке препреке постане једнака нули, тада се та препрека означи као непостојећа и бира се најближа препрека са ненултом отпорности. Временска сложеност овог приступа је O(N \cdot \max_i S_i \cdot \max_i |X_i|).

Решења за 70 и 100 поена

Ова два решења су малтене идентична и разликују се по томе што користе различите алгоритме сортирања: O(N^2) временске сложености и O(N \log N) временске сложености. Најпре се, као у претходном решењу, раздвоје низови препрека лево од нуле и препрека десно од нуле. Затим се ти низови сортирају по апсолутној вредности позиције и тако се одређује редослед којим се куглица судара са препрекама. Да ли је последње одбијање са неким левим зидом или десним зидом се одређује поређењем укупних отпорности десних зидова и левих зидова:

  • ако је укупна отпорност десних зидова r мања или једнака укупној отпорности левих l, тада са леве стране имамо l одбијања, а са десне l+1 одбијање;
  • у супротном, са леве стране и десне стране имамо по r одбијања.
    На основу укупног броја одбијања са обе стране је могуће одредити за сваку “деоницу” (простор између две узастопне препреке) колико је пута пређена. На пример, ако је дошло до m одбијања са леве стране, тада је прва деоница (од 0 до првог зида) пређена 2m пута, друга 2(m-\mathit{otp\_levih}[0]) пута итд, докле год преостали број одбијања не постане негативан. Неопходно је посветити пажњу последњем судару и одузети 1 од броја прелазака последње деонице.
2 Likes
2

Штале

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

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

Квадратно решење за 65 поена

Довољно је у две угнежђене петље проћи по свим шталама и испитати да ли је могуће доћи од једне до друге, рачунајући да се од i-те до j-те штале (наравно, само за индексе i \neq j) може доћи ако им се поклапају хоризонталне (x) или вертикалне (y) координате или се пак поклапа разлика или збир вертикалних и хоризоналних координата (то јест налазе се дијагонално/антидијагонално једна од друге), при чему се 4 поменутих једнакости (једнаке вредности x, y, x-y, x+y) рачунају по модулу c уз услов да модуо буде позитиван. Како се у свакој од две петље пролази кроз све штале и чува максимум, ово решење има квадратну временску сложеност, односно \mathcal{O}(n^2), где n представља број штала.

Главно решење у линеарној сложености

Да би се задатак урадио на ефикасан начин, сврсисходно је макар привидно пресликати дводимензионалну раван (x, y) на матрицу димензија c \times с. Пресликавање се врши тако што се поље у i-тој врсти и j-ој колони поменуте матрице попуњава са онолико штала колико их се налази на координатама x \mod c = i и y \mod c = j. Све што је тада потребно учинити јесте пронаћи поље у матрици са највећим збиром осталих елемената који се налазе у истој врсти и колони, као и на истој дијагонали и антидијагонали, тачније сам збир поменутих елемената са тренутним пољем који заправо представља тражено решење задатка. Приликом проласка кроз матрицу треба бити пажљив и обратити пажњу да се само поље кроз које се пролази не урачуна више пута, као и то да се, за парно c, поља на (продуженој) дијагонали и антидијагонали могу поклапати, односно да се (продужене) дијагонале могу сећи. Како је сама операција пресликавања равни на матрицу линеарна по n, то јест \mathcal{O}(n), а пролазак кроз матрицу у општем случају квадратан по њеним димензијама, прецизније \mathcal{O}(c^2), јасно је из поставке задатка у којој се каже да је n\leq200'000, а c\leq100, па је n>c^2, први члан доминантан, те је и укупна временска сложеност решења, под оваквим претпоставкама, линеарна по броју штала.

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

Како је услов да се из тачке (x_1,y_1) тачка (x_2, y_2) може обићи: x_1 = x_2 \lor y_1 = y_2 \lor x_1-y_1 = x_2-y_2 \lor x_1+y_1 = x_2+y_2, где је једнакост по модулу c, то можемо за сваку тачку тражити број тачака за који важи овај услов као број елемената уније 4 скупа (скуп свих са одређеном x или y координатом, или одређеном разликом/збиром двеју координата). Ово се може решити формулом укључења-искључења за 4 скупа, где величине пресека бројимо вишедимензионалним матрицама (укупна меморијска сложеност је \mathcal{O}(c^4), што је у пракси и доста мање од 512 МБ, док је временска линеарна јер сваку шталу убацујемо у константан број скупова који служе за пребројавање).

1 Like
3

Окрам

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

Решење када N, M \leq 5, A_i \leq 1

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

Решење када K \leq 5

Пошто је K \leq 5, значи да нам је битно само понашање матрице у првих 2^5 = 32 секунди. Пре свих питања, израчунаћемо све матрице, и онда за свако питање можемо само исписати тражено поље одговарајуће матрице.

Временска сложеност је O(2^KNM + Q), а меморијска О(2^KNM).

Решење када K \leq 200

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

Решење када су све почетне вредности 0, сем једне која је 1

Посматрањем како се ова јединица понаша кроз време у бесконачној матрици можемо закључити да ће након 2^K секунди да се налази на позицијама (x+2^K, y), (x-2^K, y), (x, y+2^K) и (x, y-2^K). Ово можемо и једноставно доказати индукцијом. За базу K = 0 ово је очигледно тачно. Ако претпоставимо да је тачно за неко K, и применимо индуктивну хипотезу на 4 тако добијене тачке, видећемо да се дешава нешто занимљиво - сва поља сем она 4 која су нам потребна се скрате (xor је инверз сам себи), па смо доказали тврђење.

Сада, за свако питање је довољно проверити да ли је у питању једно од највише четири поља који садрже јединицу. Пошто ова матрица није бесконачна, морамо користећи формуле да добијемо тачне координате јединица у њој.

Временска сложеност је O(NM+M+K), а меморијска O(NM+K).

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

Приметимо да ће сва поља у матрици бити xor неких поља почетне матрице. Користећи претходно решење, за свако поље почетне матрице можемо пронаћи у xor-у којих поља матрице ће се налазити након 2^K секунди. Тако можемо закључити да ће вредност поља (x, y) након 2^K секунди бити xor вредности поља (x+2^K, y), (x-2^K, y), (x, y+2^K) и (x, y-2^K) у почетној матрици.

Временска сложеност је O(NM+M+K), а меморијска O(NM+K). матрици.

1 Like
4

Сличице

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

За почетак одредимо које карте Јаков може скупити, а које не може.

Јаков може скупити карту са било којим парним бројем, јер је највећи заједнички делилац за 2 (Јаков има на располагању произвољно много карти са бројем 2) и тог парног броја једнак 2 што је веће од 1.

Јаков може скупити и карте са непарним бројевима p не већим од \lfloor\frac{n}{2}\rfloor (наравно, већим од 1), јер прво може карту са бројем 2 разменити за карту са бројем 2p, а након тога карту са бројем 2p за карту са бројем p.

На крају може скупити и карте са било којим сложеним непарним бројем m из интервала \left[\lceil\frac{n}{2}\rceil,n\right]. Сваки такав непаран сложен број има бар један прост фактор p\leq \sqrt{m} \leq \sqrt{n} \leq \lfloor\frac{n}{2}\rfloor. Због тога карту са бројем 2 може разменити за карту са бројем 2p\leq n, затим карту са бројем 2p за карту са бројем p и на крају карту са бројем p за карту са бројем m.

Јаков не може скупити карте са непарним простим бројем p већим од \lfloor\frac{n}{2}\rfloor. Да би скупио ту карту морао би да има карту са бројем дељивим са бројем p. Али најмањи број (различит од p) који је дељив бројем p је 2p који је већи од n.

Због тога је број карти које Јаков може скупити једнак разлици бројева n-1 (број бројева већих од 1, али мањих од или једнаких n) и броја простих бројева већих од \lfloor\frac{n}{2}\rfloor и мањих од или једнаких n.

Решење кад је N \leq 10

Све карте које може скупити Јаков се могу одредити варијацијом претраге у ширину.

Решење кад је N, Q \leq 200, N, Q \leq 2000

За сваки упит се одређује број простих бројева у интервалу \left[\lfloor\frac{n}{2}\rfloor+1,n\right].

Решење кад је N \leq 100.000

Непосредно након учитавања вредности броја N за све упите, одређује се највећа вредност за N (нека је то N_{\max}), а након тога за сваку вредност N \leq N_{\max} број простих бројева који нису већи од N (означимо тај број са p(N)). Вредност p(N) се одређује на основу вредности p(N-1). Наиме, вредност p(N) је једнака p(N-1)+1, ако је N прост број, односно p(N-1), ако је N сложен број. Провера да ли је број N прост се може извести у сложености O(\sqrt{N}), па је сложеност одређивање свих вредности p(N) једнака O(N_{\max}\sqrt{N_{\max}}).
Након тога се број простих бројева у интервалу \left[\lfloor\frac{n}{2}\rfloor+1,n\right] одређује по формули p(N)-p\left(\frac{N}{2}\right), тј. у сложености O(1). Сложеност комплетног алгоритма је O(N_{\max}\sqrt{N_{\max}}+Q).

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

Непосредно након учитавања вредности броја N за све упите, одређује се највећа вредност за N (нека је то N_{\max}), а након тога за сваку вредност N \leq N_{\max} број простих бројева који нису већи од N (означимо тај број са p(N)). За разлику од претходног подзадатка, провера да ли су природни бројеви прости се изводи применом Ератостеновог сита. Захваљујући томе, сложеност израчунавања свих вредности p(N) је O(N_{\max}\log N_{\max}), а сложеност комплетног решења је O(N_{\max}\log N_{\max} + Q).

1 Like
5

Ћивас

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

Решење када N, Q \leq 500

За сваку промену низа, израчунамо низ b и на њему пробамо сваку могућу периоду, од којих узимамо најмању.

Временска сложеност је O(QN^2), а меморијска сложеност O(N).

Решење када Q \leq 25

Приметимо да су једине могуће периоде делиоци броја N. Сада примењујемо претходно решење, само што испробавамо само те делиоце.

Временска сложеност је О(QNd(N)), где је d(N) број делиоца N, а меморијска сложеност O(N).

Решење када Q \leq 3000

Можемо приметити да за свако d и x важи:

a_i \text{ xor } a_{i+d} = b_i \text{ xor } b_{i+1} \text{ xor } \ldots \text{ xor } b_{i+d-1}

Аналогно, важи и:

a_{i+d} \text{ xor } a_{i+2d} = b_{i+d} \text{ xor } b_{i+d+1} \text{ xor } \ldots \text{ xor } b_{i+2d-1}

Ако за d узмемо периоду низа b, важи да су десне стране ових једначина једнаке, па важи и да су леве стране једнаке. Одатле закључујемо, да за такво d и произвољно x важи a_i = a_{i+2d}, што нам говори да је 2d периода низа a.

Пошто нам је познато да је периода низа a баш n, онда имамо два случаја. Уколико је n непарно, периода низа b је увек n, у супротном, периода може бити и \frac{N}{2}, а ако није, онда мора бити n. Зато, након сваке промене, довољно је проверити да ли је у новом низу \frac{N}{2} периода.

Временска сложеност O(NQ), а меморијска сложеност O(N).

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

Попут претходног решења, довољно је проверити периоду \frac{N}{2}, само ћемо овде то урадити на бржи начин. Пре свих промена, одрадимо проверу у O(N), памтећи у колико одговарајућих парова су исти елементи. Након сваке промене, довољно је проверити само да ли се неки од два пара на које промена утиче поправио или покварио, тј. ажурирати број парова у којима су елементи исти. Кад год је број таквих парова тачно \frac{N}{2}, периода је \frac{N}{2}, у супротном, периода је N.

Временска сложеност је O(N+Q), а меморијска сложеност O(N).

1 Like
6

AdVenture Communist

Аутор: Игор Павловић
Текст и тест примери: Игор Павловић
Анализа решења: Игор Павловић
Тестирање: Тадија Шебез

Решење за N, T \leq 2000

Овде је довољно симулирати дешавања тренутак по тренутак у сложености O(NT).

Решење за N\leq 200

У овом случају је потребно приметити да је описана рекурента веза заправо линеарна трансформација која се може представити у матричном облику kao

A(t+1)=K \cdot A(t)

gde је

A(t) = [a_0(t), a_1(t), ..., a_n(t)]^T
K_{i,i} = C \text{ , } K_{i,i+1} = (i+1) \cdot K_{i+1}
K_{ij}=0 \text{ за } (j!=i) \wedge (j!=i+1)

Одавде се добија следећа једнакост:

A(t)=K^t \cdot A(0)

из које можемо одредити вредност a_0(T) у сложености O(N^3\log T) брзим степеновањем матрица.

Решење за C = 1

Приметимо прво да се допринос сваке појединаче фабрике може посматрати одвојено од осталих зато што је описана трансформација линеарна. Укупан број кромпира у тренутку T добијамо као збир доприноса сваке фабрике.

За трансформацију

a_i(t+1)=a_i(t)+(i+1) \cdot K_{i+1} \cdot a_{i+1}(t)

се може индукцијом доказати да је допринос i-те фабрике укупном броју кромпира након t секунди заправо:

d_i = \prod_{j=1}^{i} K_j \cdot (t-j+1)

Сумирањем свих доприноса добијамо:

a_0(T) = a_0(0) + \sum_{i=1}^{N} a_i(0) \cdot d_i = a_0(0) + \sum_{i=1}^{N} a_i(0) \cdot \prod_{j=1}^{i} K_j \cdot (T-j+1)

На основу овог израза можемо одредити a_0(T) у сложености O(N).

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

Приметимо да се задата рекурентна веза може записати као:

a_i(t+1)=C \cdot a_i(t)+(i+1) \cdot K_{i+1} \cdot a_{i+1}(t)= C \cdot (a_i(t)+(i+1) \cdot \frac{K_{i+1}}{C} \cdot a_{i+1}(t))

У матричном облику ова рекурентна веза може се записати као композиција две линеарне трансформације на следећи начин:

A(t+1)=C \cdot I \cdot K' \cdot A(t)

gde је

A(t) = [a_0(t), a_1(t), ..., a_n(t)]^T
K_{i,i} = 1 \text{ , } K_{i,i+1} = (i+1) \cdot \frac{K_{i+1}}{C}
K_{ij}=0 \text{ за } (j!=i) \wedge (j!=i+1)

и матрица I је јединична матрица.

Одавде се добија следећа једнакост:

A(t)=C^t \cdot K'^{t} \cdot A(0)

Пошто је матрица K' иста као у случају када је C=1 можемо закључити да је допринос i-те фабрике:

d_i = C^t \prod_{j=1}^{i} \frac{K_j}{C} \cdot (t-j+1) = C^{t-i} \cdot \prod_{j=1}^{i} K_j \cdot (t-j+1)

Сумирањем свих доприноса добијамо:

a_0(T) = a_0(0) + \sum_{i=1}^{N} a_i(0) \cdot d_i = a_0(0) + \sum_{i=1}^{N} a_i(0) \cdot C^{T-i} \cdot \prod_{j=1}^{i} K_j \cdot (T-j+1)

На основу овог израза можемо одредити a_0(T) у сложености O(N).

1 Like
7

Овде се може смањити меморијска сложеност на О(1) уз конвенцију да не рачунамо улазне податке (у нашем случају низ а). Идеја се заснива на суми са екслузивним или и рачунању елемената низа б преко функције. Временска сложеност остаје иста. Мислим да ће све бити јасније уз приложено решење у C++ 14.

#include <iostream>
using namespace std;


const size_t N = 200000;
int a[N];

int main() {
    ios_base::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    int polovina = n >> 1;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    // Nalazi n (mod m) kao što je uobičajeno u matematici.
    // Izvor: https://stackoverflow.com/a/1907585
    auto mod = [](long n, long m) {
        return ((n % m) + m) % m;
    };

    // Nalazi vrednost b[i] na osnovu niza a.
    auto b = [&](int i) {
        return a[mod(i, n)] ^ a[mod(i + 1, n)];
    };

    int xor_suma = n % 2;
    for (int i = 0; i < polovina; i++)
        xor_suma += b(i) ^ b(i + polovina);

    if (xor_suma == 0)
        cout << polovina;
    else
        cout << n;
    cout << endl;

    while (q--) {
        int p, v;
        cin >> p >> v;
        p--;

        xor_suma -= b(p - 1) ^ b(p - 1 + polovina);
        xor_suma -= b(p) ^ b(p + polovina);
        a[p] = v;
        xor_suma += b(p - 1) ^ b(p - 1 + polovina);
        xor_suma += b(p) ^ b(p + polovina);

        if (xor_suma == 0)
            cout << polovina;
        else
            cout << n;
        cout << endl;
    }

    return 0;
}