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

Шампион

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

Решење за T \leq 2\cdot X и 1 \leq X, T \leq 10^9:

Постоје само две могуће ситуације: ако важи T \leq X, онда ће Џонас неће морати да паузира и решење је T. Ако X< T \leq 2\cdot X, Џонас ће морати да направи једну паузу, па је решење у том случају T+Y.

Решење за 1 \leq X, T \leq 1000:

Можемо симулирати Џонасово играње, или минут по минут или у блоковима од X+Y минута. Ово решење је преспоро да би радило за 100 поена.

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

Приметимо да ће за сваких одиграних пуних X минута, Џонас паузирати Y минута. Таквих блокова ће бити \lfloor \frac{T}{X} \rfloor, где је \lfloor x \rfloor цео део од x. Онда ће решење бити \lfloor \frac{T}{X} \rfloor \cdot (X+Y) + T\%X, где је T\%X остатак при дељењу T са X (односно оно што му остане да одигра након последње паузе). Једини изузетак овој формули јесте ситуација када X дели Т. Тада нећемо имати паузу у последњем блоку, па је потребно да од претходне формуле одузмемо Y.

3 Likes

Гејм шоу

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

Решење за N\leq 20:

Можемо да фиксирамо по свих 2^n комбинација, на који циљ иде који тркач. Затим за сваку фазу видимо време које је потребно као максимум од две дистанце који тркачи треба да пређу.

Решење за a_i=b_i:

У овом случају обоје прате исту јединствену путању и ми немамо никакву одлуку да правимо. Само прођемо кроз низ дестинација и сумирамо дистанце суседних.

Комплетно решење

Оно што је кључно приметити у овом задатку је да су нама тркачи сасвим симетрични у свакој фази. У преводу није битно који је играч на a_i, а који на b_i, само да треба да стигну на позиције a_{i+1} и b_{i+1} у неком поретку. То значи заправо да у свакој фази трке имамо 2 могућности: оног на позицији a_i шаљемо на или позицију a_{i+1} или позицију b_{i+1}. За обе ове могућности можемо израчунати време потребно и само просумирати минимуме по свим фазама.

3 Likes

Карте 2

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

Решење за 1 \leq N \leq 1000:

Пошто је N мало, O(N^2) решење је довољно брзо. Можемо фиксирати колико првих карата узима Коца, освојивши P_1 поена (наравно, тако да P_1 \leq K). Након тога идемо кроз преостале карте и гледамо да ли је могуће изабрати неколико следећих карата са збиром бројева P_2 тако да P_1 < P_2 и P_2 \leq K. Ако је то немогуће, онда Коца сигурно побеђује ако извуче тај број карата.

Решење кад су све карте обележене истим бројем:

Означимо тај број са A. Дакле, ако Коца узме k карата, онда ће важити P_1 = k\cdot A. Како би његов противник освојио више од P_1 поена, мора узети више од k карата, односно макар k+1. Ако важи (k+1)\cdot A > K, онда ако узме више од k карата, пребациће границу. Самим тим нема победнички потез, па Коца увек побеђује (уколико k\cdot A \leq K). Ако ипак важи (k+1)\cdot A \leq K и његов противник заиста може да узме k+1 карата (остало је довољно карата у шпилу), онда противник има победничку стратегију и Коца не сме да узме k карата ако жели да победи (а жели).

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

Слично решењу кад 1 \leq N \leq 1000, фиксирамо колико првих карата узима Коца, освојивши P_1 поена. Сада треба да проверимо да ли постоји префикс преосталих карата тако да му је збир P_2 већи од P_1, а није већи од K. Пошто се на картама налазе искључиво позитивни бројеви, што више карата противник извуче, то ће збир бити већи. Нађимо користећи бинарну претрагу најмањи префикс остатка шпила чији је збир већи од P_1 (збир префикса можемо наћи користећи префиксне суме). Ниједан мањи префикс не може довести до победе противника, јер не задовољава услов P_1 < P_2. За тај префикс проверимо да ли је збир већи од K. Aко јесте, сви већи префикси су такође већи од K, па самим тим не постоји потез којим противник побеђује, па је одговор да. Ако му збир није већи од K, он задовољава оба услова, па је самим тим и победнички потез за противника. Онда морамо пробати следећи могућ Коцин потез, док не проверимо све могуће. Временска сложеност: O(NlogN), меморијска сложеност: O(N).

2 Likes

Питања

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

Дефинишимо са d_i = \frac{y_i - x_i}{k_i} + 1. У i-том упиту је потребно израчунати суму тачно d_i бројева.

Први подзадатак

Као помоћ потребно је користити формулу за суму првих n природних бројева \sum_{i=1}^{n} i= \frac{n\cdot(n+1)}{2}

Решење за i-ти упит можемо записати у обликз \sum_{j = 0}^{d_i -1} (x_i + j \cdot k_i) = \sum_{j = 0}^{d_i-1} x_i + k_i \cdot \sum_{j = 0}^{d_i-1} j = d_i \cdot x_i + k_i \cdot \frac{(d_i - 1)\cdot d_i}{2}. Последње написану формулу можемо израчунати у временској и меморијској сложености O(1) по упиту.

Други подзадатак

Поред формуле из првог подзадатка потребно је искористити формулу за суму првих n квадрата природних бројева \sum_{i=1}^{n} i^2= \frac{n \cdot(n+1) \cdot(2n+1)}{6}

На сличан начин можемо решити и други подзадатак, уз мало већу манипулацију са математичким формулама. Тако да решење можемо представити у облику \sum_{j = 0}^{d_i -1} (x_i + j\cdot k_i)^2 = \sum_{j = 0}^{d_i -1} (x_i^2 + 2\cdot x_i \cdot k_i \cdot j + (j\cdot k_i)^2) = = \sum_{j = 0}^{d_i -1} x_i^2 + 2\cdot x_i \cdot k_i \cdot \sum_{j = 0}^{d_i -1} j + k_i^2 \cdot \sum_{j = 0}^{d_i -1} j^2 = = d_i \cdot x_i^2 + 2 \cdot x_i \cdot k_i \cdot \frac{d_i\cdot (d_i - 1)}{2} + k_i^2 \cdot \frac{(d_i -1)\cdot d_i \cdot (2 \cdot d_i - 1)}{6}. Слично као и у првом подзадатку, наведени израз можемо израчунати у временској и меморијској сложености O(1) по упиту.

Трећи подзадатак:

У i-том упиту можемо проћи кроз свих d_i бројева и израчунати њихову суму. У најгорем случају за наш програм потребно је N итерација по упиту (на пример x_i=1, y_i=N, k_i=1). Временска сложеност описаног алгоритма је O(NQ).

Четврти подзадатак:

Алгоритам описан у трећем подзадатку је ефиксан за упите чија је вредност d_i релативно мала. Поставићемо границу B, и сваки упит за који важи d_i \leq B обрадићемо као и у трећем подзадатку. У случају d_i > B, вредност броја k не може бити већа од \frac{N}{B}. Направићемо матрицу D димензије \frac{N}{B} \times N, где вредност D[i][j] представља \sum A_x тако да важи x \mod i = j \mod i и x\leq j. Описану матрицу можемо израчунати у временској сложености O(\frac{N^2}{B}), слично поступку прерачунавања префиксних сума. Када израчунамо матрицу D одговор на упит (x_i, y_i, k_i), за који важи d_i > B можемо добити као D[k_i][y_i] - D[k_i][x_i] + A_{x_i} y временској сложености O(1). Коначан алгоритам који комбинује претходна два у зависности од вредности d_i има временску сложеност O(\frac{N^2}{B} + Q \cdot B) и меморијску O(\frac{N^2}{B}). Ако константу B поставимо на вредност B~\sqrt N добили смо алгоритам временске сложености O(N \sqrt N + Q \sqrt N) и меморијске O(N\sqrt N).

Приметити да меморијску сложеност алгоритма можемо побољшати ако упите за које важи d_i > B обрађујемо у групама по истој вредности k_i (нпр. прво обрадимо све упите за које важи k_i = 1, затим k_i = 2 итд). У овом случају је довољно памтити само један низ D који би се након сваке групе једнаких ресетовао на 0. Постоје и многи други начини оптимизације меморије на линеарну, међутим то се не захтева за максималан број бодова у задатку.

2 Likes

Новогодишње стабло

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

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

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

Скуп лепих чворова можемо одржавати на пример користећи бинарно претраживо стабло (односно set у C++). Такође се може користити сегментно стабло са лењом пропагацијом. За чување података о томе који чвор је које боје морамо користити сегментно стабло са лењом пропагацијом (или сличну структуру). Ово ћемо радити над ДФС обиласком стаблом, односно спљоштеним стаблом. Крајња временска сложеност је O(N+QlogN) или O((N+Q)logN)), у зависности од имплементације.

4 Likes

Zadatak Pitanja, drugi podzadatak…
Zar nije rešenje
\sum_{j = 0}^{d_i -1} (x_i + j \cdot k_i)^2 =
=\sum_{j = 0}^{d_i -1} (x_i^2 + 2\cdot x_i \cdot j \cdot k_i + j^2 \cdot k_i^2) =
=\sum_{j = 0}^{d_i -1} x_i^2 + 2\cdot x_i \cdot k_i \cdot \sum_{j = 0}^{d_i -1} j + k_i^2 \cdot \sum_{j = 0}^{d_i -1} j^2 =
= d_i \cdot x_i^2 + 2 \cdot x_i \cdot k_i \cdot \frac{d_i\cdot (d_i - 1)}{2} +k_i^2 \cdot \frac{(d_i -1)\cdot d_i \cdot (2 \cdot d_i - 1)}{6} ?

2 Likes

U pravu si, hvala na komentaru.

Dodato je rešenje petog zadatka.

Карте 2

Затак је могуће решити у временској сложености O(N):

Означимо са p_k индекс последње карте коју Коцин противник може да извуче а да збир карата које је извукао није већи од K ако је Коца извукао првих k карата, при чему је p_k=k ако противник не може да извуче ни једну карту.

Онда је или p_k=N или \displaystyle\sum_{i=k+1}^{p_k+1}A_i>K. Како су A_i позитивни бројеви, у другом случају је за свако p\ge p_k+1, \displaystyle\sum_{i=k}^{p}A_i\ge\displaystyle\sum_{i=k}^{p_k+1}A_i>\displaystyle\sum_{i=k+1}^{p_k+1}A_i>K, па је у оба случаја p_{k-1}\le p_k.

Дакле могуће је одредити све p_k у сложености O(N). Овим се и временска сложеност целог пробема смањује на O(N). Меморијска сложеност остаје O(N).

2 Likes