Tekstove zadataka možete ovde, gde možete i testirati svoje kodove.
Мала матрица
Аутор: Алекса Плавшић
Текст, тест примери и анализа решења: Драган Урошевић
Тестери: Алекса Плавшић и Иван Стошић
Анализа
Приметимо да ако су збирови подматрице коју чине прве две колоне и подматрице коју чине последње две колоне једнаки, онда су једнаки збир елемената у првој колони и збир елемената у трећој колони. Према томе, провераваћемо да ли можемо да подесимо вредности нула-елемената тако да збир прве и збир треће колоне буду једнаки. Елементи који се налазе у другој (средњој) колони не утичу на збир и због тога је довољно оне који су једнаки нули поставити на један.
Нека је nz укупан број нула у првој и трећој колони.
Ако је nz=0, онда у тим двема колонама нема нити један елемент који се може променити. Ако су збирови тих колона једнаки, онда проблем има решење и то је матрица у којој је само средња колона ажурирана тако што су елементи који су једнаки нули замењени јединицом.
Ако је nz=1, онда је само један елемент једнак нули и он може променити вредност. Његова вредност се одреди тако да збирови прве и треће колоне буду једнаки. Ако је та вредност већа од нуле, онда проблем има решење.
Ако је nz=3, онда је само један од 4 елемента у првој и трећој колони различит од нуле. Нека је k редни број колоне у којој се налази тај не-нула елемент. Једно од решења се добија тако што се други елемент у колони k изједначи са један, а елементи у колони 4-k (колоне нумерисане бројевима 1, 2 и 3) изједначе са одговарајућим елементима (иста врста) у колони k.
Ако је nz=4, онда су сва четири елемента једнаки нули и треба их променити у један.
Ако је nz=2, имамо два подслучаја:
Не-нула елементи су у истој колони (нека је то колона k). Тада елементе у колони 4-k трeба изједначити са одговарајућим у колони k (то је једно од могућих решења).
Не-нула елементи су у различитим колонама. Нека су вредности тих елемената a и b (обележени тако да је a\leq b). Једно од могућих решења се добија тако што се нула-елемент у колони у којој је b изједначи са 1, а нула-елемент у колони у којој је a изједначи са b-a+1. Лако се проверава да ово решење задовољава све услове задатка.
2 Likes
Тривијалан број
Аутор: Никола Милосављевић
Текст и тест примери: Алекса Плавшић
Анализа решења: Драган Урошевић
Тестери: Никола Јовановић и Иван Стошић
Анализа
Свакако најлакши начин да се реши овај задатак јесте да се одреди тривијалност сваког од бројева између 2 и N (N је број за који се тражи одговор) и након тога одреди број који има најмању тривијалност. При одређивању збира делилаца користимо чињеницу да у пару са сваким делиоцем d_1 < \sqrt{N} иде и делилац d_2 = \frac{N}{d_1}. Због тога је довољно само за бројеве између 1 и \sqrt{N} проверавати да ли деле број N и за сваки број d<\sqrt{N} који дели број n додати збиру делилаца вредност d + \frac{N}{d}, ако је \sqrt{N} цео број онда је и \sqrt{N} такође делилац броја N и треба га додати збиру (али са њим у пару не иде други делилац). Према томе, одређивање збира свих делилаца за све бројеве између 2 и N има сложеност O(N\sqrt{N}). Ако то треба да поновимо T пута (за T различитих улазних вредности), онда је укупна сложеност O(TN\sqrt{N}).
Горње решење можемо профинити тако што би само једном рачунали збир делилаца за бројеве између 2 и највећег од бројева A_i, након тога за сваки појединачни A_i, одређујемо број са најмањом тривијалношћу, рачунајући количнике збира делилаца и бројева за одговарајуће бројеве.
Одређивање збира делилаца можемо убрзати користећи чињеницу да су сви бројеви d, 2d, 3d, 4d, \ldots дељиви бројем d и због тога збиру делилаца за те бројеве треба додати број d. Према томе за сваку вредност d=1, 2, 3, \ldots, N треба збиру делилаца бројева d, 2d, 3d, \ldots, kd (где је k број са особином да је kd \leq n < (k+1)d) додати број тј. делилац d. Лако закључујемо да за конкретно d треба ажурирати (увећати) збир делилаца за \frac{N}{d} бројева, па је сложеност одређивања збира делилаца за бројеве између 2 и N једнака O(N + \frac{N}{2} + \frac{N}{3} + \ldots + \frac{N}{N}) = O(N\log N).
Приметимо да је збир делилаца за просте бројеве p једнак p+1 и тривијалност простог броја је једнака 1 + \frac{1}{p}. С друге стране сваки сложен број N има особину да је збир делилаца већи од N + \sqrt{N}, па је тривијалност вeћа од 1 + \frac{1}{\sqrt{N}}. Намеће се да ће најмању тривијалност у интервалу од 2 до N имати највећи прост број који није већи од N. Одређивање тог највећег простог броја можемо извести тако што за бројеве N, N-1, N-2, \ldots проверавамо да ли су прости и поступак прекидамо када одредимо први број који јесте прост. Поступак можемо профинити тако што би тестирали (проверавали) само бројеве облика 6k+1 и 6k+5 (наравно, изузетак су 2 и 3).
Проверу да ли је број прост N изводимо проверававајући да ли има делиоце међу бројевима између 2 и \sqrt{N}. Ако међу њима има бар један делилац онда број N није прост, у супротном јесте.
Поступак провере да ли је број прост можемо убрзати тако што би проверавали да ли број N има делиоце само међу простим бројевима између 2 и \sqrt{N}. Због тога би за почетак требало да одредимо само просте бројеве између 2 и \sqrt{N} (користећи на пример Ератостеново сито), а затим да тестирамо да ли је неки број прост тако што проверавамо да ли је дељив неким простим бројем које смо претходно издвојили.
2 Likes
Топла вода
Аутор, текст и тест примери: Иван Стошић
Анализа решења: Никола Јовановић
Тестер: Алекса Плавшић
Анализа
Водоводну мрежу можемо посматрати као стабло са кореном у чвору у ком се налази бојлер (чвор 1). На самом почетку, вода у свим цевима (тј. свим гранама стабла) је ледена. У току извршавања упита маркираћемо оне гране у којима вода постане топла. Сада сваки упит можемо формулисати као одговор на питање ,,Колико има немаркираних грана на путу од корена до чвора x_i?’’. Наравно, на почетку ниједна грана није маркирана.
Најједноставнији начин да одговоримо на упит је да обиђемо све гране од x_i до корена, избројимо немаркиране, а затим их маркирамо. Овај приступ у најнеповољнијем случају обилази цело стабло при сваком упиту па је временска сложеност O(MN).
Кључна опсервација која нас доводи до бољег решења је да се сваки пут од корена до неког чвора дели на низ (0 или више) маркираних грана, а затим низ (0 или више) немаркираних грана. Другим речима, сви маркирани чворови на неком таквом путу чине префикс тог пута. Ово се лако доказује тако што приметимо да је свака маркирана грана постала маркирана при тражењу одговара на неки упит. Самим тим, све гране од ње до корена су такође маркиране у истом упиту. Имајући ово својство у виду, довољно је при сваком упиту обилазити само гране од x_i до прве маркиране гране на путу до корена. Све гране на остатку пута су сигурно већ маркиране.
Ово решење, иако за неке ,,незгодне’’ упите може обићи много грана, у току целог извршавања програма обиђе сваку грану највише једном (у тренутку када бива маркирана), па је укупна временска сложеност O(N+M), што је у овом случају оптимално.
Смернице за алгоритам
Са стране имплементације, решење се дели на два дела: припрему стабла и одговарање на упите. Припрема стабла се своди на чување родитељског чвора за сваки чвор, што након учитавања грана можемо урадити простом графовском претрагом (DFS/BFS). При сваком упиту долазимо до одговора праћењем низа родитељских чворова почевши од чвора x_i, притом вршећи маркирање свих посећених чворова.
2 Likes
Џокери
Аутор, текст и тест примери: Петар Величковић
Анализа решења и тестирање: Слободан Митровић
Анализа
Приметимо најпре да је задатак за случај x = y = 0 једнак проблему Најдужи Заједничи Подниз (енгл. Longest Common Subsequence; скр. LCS). Уз врло једноставну измену, алгоритам за LCS може такође решити варијанту овог задатка за случај x = 0. Дакле, права тежина задатка лежи у случају када x \neq 0. У наставку ћемо се најпре укратко подсетити алгоритма за LCS и показати како се једноставном изменом може искористити да реши овај задатак за случај x = 0. Потом ћемо описати како се тај алгоритам може проширити тако да реши овај задатак у општем случају, тј. чак и када x \neq 0.
Стандардни LCS алгоритам дефинише низ dp[i][j] који представља LCS за стрингове A^i и B^j, где A^i (B^j) означава суфикс стринга A (B) од позиције i (j). Тада, dp[i][j] дефинишемо као: dp[i][j] = \max\{dp[i + 1][j], dp[i][j + 1], eq_{i, j}\}, где у случају да А[i] = B[j] имамо eq_{i, j} = dp[i + 1][j + 1] + 1, а иначе eq_{i, j} = -\infty.
Да бисмо решили овај задатак у случају када x = 0, довољно је да дефинишемо dp[i][j] на само мало другачији начин, наиме dp[i][j] = \max\{dp[i + 1][j] - y, dp[i][j + 1] - y, eq_{i, j}\}, где је eq_{i, j} дефинисано као и пре.
Посматрајмо сада случај x \neq 0. Прво, у дефиницији dp[i][j] имамо, између осталог, вредност dp[i + 1][j] - y која се може интепретирати на следећи начин: убацимо џокер испод карактера А[i], што има цену y, и пронађимо LCS за A^{i + 1} и B^j. Када x \neq 0, треба ли цена и даље да буде само y или ипак треба да буде x + y? То зависи од тога да ли је и испод A[i - 1] био џокер или није. Ако је испод био џокер, онда је цена само y (јер не почињемо нову операцију), а ако није био џокер онда је цена x + y (јер почињемо нову операцију). Сада је јасно како проширити алгоритам за LCS да реши овај задатак – поред индекса i и j, требало би памтити још два индикатора (тј. две променњиве где свака има вредност 0 или 1) које означавају да ли је испод A[i - 1], тј. изнад B[j - 1], био уметнут џокер или није.
Смернице за алгоритам
Рецимо да желимо да израчунамо dp[i][j][ind1][ind2], где су ind1 и ind2 као што је описано изнад. У смерницама датим испод, претпостављамо да су стрингови A и B индексирани од 0. Ради једноставности, нека ret представља вредност коју желимо да израчунамо. Тада имамо
Ако ако i == length(A) и j == length(B):
ret = 0
Иначе, ако је i == length(A):
ret = -x * (1 - ind2) - y * (length(B) - j)
Иначе, ако је j == length(B):
ret = -x * (1 - ind1) - y * (length(A) - i)
Иначе:
Ако је A[i] == B[j]:
ret = \max\{dp[i][j + 1][0][1] - x * (1 - ind2) - y, dp[i + 1][j][1][0] - x * (1 - ind1) - y,
dp[i + 1][j + 1][0][0] + 1\}
Иначе:
ret = \max\{dp[i][j + 1][0][1] - x * (1 - ind2) - y, dp[i + 1][j][1][0] - x * (1 - ind1) - y\}
5 Likes
Киосци
Аутор, текст, тест примери и анализа решења: Никола Милосављевић
Тестери: Иван Стошић и Душан Живановић
Анализа
Означимо са (x_i, y_i) координате а са v_i количину магле у i-том по реду отвореном киоску. Јасно је да је за сваки упит типа 2 са параметрима (x, y) потребно израчунати суму \sum_{i=1}^k (|x - x_i| + |y - y_i|)\cdot v_i, где је k тренутни број изграђених киоска. Директно рачунање суме за сваки упит доводи до решења сложености O(n^2) што је довољно само за први подзадатак. Једно корисно (и, када се ради са Менхетн растојањима, врло стандардно) запажање је да се претходна сума може независно посматрати по x и y координатама; дакле, довољно је решити проблем рачунања суме \sum_{i=1}^k |x - x_i|\cdot v_i, применити исти алгоритам за y координате и сабрати две добијене вредности на крају.
Уколико је m довољно мала вредност, можемо користити помоћне низове vx[] и vy[] дужине m где је vx[a] = сума вредности v_i за све изграђене киоске чија је x-координата једнака a (аналогно и за низ vy[]). Приликом додавања новог киоска (x_i, y_i, v_i), aжурирамо информације са vx[x_i] \leftarrow vx[x_i] + v_i док приликом упита типа 2 (x, y), тражена сума се своди на \sum_{i=1}^m |x - i|\cdot vx[i]. Овим смо добили алгоритам сложености O(nm) који користи O(m) меморије, што решава други подзадатак.
У трећем подзадатку, након учитавања свих упита типа 1, нема више промена; посматрано по једној координати, задатак постаје еквивалентан “тежинској” верзији задатка Продавнице са првог круга квалификација (видети одговарајуће решење). Сортирањем упита типа 1 на почетку и користећи бинарну претрагу за упите типа 2 добиијамо решење сложености O(n \log n).
Мотивисани решењем другог подзадатка, нека је A[i] сума вредности v за све киоске са x-координатом i, а нека је B[i] = i \cdot A[i] (на почетку су оба низа попуњена нулама). Тражена сума (за упит (x,y)) се може трансформисати као
\sum_{i=1}^k |x - x_i|\cdot v_i = \sum_{i=1}^m |x - i|\cdot A[i] = \sum_{1 \leq i \leq x} (x \cdot A[i] - B[i]) + \sum_{x < i \leq m} (B[i] - x \cdot A[i])
= 2x \cdot \sum_{1 \leq i \leq x} A[i] - 2 \cdot \sum_{1 \leq i \leq x} B[i] - (x \cdot totalA - totalB)
где су totalA и totalB, редом, суме свих елемената низова A и B. Задатак се сада своди на следеће: приликом упита типа 1 (x, y, v) треба ажурирати A[x] \leftarrow A[x] + v и B[x] \leftarrow B[x] + x \cdot v (као и totalA и totalB), док приликом упита типа 2 (x, y) треба израчунати суме \sum_{1 \leq i \leq x} A[i] и \sum_{1 \leq i \leq x} B[i] и убацити их у горњу формулу.
Међутим, ово је познати проблем који се најефикасније решава помоћу Кумулативне табеле или Сегментног стабла над низовима A и B (и, наравно, одговарајућим низовима за y-координате). Користећи ове структуре, добијамо сложеност O(\log n) по упиту, тј. укупно O(n \log n). Како ове структуре захтевају O(m) меморије, праволинијска имплементација је довољна за прва 4 подзадатка. Да бисмо очували ову сложеност, финални позадатак је потребно радити ‘offline’ уз пар трикова: учитати све координате и компресовати их на сегмент [1,n] (нпр. сортирањем) уз одговарајуће мапирање - тиме се меморијска сложеност своди на O(n). Меморијско ограничење је дозвољавало и да се задатак ради ‘online’ користећи Имплицитно сегментно стабло - у том случају је временска и меморијска сложеност алгоритма O(n \log m).
4 Likes
Bilo bi predobro kada bi ovako nesto postojalo za svako takmicenje, barem za republicko i SIO.
2 Likes
I naravno zadaci sa SIO
Svakako to i jeste plan. Na Algori smo već pisali rešenja sa prošlogodišnjeg SIO, ali radimo na tome da budu lako dostupna, zajedno sa svim prethodnim zadacima.
1 Like