Takmičarsko okruženje i tekstovi zadataka nalaze se ovde.
1 Like
Задатак Б1: Панграм
Аутор: Душан Здравковић
Текст и тест примери: Никола Јовановић
Анализа решења: Никола Јовановић
Тестер: Димитрије Ердељан
Анализа
Означимо број појављивања карактера ? у стрингу A са U, а скуп слова енглеске абецеде која се не појављују у стрингу A са S. Једним проласком кроз стринг можемо лако наћи ове вредности. Уколико се неко слово појављује више од једном можемо одмах закључити да реконструкција није могућа и прекинути извршавање програма.
Сада знамо да треба заменити тачно |S| карактера ? словима енглеске абецеде како би добијена реченица била савршен панграм. Како морамо заменити све карактере ?, следи да треба заменити тачно R=U-|S| њих размацима. Притом, ако важи U < |S| није могуће додати сва недостајућа слова, па је ово још један случај у ком закључујемо да реконструкција није могућа.
Остало је још извршити саму реконструкцију тј. распоредити слова и размаке. Треба имати у виду да није свеједно на који начин ово радимо. На пример, ако прво додамо свих |S| слова (тј. заменимо првих |S| карактера ? словима) можда неће бити могуће поставити свих R размака (нпр. због услова да два размака не смеју бити суседи). Приметимо да је увек могуће додати слово, али није увек могуће додати размак. Стога, вршићемо реконструкцију тако да greedy додајемо размаке док не додамо свих R. Другим речима, крећемо се кроз стринг A са лева на десно, и на свакој позицији постављамо размак уколико су сви услови испуњени: на тој позицији је карактер ?, нисмо на почетку/крају стринга, ниједан од два суседна карактера није размак. У супротном, додајемо једно од недостајућих слова из скупа S. Када на овај начин додамо свих R размака, све преостале карактере ? мењамо преосталим недостајућим словима из скупа S и исписујемо добијени стринг као решење задатка. Није тешко показати да се на овај начин може додати максималан број размака, те да уколико оваква процедура није у стању да дода свих R, дошли смо до трећег и последњег случаја у ком је немогуће извршити реконструкцију.
1 Like
Задатак Б2: Матрикс
Аутор: Алекса Плавшић
Текст и тест примери: Алекса Плавшић
Анализа решења: Никола Јовановић
Тестер: Иван Стошић
Анализа
Пођимо од наивног решења: ако за сваки упит рачунамо тражени \text{xor} проласком кроз целу подматрицу укупна временска сложеност је \mathcal{O}(qnm), што је довољно за први подзадатак у ком важи 1\leq n,m,q \leq 100.
Означимо вредност израза који треба израчунати за неку подматрицу са S. У наставку ћемо операцију \text{xor} означавати симболом \oplus. Важи S = A_{x_ly_l} \oplus \ldots\oplus A_{x_ry_r} = (x_l \oplus y_l) \oplus \ldots \oplus (x_r \oplus y_r). Означимо сада S_x = x_l \oplus \ldots \oplus x_r и S_y = y_l \oplus \ldots \oplus y_r. Независним разматрањем чланова по x и по y у изразу за S добијамо S = (S_x \oplus \ldots \oplus S_x) \oplus (S_y \oplus \ldots \oplus S_y) при чему прва заграда има \Delta y=y_r - y_l + 1, а друга \Delta x=x_r - x_l + 1 чланова (ширина и висина подматрице). Оваква репрезентација следи из комутативности операције \text{xor} и представља основу за побољшање нашег решења.
Искористићемо познато својство операције \text{xor}: за свако a важи a \oplus a = 0. Из овога следи да je вредност израза a \oplus \ldots \oplus a једнака a ако имамо непаран број чланова, а 0 у супротном. Ако применимо ово на добијену репрезентацију S добијамо да је вредност прве заграде једнака S_x када је \Delta y непарно, а 0 када је парно. На исти начин вредност друге заграде је S_y када је \Delta x непарно, а 0 када је парно. Дакле, ако наивно израчунамо вредности S_x и S_y можемо у зависности од парности димензија подматрице наћи \text{xor} свих њених вредности. Ово нас доводи до укупне временске сложености од \mathcal{O}(q(n+m)) што је довољно за други подзадатак у ком важи 1\leq n,m \leq 1000.
Покушајмо да убрзамо рачунање вредности S_x и S_y. Ако означимо са P(a) = 1 \oplus \ldots \oplus a видимо да је S_x = P(x_r) \oplus P(x_l - 1) и S_y = P(x_r) \oplus P(x_l - 1). Ово следи из својства истакнутог у претходном пасусу. Ако унапред израчунамо све потребне вредности P можемо при сваком упиту рачунати S_x и S_y у константном времену, тј. решити задатак у укупној временској сложености од \mathcal{O}(q). За чување вредности P нам је потребан низ одговарајуће дужине, па је укупна меморијска сложеност \mathcal{O}(m+n), што је довољно за трећи подзадатак у ком важи 1\leq n,m \leq 10^6.
Да бисмо дошли до оптималног решења смањићемо меморијску сложеност без погоршавања временске, тј. наћи начин да у константном времену израчунавамо вредности P(a). За ово треба приметити још једно, мало компликованије, својство операције \text{xor}:
P(a) =
\begin{cases}
a & \text{за} ~ a = 4k \\
1 & \text{за} ~ a = 4k+1 \\
a+1 & \text{за} ~ a = 4k+2 \\
0 & \text{за} ~ a = 4k+3
\end{cases}
До овог својства је могуће доћи посматрањем наивно израчунатих вредности P(a) или директно из опсервације да свака четворка бројева (4k, 4k+1, 4k+2, 4k+3) у бинарном систему има облик (\bar{L}00, \bar{L}01, \bar{L}10, \bar{L}11).
Сада имамо оптимално решење: за сваки упит у константном времену рачунамо вредности P(a) потребне да би се добили S_x и S_y. На основу њих, у зависности од парности димензија подматрице, рачунамо тражену вредност S.
1 Like
Задатак Б3: Жалбе
Аутор: Никола Милосављевић
Текст и тест примери: Никола Милосављевић
Анализа решења: Никола Милосављевић
Тестер: Андреј Ивашковић
Анализа
Први подзадатак се може решити једноставном анализом случајева: за n \leq 4 после фиксирања p_1 = k остаје нам највише 3 \cdot 2 могућих распореда које треба проверити. Други (истовремено и први) подзадатак се може решити у сложености O(n! \cdot n) проверавањем свих пермутација дужине n за укупно 25 поена.
Анализирајмо сада како генерисати било коју добру пермутацију, не обраћајући пажњу на број k и на лексикографски поредак (решење за 60 поена). Један од начина је
следећи: редом ћемо постављати вредности p_1, p_2, \ldots, p_n тако да се након i постављања на позицијама p_1, p_2, \ldots, p_i налазе узастопне вредности из сегмента [l, r] за неке l,r (где је l - r + 1 = i). У (i+1)-вом потезу, уколико је одговарајући карактер ‘P’, довољно је поставити p_{i+1} = l - 1, односно p_{i+1} = r+1 у супротном (наредни постављени број је увек или тренутни најмањи број - 1 или тренутни највећи број + 1); на почетку постављамо p_1 = x (за неки природан број x). На пример, за улаз
’PPGPGGGPP’ и нпр. x = 1, добијамо 1 \rightarrow 1 0 \rightarrow 1 0 -1 \rightarrow 1 0 -1 2 \rightarrow 1 0 -1 2 -2 \rightarrow 1 0 -1 2 -2 3 \rightarrow 1 0 -1 2 -2 3 4 \rightarrow 1 0 -1 2 -2 3 4 5 \rightarrow 1 0 -1 2 -2 3 4 5 -3 \rightarrow 1 0 -1 2 -2 3 4 5 -3 -4.
Поменути поступак се може имплементирати у сложености O(n). Јасно, добијена “пермутација” је у складу са бацањем новчића али добијени бројеви нису нужно из сегмента [1, n]. Ово можемо решити на 2 начина: 1) додати свим елементима пермутације p апсолутну вредност најмањег елемента + 1 или 2) изабрати x као 1 + број појављивања карактера ‘P’. Нпр. први начин примењен на поменути пример даје $$(1, 0, -1, 2, -2, 3, 4, 5, -3, -4) + 5 = (6, 5, 4, 7, 3, 8, 9, 10, 2, 1)$$
Дакле, (бар једна) добра пермутација увек постоји. У четвртом подзадатку се тражи лексикографски најмања добра пермутација (без услова за почетни број k) – сада је неопходно тежити да p_1 буде најмање могуће, затим да p_2 буде најмање могуће за изабрано p_1 итд. Уколико на почетку имамо m \geq 0 узастопних карактера ‘P’, тада мора бити p_1 = m + 1. Заиста, уколико би било p_1 < m + 1 не бисмо имали довољно места за померање улево; са друге стране, постоји добра пермутација која почиње са (m + 1, m, m - 1, \ldots, 2, 1) а затим неки скок удесно преко m+1 (могуће је наставити, нпр. на основу конструкције за 60%). Настављањем овог поступка за низ (m+2, m+3, \ldots, n) и преостале карактера долазимо до оптималног решења.
Није тешко доћи до следећег алгоритма сложености O(n) који реализује поменути поступак: додати ‘вештачки’ карактер ‘G’ на почетак стринга; поделити стринг на узастопне подстрингове чији је први карактер ‘G’; у пермутацији (1, 2, \ldots, n) обрнути редослед узатопним елементима који одговарају одговарајућим подстринговима и вратити добијену пермутацију. На пример, PPGPGGGPP \rightarrow GPPGPGGGPP \rightarrow GPP|GP|G|G|GPP \rightarrow 1 2 3 | 4 5 | 6 | 7 | 8 9 10 \rightarrow 3 2 1 | 5 4 | 6 | 7 | 10 9 8 \rightarrow (3, 2, 1, 5, 4, 6, 7, 10, 9, 8). Овај алгоритам осваја 72 поена.
Коначно, за максималан број поена треба модификовати претходни алгоритам тако да пермутација увек почиње бројем k. Нека на почетку стринга иде прво a \geq 0 ‘G’-ова а затим b \geq 0 ‘P’-ова. Узимајући у обзир лексикографску минималност, разликујемо два случаја: 1) Уколико је b < k (има места улево) тражена пермутација почиње са (k, k+1, \ldots, k + a) а остатак добијамо тражењем минималне добре пермутације преосталог скупа вредности (\{1, 2, \ldots, n\} \setminus \{k, k+1, \ldots, k + a\}) за преостали низ карактера; 2) Уколико је b \geq k (нема места улево) тражена пермутација почиње са (k, k+1, \ldots, k + a - 1, k + a + (b - k + 1)) а остатак добијамо тражењем минималне добре пермутације преосталог скупа вредности за преостали низ карактера. Наравно, у оба случаја за остатак пермутације користимо алгоритам из четвртог подзадатка.
Неефикасна имплементација претходних алгоритама (нпр. у O(n^2)) довољна је за прва три подзадатка тј. за око 40 поена.
1 Like
Задатак А1: Цик-цак
Аутор: Драган Урошевић
Текст и тест примери: Драган Урошевић
Анализа решења: Драган Урошевић
Тестер: Алекса Плавшић
Анализа
Приметимо да је највећи збир који може имати цик-цак низ са n елемената једнак \frac{n(n-1)}{2} и постиже се ако је сваки следећи елемент за један већи од претходног, тј. ако низ има следећи изглед:
0, 1, 2, ..., n-1.
Такође је најмањи збир који се може постићи једнак -\frac{n(n-1)}{2} и добија се када је сваки следећи елемент за један мањи од претходног па су елементи тог низа:
0, -1, -2, ..., -n+1.
Такође, приметимо да елементи низа задржавају парност, па су тако први, трећи, пети, итд. увек парни, а други, четврти, шести, итд. су увек непарни. Због тога суме свих цик-цак низова са истим бројем елемената (нека је број елемената n) увек исте парности. Према томе, ако су вредност \frac{n(n-1)}{2} и сума задата у поставци проблема (означимо ту суму са S) различите парности, задатак нема решење. Такође, ако је тражена сума већа од највеће могуће или мања од најмање могуће, задатак нема решење. У осталим случајевима задатак има решење и потребно је кренути од цик цак низа $$0, 1, 2, 3, …, n-1$$ чија је сума \frac{n(n-1)}{2} и смањивати док се не добије тражена сума. Приметимо да ако се други елемент добија смањивањем првог за један, док се сви остали добијају додавањем броја 1 на претходни, онда се укупна сума смањи за 2(n-1). То је зато што су се сви елементи осим првог смањили за два. Аналогно, ако трећи добијемо смањивањем другог за 1, а остале рачунамо непромењено, збир ће се смањити за 2(n-2).
Тако долазмо до правилности како рачунамо елементе низа. Нека је
D = \frac{n(n-1)}{2} - S.
Поставимо да је први елемент једнак нули (јер је тако и дефинисан цик-цак низ).
Почев од елемента са индексом k=2 (елементи су иначе индексирани почев од индекса 1), проверавамо да ли је тренутна вредност D већа од или једнака 2(n-k+1). Ако јесте, онда тај елемент добијамо умањивањем претходног за један и истовремено вредност D смањимо за 2(n-k+1). У супротном, тај елемент добијамо увећавањем претходног за један, а вредност D остаје непоромењена. Лако се уверавамо да ће се на овај начин увек добити низ чија је сума једнака траженој.
Приметимо да тиме што почетне елементе добијамо смањивањем претходних (када год је то могуће), обезбеђујемо да ће бити добијен лексикографски најмањи цик-цак низ са задатом сумом.
Задатак А2: Велика матрица
Аутор: Алекса Плавшић
Текст и тест примери: Алекса Плавшић
Анализа решења: Иван Стошић
Тестер: Иван Стошић
Анализа
За први подзадатак решење које рачуна суму подматрице елемент по елемент тј. решење сложености O(nmq) је довољно брзо.
За подзадатак где је M=2, уколико је висина H или ширина W подматрице паран број, одговор је \frac{WH}{2}. У супротном (ако су оба непарна), решење је \frac{WH + x}{2}, где је x вредност у горњем левом углу матрице. Ово проистиче из чињенице да матрица изгледа као шаховска табла.
За подзадатак где је n,m \leq 1000, можемо израчунати 2D префиксне суме, односно за свако u,v вредност P_{u,v} = \sum_{i\leq u, j \leq v} A_{i, j}. За ове вредности важи следећа веза: P_{u,v} = P_{u-1,v} + P_{u,v-1} - P_{u-1,v-1} + A_{u,v}. Након тога, вредност у подматрици (x_l, y_l) - (x_r, y_r) налазимо као P_{x_r,y_r}+P_{x_l-1,y_l-1}-P_{x_r, y_l-1}-P_{x_l-1,y_r}. Временска сложеност је O(nm+q).
Четврти подзадатак се решава исто као последњи, с тим што за поједине математичке суме није неопходно тражити формулу сложености O(1) већ се могу израчунати унапред све вредности у линеарној сложености по n,m.
Решење за максимални број поена се састоји од тога да се матрица подели на три дела, затим се сваки од тих делова дели на три поддела, а за сваки од њих се сума може израчунати у O(1), па је укупна временска сложеност O(1) по упиту односно O(q). Уколико је матрица правоугаона, први део биће једнакокрако-правоугли троугао коме је катета краћа ивица (горња или лева) а прав угао му је у горњем-левом темену подматрице. Слично, други део биће једнакокрако-правоугли троугао коме је прав угао у доњем-десном темену подматрице а катета му је краћа ивица (десна или доња). Трећи део је остатак ове подматрице који ће имати облик паралелограма (овај део може бити празан). У случају да је дата подматрица квадратна можемо узети да доњи десни троугао има за 1 краћу катету од горњег левог, а трећи део (паралелограм у средини) ће опет бити празан.
Затим, сваки од ових делова делимо на подделове. Сваки од делова ће се састојати од скупа споредних дијагонала таквих да су унутар дијагонале сви бројеви једнаки. Код првог дела (горњи/леви троугао), ове дијагонале имају растуће дужине, код другог дела (доњи/десни троугао) оне имају опадајуће дужине, а код трећег (средњег) дела оне имају једнаке дужине. Сваки од делова делимо на три поддела: Средњи од ових подделова се састоји максималног броја поддијагонала које редом узимају вредности 0, 1, 2, \ldots, M-1, док су остала два дела леви и десни остаци. За рачунање суме унутар сваког од ових подделова можемо користити следеће идентитете:
- \sum_{i=1}^n i = \frac{n(n+1)}{2}
- \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}
Неке од последица које су корисне при рачунању сума су:
- \sum_{i=1}^n (a+i)(b+i) = abn + \frac{n(n+1)(2n+1)}{6} + \frac{(a+b)n(n+1)}{2}
- \sum_{i=1}^n (a+i)(b-i) = abn - \frac{n(n+1)(2n+1)}{6} + \frac{(b-a)n(n+1)}{2}
1 Like
Задатак А3: Формула
Аутор: Душан Здравковић
Текст и тест примери: Иван Стошић
Анализа решења: Иван Стошић
Тестер: Никола Спасић
Анализа
Посматрајмо све K-елементне подскупове скупа симбола x_1, \ldots, x_n, где је x_i i-то слово енглеске абецеде. У свакој замени симбола конкретним вредностима, сваки од ових подскупова ће имати максимални елемент. Приметимо да вредност тог максималног елемента не може бити мања од K-те вредности по величини од свих N вредности. Штавише, тачно један од тих подскупова ће садржати K-ти елемент по величини од свих као свој максимум, и то онај подскуп који садржи најмањих K елемената. Дакле, овај максимум ће бити уједно и минимални максимум по свим K-елементним подскуповима.
Решење је, дакле, наћи максимум за све K-елементне подскупове а затим минимум свих тих вредности. Израчунајмо дужину формуле у зависности од K, N. Постоји \binom{N}{K} K-елементних подскупова. Запис максимума за сваког од њих ће се састојати од 4K-3 карактера. Затим, неопходно је израчунати минимум свих ових вредности за шта је потребно још 3(\binom{N}{K}-1) карактера. Дакле, укупан број карактера је (4K-3)\binom{N}{K} + 3(\binom{N}{K}-1). Овај израз се може упростити и износи 4K\binom{N}{K} - 3. “Најгори” случај је N=12, K=6 или N=12, K=7 и тада је број карактера 22173, што је свакако мање од 30000.
Смернице за алгоритам
Сви K-елементни подскупови неког скупа могу се генерисати рекурзивном функцијом или у језику C++ функцијом next_permutation примењеном на низ који се састоји од N-K нула и K јединица, тим редом.
1 Like
Zasto je u slucaju samo jednog polja odgovor 0 a ne vrednost tog polja. Drugi zadatak B
Odgovor u tom slucaju je vrednost polja. Ako se ovo odnosi na primer iz teksta zadatka, tamo se vrednost poklopila sa 0 ( matrica je nacrtana ispod ).