[Rešenja zadataka] Okružno 2020

Algoritam
1

Премештања

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

Анализа

Означимо са R_i редни број ученика који седи за рачунаром i. На почетку је R_i = i за свако i = 1, 2, \ldots, N. У сваком премештању ми практично мењамо места два елемента низа R и након сваког премештања желимо да проверимо да ли постоји неки индекс i за који важи |i - R_i| > K.

Поменуту проверу можемо урадити праволинијски: у сваком од M корака заменимо два елемента низа а затим прођемо кроз цео низ и упоредимо |i - R_i| и K. Сложеност овог алгоритма је O(NM) и решава подзадатак 1 (20-30 поена) али је превише спор за остале подзадатке.

Приметимо да када вршимо проверу након i премештања, за све индексе j који нису учествовали у првих i премештања важи R_j = j; дакле, не морамо проверавати цео низ већ (у i-том кораку) само индексе из првих i премештања (А_1, B_1, A_2, B_2, \ldots, A_i, B_i; међу њима може бити истих). Ово даје алгоритам сложености О(M^2) што је довољно за прва два подзадатка (40-50 поена).

У трећем подзадатку важи K = N - 3. Међутим, једини индекси i за које је могуће да важи |i - R_i| < N - 3 су 1, 2, N-1 и N (остали се не могу довољно “удаљити”; проверити!) па је након сваке замене довољно проверити вредности R_1, R_2, R_{N-1} и R_N што нам даје укупну сложеност O(N+M) и решава овај подзадатак (20 поена).

Да бисмо решили цео задатак, приметимо да није неопходно стално проверавати пуно индекса већ је довољно да у сваком тренутку памтимо колико има индекса i за које важи |i - R_i| > K; означимо ту количину са x (на почетку је x = 0). Поменути индекс постоји акко је x > 0. Заменом два елемента низа вредност x се може променити највише за 2 и разликовањем неколико случајева лако “update”-ујемо x (нпр. ако је |A_i - R_{A_i}| \leq K и |B_i - R_{B_i}| > K, а |A_i - R_{B_i}| > K и |B_i - R_{A_i}| > K, тада се након i-тог премештања x повећава за 1, итд.) . Сложеност овог решења је O(N+M) и осваја свих 100 поена.

1 Like
2

Заборављена Партија

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

Анализа

За почетак, треба одредити да ли је уопште могуће генерисати таблу
каква се тражи у задатку. Уколико Т < 2K-1, очигледно није, јер ни
један играч неће стићи да постави K симбола неопходних за победу. У
супротном, решење увек постоји (што ће бити јасно из алгоритма који га
генерише), осим уколико је K = 2 и T > N \cdot \lceil \frac{N}{2} \rceil + 1. Да би доказали да у овом случају нема решења, можемо
поделити таблу на 2 \times 2 квадрате и приметити да пре последњег
потеза у сваком од њих може бити највише један X и један O.

Решење за произвољно T можемо направити од решења где T = N^2 (X
побеђује у последњем потезу), односно T = N \cdot \lceil \frac{N}{2} \rceil + 1 ако K = 2, на следећи начин:

  • уколико је T парно (O треба да победи), заменимо све X са O
    и обрнуто,
  • израчунамо колико ће X и O бити на табли после T потеза, и
  • бришемо симболе док не остане очекиван број, водећи рачуна да не
    обришемо ниједан из низа од K узастопних због ког је један од
    играча победио.

Остаје само да конструишемо такво решење. Ово ћемо урадити одвојено за
три случаја: K = 2, K = 3 и K > 3

K = 2

Таблу можемо попунити на следећи начин (наизменични X и O) у
сваком другом реду (пример за N = 7):

XOXOXOX
*......
OXOXOXO
.......
XOXOXOX
.......
OXOXOXO

Играч који игра последњи потез игра на поље обележено са *.

K = 3

Почећемо од табле на којој ни један играч не побеђује:

xOXOXOX
XoXOXOX
OXOXOXO
OXOXOXO
XOXOXOX
XOXOXOX
OXOXOXO

Приметимо да, уколико заменимо поља (1,1) и (2,2) (обележена малим
словима), добијамо таблу на којој X побеђује у последњем потезу ако
“за крај” остави (2, 2).

K > 3

Слично као за K = 3, почећемо од табле у којој нико не побеђује,
коју конструишемо на следећи начин:

  • У првом реду имамо K-1 симбола X, затим један O, па опет K-1
    X, и тако даље.
  • Други ред је исти, са замењеним X и O.
  • Даље редове правимо наизменичним понављањем ова два.
  • Уколико је N непарно, да би имали очекивани број X и O,
    последњи ред чине наизменични X и O.

На пример, за N = 7, K = 5:

XXXXoxX
OOOOXOO
XXXXOXX
OOOOXOO
XXXXOXX
OOOOXOO
XOXOXOX

Слично као у прошлом случају, можемо заменити први O са X који се
налази после њега и добити позицију у којој X “чува” потез (1, K)
за крај и побеђује у последњем потезу.

Уколико N = K, не можемо заменити ова два симбола (јер нема ничег
десно од тог O). У овом случају, није тешко видети да уместо тога
можемо заменити први O са пољем (3, 1).

3

Чаробњак из Воза

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

Анализа

Намеће да ће чаробњаци потрошити мање времена на успављивање Јетија ако користе више снаге. Поред тога, без обзира што се специјална магија користи на крају (после бацања обичних чаролија), можемо већ на почетку “урачунати” специјалну магију (ако је већа од обичне магије).
Због тога формирамо низ са свим могућим чаролијама и магијама. Наиме, ако су S_i и M_i почетна јачина обичне чаролије и јачина специјалне магије чаробњака број i, онда у низ a са свим (могућим) магијама додајемо следеће јачине:

M_i, S_i, \frac{S_i}{2^1}, \frac{S_i}{2^2}, \frac{S_i}{2^3}, ..., \frac{S_i}{2^k},

где је k број са особином да је

\frac{S_i}{2^k}\geqslant 1 \ \ \ \ \text{и}\ \ \ \ \ \frac{S_i}{2^{k+1}} < 1.

По формирању низа a, соритрамо га у нерастућем поретку, а затим одређујемо најмањи број m такав да је

a_1 + a_2 + a_3 + \dotsb + a_m \geqslant E.

Како су јачине свих моћи мање од или једнаке броју 10^6, елементи низа a ће бити између 1 и 10^6, па се тај низ може сортирати применом сортирања пребрајањем (counting sort). Ако највећу вредносту у низу а обележимо са K, дужина низа ће бити највише N\log K, док ће сложеност сортирања ће бити О(\max\{ N\log K, K\}) . Одређивање броја m који представља број дана потребних да се успава Јети се може урадити у сложености О(K) или О(N\log K) проласком кроз сортиран низ. Коначна сложеност решења ће бити иста као и сложеност сортирања.

4

Добитни Листић

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

Анализа

Означимо са nzd(a,b) највећи број који дели и a и b, а са nzs(a,b) најмањи број којег деле и a и b. Приметимо да је једино ограничење на L_{1} и L_{N} да их A_{1} и A_{N-1} деле редом. Даље, приметимо да за сваки број L_{i}, 1 < i < N важи A_{i-1} | L_{i} и A_{i} | L_{i}, тј. nzs(A_{i-1},A_{i}) | L_{i} . Посматрајмо низ:

K_{1} = A_1, K_{2} = nzs(A_{1},A_{2}),...,K_{i}=nzs(A_{i-1},A_{i}),...,K_{N-1}=nzs(A_{N-2},A_{N-1}),K_{N}=A_{N-1}

Приметимо да за овакав низ K_{i} важи да A_{i} | K_{i} и A_{i} | K_{i+1}, тј. A_{i} | nzd(K_{i},K_{i+1}). Приметимо, такође, да за сваки низ M_{i} који испуњава ограничења важи да:

K_{i} | M_{i}, 1 \leq i \leq N

Због тога, важи да nzd(K_{i},K_{i+1}​) ∣ nzd(M_{i},M_{i+1}), тј. A_{i} \leq nzd(K_{i},K_{i+1}) \leq nzd(M_{i},M_{i+1}). Дакле довољно је проверити да ли низ K_{i} испуњава ограничења, тј. проверити да ли важи A_{i} = nzd(K_{i},K_{i+1}) за свако i.

1 Like
5

Безбедна Подматрица

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

Анализа

Приметимо да ако смо изградили ограду чије је горње лево поље (x,y), а доње десно је (z,t) мора да важи x\leq a\leq z и y\leq b\leq t да би садржало поље које садржи кућу. Такође видимо да је у том случају обим подматрице управо 2\cdot(z+t-x-y)+4. Сада видимо да треба да максмизирамо вредност C_{xy}+C_{zt}+2\cdot(z+t-x-y)+4, за x\leq a\leq z и y\leq b\leq t. Простом провером по свим четворкама даје лако O((NM)^2).
Да би се ово даље оптимизовало, извршићемо замену редоследа сабирака: треба да максимизизирамо израз (C_{xy}-2\cdot x-2\cdot y)+(C_{zt}+2\cdot z+2\cdot t)+4. Означимо G_{xy}=C_{xy}-2\cdot x-2\cdot y и H_{zt}=C_{zt}+2\cdot z+2\cdot t. Сада видимо да тражимо максимум G_{xy}+H_{zt}+4, при чему важи x\leq a\leq z, y\leq b \leq t и сабирци G_{xy} и H_{zt} су потпуно независни. Стога можемо да нађемо максимум G_{xy} под условом x\leq a, y\leq b (нека је овај максимум M_1) и максимум H_{zt} по условом z\geq a, t\geq b (нека је овај максимум M_2), и затим испишемо решење M_1+M_2+4. Рачунање матрица G и H, као и тражење M_1 и M_2 се раде лаком претрагом у O(NM).

1 Like
6

Мој Број

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

Анализа

Идеја у овом задатку јесте дистанцирати се од конкретних бројева који су дати у низу А. Конструисаћемо низ од 12 бројева B такав да се сви бројеви од 1 до 10^8 могу представити као комбинација бројева из B помоћу рачунских операција.

Један пример оваквог скупа бројева јесу сви степени двојке 1, 2, 4, \dots, 2^{26}. Само сабирањем ових бројева могу се представити сви бројеви у интервалу [1, 2^{27}-1], што је довољно јер је 2^{27}>10^8. Конкретно представљање сваког броја иѕ низа A онда се може наћи користећи бинарни запис тог броја. Предвиђено је да ово решење носи 30 бодова.

Очигледно је да претходна идеја није оптимална јер не користи знакове - и *. Да бисмо могли правилно да искористимо знак -, направићемо малу промену у претходној идеји: уместо степена двојке, користићемо степене тројке. За то имамо помоћно математичко тврђење:

Лема: Сваки број од 1 до 3^n може се представити у облику е_03^0+e_13^1+\dots+e_n3^n, где e_i\in \{-1, 0, 1\}. Доказ: Овакво представљање бројева јако је слично са тернарним записом, али уместо цифре 2, користимо цифру -1. До оваквог записа долазимо тако што прво напишемо број у тернарном запису, а затим почевши од цифре најмање вредности проверавамо да ли је та цифра 2. Ако јесте, мењамо је у -1, а следећој цифри најмање вредности додајемо 1 (у суштини, 2\cdot 3^k мењамо са 3^{k+1}-3^k).

Користећи представљање описано горе, могуће је наћи израз облика који користи знакове + и - и представља сваки број од 1 до 3^{17} користећи бројеве 1, 3, ..., 3^{17}. Ово решење носи 70 бодова. Овде је добро прокоментарисати и сложеност овог решења. Наиме, описани алгоритам за сваки број налази представљање у О(дужина тернарног записа), што је О(\log A[i]). Ово значи да је сложеност укупног решења О(n\cdot\log 10^8).

Помоћу идеја описаних горе, лако је генерализовати поступак на базе веће о три. На пример, ако узмемо бројеве 1, 7^1, 7^2, \dots, 7^9, могуће је показати, истим алгоритмом као у доказу леме, да се сваки број од 1 до 10^8 може представити као e_07^0+e_17^1+\dots+e_97^9, где e_i\in\{-3, -2, -1, 0, 1, 2, 3\}. Зато ћемо у наш низ B додати и бројеве 2, 3, што даје низ B од укупно 12 бројева. Затим ћемо груписати све степене седмице уз које стоји +2 или -2 у једну заграду и њу помножити са 2 (аналогно за 3). То значи да бисмо могли добити израз облика нпр. 2\cdot(7^7-7^3)+3\cdot(7^6+7^1)-7^5=1982561. Овај алгоритам и даље ради у горе наведеној сложености О(n\cdot\log 10^8) . У описаној имплементацији само треба бити пажљив да свака заграда почиње са позитивним сабирком (ако нека заграда садржи само негативне сабирке, треба извући минус испред заграде).

6 Likes