[Rešenja zadataka] Kvalifikacije 2020 - Prvi krug

Algoritam
1

Исплата

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

Анализа

Уочимо да ћемо за фиксно k и скуп \{1 \cdot 10^k, 2 \cdot 10^k, 5 \cdot 10^k\} у оптималном решењу искористити:

  • највише једну новчаницу типа 1 \cdot 10^k (две 1 \cdot 10^k се могу заменити једном 2 \cdot 10^k);
  • највише једну новчаницу типа 5 \cdot 10^k (две 5 \cdot 10^k се могу заменити једном 1 \cdot 10^{k+1});
  • највише две новчанице типа 2 \cdot 10^k (три 2 \cdot 10^k се могу заменити једном 1 \cdot 10^k и једном 5 \cdot 10^k), а ако искористимо барем две тада не користимо 1 \cdot 10^k (две 2 \cdot 10^k и једна 1 \cdot 10^k се могу заменити једном 5 \cdot 10^k).

Одавде следи да у оптималном решењу нема преноса, тј. ако представимо V=c_n 10^n + c_{n-1} 10^{n-1} + \dots + c_0 10^0, новчанице типа d \cdot 10^k користимо само како бисмо се решили члана c_k 10^k. Дакле, оптимално решење добијамо проласком кроз V цифру-по-цифру и сабирањем минималног броја новчаница типа d \cdot 10^k чији је збир c_k \cdot 10^k. На пример, за c_k=7 бирамо скуп \{5 \cdot 10^{k}, 2 \cdot 10^{k}\} што додаје 2 на коначан резултат. Све вредности минималног броја новчаница за c_k \in \{0,\dots9\} се лако могу израчунати: [0, 1, 1, 2, 2, 1, 2, 2, 3, 3].

Овај задатак је специјалан случај change making проблема. За скуп новчаница дат у овом задатку, greedy приступ (поновљено бирање највредније новчанице која нема вредност већу од преостале суме) дао би оптимално решење, еквивалентно горе описаном. Ипак, овај приступ није оптималан за све скупове новчаница, па се овај проблем у општем случају решава методом динамичког програмирања.

2 Likes
2

Одбојка

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

Анализа

Постоје два случаја у којима тражени меч не постоји: уколико важи N < 3A (јер морамо имати барем 3 сета са барем A поена у сваком), или уколико важи A=2 и 2 \nmid n (јер се тада сваки сет завршава разликом тачно 2, па укупан број поена мора бити паран).

У свим осталим случајевима, можемо пронаћи решење у тачно 3 сета. Претпоставимо, без умањења општости, да је први тим (чији је капитен Павле) победио 3:0 у сетовима. Нека су прва два сета завршена резултатом А:0. Дакле, у трећем сету је одиграно тачно N' = N-2A поена. Имамо два случаја:

  • Ако важи N' \leq 2A-2 тј. N'-A \leq A-2, трећи сет се не игра ,на разлику’’ и завршава се резултатом A : (N'-A).
  • У супротном, N' > 2A-2 тј. \frac{N'}{2}+1 > A, и трећи сет се игра ,на разлику’’, тј. први тим осваја више од A поена и разлика је тачно 2.
    • Ако је N' парно, трећи сет се завршава резултатом \frac{N'}{2}+1 : \frac{N'}{2}-1. По услову за овај случај, резултат је валидан.
    • Aко је N' непарно, трећи сет се завршава резултатом \frac{N'-1}{2}+1 : \frac{N'-1}{2}-1. Поново, из услова за овај случај следи \frac{N'-1}{2}+1 > A (јер је A природан број), па је овај резултат валидан. Сада нам преостаје 1 поен који просто пребацујемо у други сет, тако да резултат у њему постаје A:1 (ово није могуће урадити једино у случају A=2, али тај случај смо за непарно N', дакле непарно N, већ обрадили).
1 Like
3

Водопад

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

Анализа

Најпре ћемо објаснити решење које ради у сложености O(n^2 \cdot h), што је довољно да се освоји 70 поена, а затим ћемо показати како се то решење може једноставно изменити тако да ради у сложености O(n \cdot h) и донесе 100 поена.

Решење у O(n^2 \cdot h)

Ово решење добијамо једноставним симулирањем протокоа. Наиме, за свако i = 1 \ldots n “пустимо” јединични проток са врха водопада i-те колоне и симулирамо понашање тог јединичног протока. Кад проток удари у стену, тада га преусмеравамо лево или десно пратећи правила описана у поставци задатка. Када проток заврши на дну водопада у колони j тада увећамо за 1 испис за колону j.

Да бисмо проток који удари у стену правилно поделили лево и десно, приметимо прво да поставку проблема можемо преформулисати на следећи начин. Посматрајмо блок стена B.

  • Ако је B у непарном реду, тада се непарни по реду проток који удари у B преусмерава лево, док се парни по реду проток који удари у B преусмерава десно.
  • Ако је B у парном реду, тада се непарни по реду проток који удари у B преусмерава десно, док се парни по реду проток који удари у B преусмерава лево.

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

У овом решењу имамо n јединичних протока које симулирамо “поље по поље”. Пошто блок стена може имати дужину n - 1, дати проток може обићи O(n \cdot h) поља пре него што дође до дна. Одатле следи горе назначено време извршавања.

Решење у O(n \cdot h)

Да бисмо убрзали описано решење изнад, довољно је да за сваки блок стена запамтимо где су крај и почетак блока. Тада када проток удари било где у блок можемо га одмах симулирати са једног од крајева блока, без потребе да проток поље по поље прелази преко целог блока стена. То значи да се сваки ред може симулирати у O(1) времену, што даје укупну сложеност од O(n \cdot h).

Смернице за алгоритам

За алгоритам је потребно да означимо ком блоку свака стена припада, као и да за сваки блок одредимо његов почетак и крај. Да бисмо то урадили, најпре ћемо сваком блоку узастопних стена доделити јединствен број, на пример, редом бројеве почевши од 1. То можемо урадити на следећи начин. Чуваћемо променљиву blockNumber, која ће означавати редни број тренутног блока, и обилазити поља редом по редовима. Када наиђемо на стену, она је почетак новог блока ако и само ако је та стена прва у том реду, или ако је претходно поље било 1. Када детектујемо почетак блока, тада увећамо blockNumber за 1. Стени, била прва у блоку или не, доделимо blockNumber.

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

Бонус задатак

Симулација која доноси 100 поена кључно зависи од чињенице да постоји n јединичних протока. Како би се могао овај задатак решити у O(n \cdot h) времену ако се са врха водопада из i-те колоне пушта између 0 и 10^9 запремине воде?

1 Like
4

Шаховска трка

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

Анализа

Главна идеја је да се направи граф од 5*h*w чворова где свака позиција на табли има по 5 чворова (један за сваку фигуру). Гране у овом графу представљају све потезе које можемо да направимо и имају тежину од 1 до 5. Како би избегли MLE, ове гране не треба да чувамо у меморији него да прођемо кроз њих итеративно када посматрамо неки чвор.

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

Временска сложеност: O(n^3 * \log n), Меморијска сложеност: O(n^2).

Још једна оптимизација програма која није била потребна за 100 бодова је да се уместо Dijkstrinog~algoritma пусти Dialov~algoritam.

Временска сложеност: O(n^3), Меморијска сложеност: O(n^2).

3 Likes
5

Луксор

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

Анализа

Подзадатак 1

Приметимо да је један од бројева X,Y мањи или једнак \sqrt{A}, па је довољно извршити претрагу по свим бројевима X до \sqrt{A}, где проверавамо да је Y = \frac{A}{X} цео број и да је X \text{ XOR } Y = B. Временска сложеност по примеру је O(\sqrt{A}).

Подзадатак 2

Да би се смањио број кандидата за број X приметимо да X мора бити делилац броја A. Може се искористити било који брзи алгоритам за факторизацију целих бројева. Један такав алгоритам је Pollard-Rho алгоритам, који се најчешће имплементира заједно са Miller-Rabin алгоритмом за проверу да ли је број прост. Овај алгоритам има временску сложеност O(\sqrt[4]{n}) за налажење једног фактора броја n, али има велику скривену константу и из тог разлога није довољно брз.

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

Најпре, приметимо да при рачунању XOR вредности и производа два броја, најнижих n битова резултата зависе само од најнижих n битова операнада. Ако посматрамо фиксне вредности n, a, b, где је 0 \leq a, b < 2^n и a је непарно, показује се да постоји највише 2^{\lfloor\frac{n+3}{2}\rfloor} решења једначине

xy \equiv a \mod 2^n, x \text{ XOR } y = b,

где су x,y непознате, такође бројеви из скупа [0, 2^n). Из тог разлога, ако фиксирамо најнижих n битова броја X, оваквих валидних парцијалних решења неће бити више од 2^{\lfloor\frac{n+3}{2}\rfloor}. Ова парцијална решења можемо генерисати рекурзивно. У n том нивоу рекурзије имамо не више од 2^{\lfloor\frac{n+3}{2}\rfloor} позива. Довољно је пронаћи само првих 31 битова броја X, јер је због услова XY=A бар један од бројева X,Y мањи или једнак A, а увек можемо да претпоставимо да је то број X. Сумирањем по n добијамо да има O(\sqrt[4]{A}) рекурзивних позива, па је управо ово временска сложеност решавања једног тест примера.

2 Likes
6

Надам се да ће у следећим круговима бити више програмирања и мање математике. Ово скоро да није такмичење из информатике, већ такмичење из математике.

5 Likes
7

A po cemu je ovo takmicenje matematicarsko?
Moze se reci da je matematika zahtevnija od programiranja u 2. i 5. zadatku po meni, a 2. zahteva matematicko znanje osnovne skole za resavanje…

3 Likes
8

Po mom mišljenju ni 2. zadatak ne bih nazvao matematičkim, već čisto logičkim. Samo je 5. zadatak onako malo značajnije poznavanje matematike (kad se aproksimira koliko će biti (parcijalnih) rešenja jednačine za proveru, što nam pomaže da uočimo lakše optimalno rešenje zadatka).

1 Like
9

To to, ne bih ga ni ja nazvao, nego ajde kao ima vise matematike nego u ostalim zadacima pa da ga kazes… Ali mislim svakako informatika je bazirana na matematici, ne moze da se zali na matematiku bas tako…

1 Like
10

Dobro si rekao. Matematika je zahtevnija od programiranja u 2. i 5. zadatku i potrebno je više znanja iz matematike nego iz programiranja.
Moje znanje je još suviše malo da bih mogao previše da komentarišem na ovu temu ali mislim da bi takmičenje moglo biti malo manje fokusirano na matematiku.
I nisam sasvim siguran kako je to matematičko znanje iz osnovne škole?
(Možda napredno, ali nekako mislim da to ne pripada informatičkom takmičenju za 1. razrede srednje škole)
Podržavam svakoga ko dobro zna matematiku i može da reši ovakve zadatke ali mislim da ima mesta za promene.

P.S.
Ne zelim nikoga da uvredim. Kapiram da ste vi pametniji od mene i da je vama definitivno lakše. Samo kažem da bi po mom mišljenju trebalo biti manje orijentisano na matematiku.

11

Ne, nego se samo koriste radovi sa slucajevima u kojima se ne zahteva nista pored mnozenja/deljenja/sabiranja/oduzimanja.
Prvo se uvidi da nije potrebno imati vise od 3 seta, pa se napravi dobitna situacija za jednog igraca (recimo a,0;a,0;a,0). Po njoj rasporediti preostale poene ako je to moguce:
Tipa prvi set se dopuni do a,a-2. Ako jos poena ostane dopuniti sa n/2 poena oba igraca u prvom setu. Cim si raspodelio tako moze 1 poen da ti ostane za 2. set ili nista.
Sve ostalo su slucajevi i rad sa njima, ovo sve gore navedeno smatram da spada u neko osnovno znanje matematike. Vise ima sa logikom veze al o tome se sad ne raspravlja.
P.S.
Ne vredjas nikog sem sebe.

4 Likes
12

Sad kada ovako kažeš mogu se složiti da nije suviše komplikovano.
Izgleda da samo ja treba da steknem više iskustva.

Hvala na objasnjenju :smiley:

1 Like
13

Da, samo vezba.

2 Likes
14

Je l imate neku specificnu temu za 14. primer pa nadalje? S obzirom da su preveliki brojevi ne mogu da uvidim sto dobijam WA.

15

Ovako su rasporedjeni testovi:
1,2,3: sample
{10,13,34,35,36} Resenje je -1
[4,8] H,W<=5
[9,13] H,W<=200,BFS je resenje
[4,33] H,W<=200
[9,13]U[34,38] H,W<=500, BFS je resenje
[4,53] H,W<=500.
Od 14. pa nadalje idu normalni (gde samo BFS nije resenje) sa H,W<=200

1 Like
16

Kako BFS nije resenje? Je l mozes da das jedan primer za to?

1 Like
17

Jeste*.
Nisam dobro napisao.

1 Like
18

Steta, u tom slucaju tesko da cu da saznam razlog WA :frowning:

19

A ne cekaj, bio sam dobro napisao. Pod BFS sam mislio algoritam koji ide samo sa kraljem.