Takmičarsko okruženje i tekstovi zadataka nalaze se ovde.
Задатак 1 - Зечеви
Аутор, текст и тест примери: Иван Стошић
Анализа решења: Иван Стошић
Тестер: Душан Здравковић
Учитамо висине три зеца и уредимо их у неопадајући редослед. Добијамо три броја b_1 \leq b_2 \leq b_3. Посматрајмо разлике d_1 = b_2 - b_1 и d_2 = b_3 - b_2. Уколико су ове разлике једнаке, могуће је наћи решење, то је број b_3 + d_2 и он заједно са остала три чини аритметичку прогресију. И број b_1 - d_1 такође чини аритметичку прогресију са остала три броја али овај број може бити мањи или једнак нули, док претходно наведени b_3 + d_2 не може, јер је већи или једнак од b_3 који је природан број. Даље, уколико је d_1 = 2 d_2, односно, уколико је разлика другог и првог броја дупло већа од разлике трећег и другог броја, можемо додати нови број између прва два, а то је број b_1 + d_2, и он са осталима чини аритметичку прогресију. Ако је пак d_2 = 2 d_1 можемо додати број b_2 + d_1 и он ће са преостала три чинити аритметичку прогресију. Ако ниједан од ових услова није испуњен, такав број не постоји.
2 Likes
Задатак 2 - Најближи неопадајући
Аутор, текст и тест примери: Владимир Миловановић
Анализа решења: Владимир Миловановић
Тестер: Иван Стошић
Анализа
Потребно је приметити да провера да ли је одређени број неопадајући не зависи линеарно од вредности тог броја, већ од броја његових цифара који је за природне бројеве у декадном запису пропорционалан \log_{10}N.
Идејно најједноставније решење највероватније је да се крене од задатог броја N и редом проверава да ли је неопадајући или не, тако што ће се најпре испитати сам задати број N, затим N\pm1, па N\pm2 и тако даље.
Међутим, свакако елегантније решење је да се за унети број N на ефикасан начин пронађе најближи неопадајући број већи и најближи неопадајући број мањи од задатог броја, а потом врати онај који се налази на мањој разлици од N, односно да се испишу оба, уколико се испостави да су подједнако удаљена.
Да би се одредио најближи неопадајући број већи од задатог броја, најпре у низу цифара унетог броја почевши од цифре највећег значаја треба пронаћи прво место где низ постаје опадајући, односно две суседне цифре за које важи c_{i} > c_{i-1}, а затим све цифре у опсегу од c_{0} до c_{i-1} променити у c_{i}. Тако ће на пример број N=12321 бити преправљен у 12333, а самим тим и одређен најближи неопадајући број већи од задатог броја.
Слично томе, како би се одредио најближи неопадајући број мањи од задатог броја, прво се на исти начин пронађе монотоно неопадајући префикс броја N, потом c_{i} умањи за један, а цифре у опсегу од c_{0} до c_{i-1} промене у 9. За горњи пример N=12321 то значи да ће најближи неопадајући број мањи од задатог броја бити 12299. Треба обратити пажњу да декрементирање последње цифре префикса може проузроковати промену његове монотоности, као на пример код N=12345554321, па најближи неопадајући број неће бити 12345549999, ни 12345499999, већ 12344999999. Узимајући и тај случај у обзир долази се до најближег неопадајућег броја који је мањи од задатог.
Уз напомену да је временска сложеност проналаска најближег неопадајућег броја линеарна по дужини низа цифара, односно логаритамска по вредности задатог броја N, преостаје само да се провери који је од два неопадајућа броја ближи, и да се исти испише, чиме је задатак урађен у \mathcal{O}(\log{N}) временској сложености.
2 Likes
Задатак 3 - Струја
Аутор: Никола Јовановић
Текст и тест примери: Димитрије Ердељан
Анализа решења: Димитрије Ердељан
Тестер: Никола Јовановић
Ако оптимално тргујемо струјом, сигурно ћемо сваког дана или “чекати”
(без куповине и продаје), или потрошити сав новац на струју, или
продати сву струју коју имамо. Ово тврђење неће бити формално доказано
овде, али идеја иза њега је да ако “раздвојимо” новац (или струју) и
потрошимо само део, потрошен и сачуван део се могу посматрати
независно. Ако потрошен део новца доноси бољу зараду од непотрошеног,
боље је да потрошимо све (и обрнуто).
Сада је потребно само одабрати дане када ћемо куповати и продавати
струју. Оптималан избор је да купујемо у локалним минимумима цене,
односно данима када је струја јефтинија него што је била јуче и него
што ће бити сутра, и да продајемо у локалним максимумима (кад је
скупља од суседних дана). Да бисмо доказали да је ово оптимално,
посматрајмо било који други избор дана. Тада сигурно можемо “померити"
ону куповину (или продају) која није локални минимум (максимум) на
"суседни” дан када је цена повољнија и зарадити више.
Локалне минимуме и максимуме можемо наћи у \mathcal{O}(N) (за сваки
дан гледамо само два суседа), тако да се цео задатак може решити у
\mathcal{O}(N). Обратите пажњу на први и последњи дан – пошто имају
само једног суседа, можемо их или посматрати као специјалне случајеве,
или додати “вештачке” елементе за дане 0 и N+1, са ценама \infty и
-\infty.
Нешто једноставније решење за имплементацију је следеће: за сваки дан
можемо одлучити да ли ћемо тог дана купити струју и одмах је продати
следећег дана. У овом случају дозвољавамо да исти дан продамо струју и
опет је купимо по истој цени (што је исто као да не урадимо
ништа). Јасно је да ћемо у овом случају куповати оних дана када је
цена мања него следећег, тако да можемо избећи “памћење” минимума и
максимума.
3 Likes
Задатак 4 - Плус минус
Аутор, текст и тест примери: Драган Урошевић
Анализа решења: Драган Урошевић
Тестер: Никола Јовановић
Анализа
Означимо са s_k збир првих k елемената низа, тј. s_k = \sum_{i=1}^k x_k, \ \ \ \ k=0, 1, 2, ..., n.
Зваћемо ове збирове парцијалне суме.
Лако се закључује да је збир елемената ед елемента на позицији i до елемента на позицији j једнак
x_i + x_{i+1} + ... +x_{j-1} + x_j = s_j - s_{i-1}.
Ако је збир елеманата од елемента на позицији i до елемента на позицији j позитиван, онда је s_j-s_{i-1} > 0, односно s_{i-1} < s_j. Ако је збир елеманата од елемента на позицији i до елемента на позицији j негативан, онда је s_j-s_{i-1} < 0, односно s_{j} < s_{i-1}.
Формираћемо оријентисан граф G=(V,E) у коме чворови одговарају парцијалним сумама (можемо чворове нумерисати и бројевима између 0 и n). За сваку неједнакост облика s_a < s_b уводимо ивицу од чвора који одговара парцијалној суми s_a до чвора који одговара парцијалној суми s_b. Ако у том графу постоји петља, онда не постоји низ који задовољава задате услове. Наиме, петља је низ чворова у коме се први и последњи чвор поклапају такав да између свака два узастопна постоји ивица. Нека тај низ чине чворови
s_{k_1}, s_{k_2}, s_{k_3}, ..., s_{k_c}, s_{k_1}.
Тада за парцијалне суме важи
s_{k_1} < s_{k_2} < s_{k_3} < ..., <s_{k_c} < s_{k_1}
и због транзитивности је s_{k_1} < s_{k_1} , што је контрадикција.
Ако у графу G не постоји циклус, чворови графа се могу поређати у низ тако да ако постоји ивица од чвора s_a до чвора s_b онда је чвор s_a стоји у низу пре чвора s_b. Свако такво ређање у низ се назива тополошко сортирање и може се обавити варијацијом на обилазак графа у дубину. На основу тог набрајања чворова, парцијалним сумама (чворовима графа) можемо доделити целе бројеве, тако да се чвору s_0 додели вредност 0, чворовима који се налазе после њега у том набрајању редом бројеви 1, 2, 3, ... (у складу са поретком у набрајању), а чворовима који се налазе пре њега редом бројеви -1, -2, -3, ... (овај пут сдесна улево, у складу са набрајањем). Лако се уверавамо да ће за свака два чвора s_a и s_b важити да ако је s_a пре (лево) од s_b у набрајању, онда је s_a < s_b. Другим речима, парцијалним сумама смо доделили различите целе бројеве и они задовољавају све неједнакости које су задате у улазним подацима.
На основу парцијалних сума се могу одредити елементи низа:
x_i = s_i - s_{i-1},\ \ \ \ i = 1, 2, ..., n.
Смернице за алгоритам
Дајемо само псеудокод за топошко сортирање (набрајање). Претпостављамо да је граф репрезентован помоћу вектора/листи суседа својих чворова. Резултат који враћа функција је 0, ако граф јесте ацикличан (поред тога је у низу tops његово тополошко сортирање), a 1, ако је граф има бар једну петљу и самим тим не постоји тополошко сортирање.
topsort() {
p = n;
for (i = 0; i <= n; i++)
mark[i] = BEO
for (i = 0; i <= n; i++)
if (mark[i] == BEO)
if (topsortr(i) != 0) return 1;
return 0;
}
topsortr(i) {
mark[i] = SIV;
for (k = 0; k < susedi[i].size(); k++) {
j = susedi[i][k];
if (mark[j] == SIV) return 1;
if (mark[j] == BEO)
if (topsortr(j) != 0) return 1;
}
tops[p] = i;
p = p - 1;
mark[i] = CRN;
return 0;
}
3 Likes
Задатак 5 - Преписивање
Аутор, текст и тест примери: Душан Здравковић
Анализа решења: -
Тестер: Иван Стошић
1 Like
Kada ce resenje za 5. zadatak biti okaceno?
2 Likes
U toku ove nedelje sigurno, a nadam se vrlo uskoro 
2 Likes
Rešenje je napisano još “one nedelje”, samo što su slova obojena u belo i post je vešto sakriven na Algori.
7 Likes
Ako komisija ne moze da oboji slova u neku drugu boju, ja cu napisati svoje resenje u toku ove nedelje sigurno, a nadam se vrlo uskoro
3 Likes
Bilo bi lepo da napišeš svoju ideju, verujem da bi mnogima bila korisna !
Naravno nadam se da će @DuX isto uraditi, kao i da če skorije biti objavljena rešenja svih zadataka sa SIO.
1 Like
Преписивање
Подзадатак 1
Сложеност O(K\sum_{i=1}^{N} S_{i}).
За сваку рунду треба имати листу такмичара који су на њој преписивали. Сваки упит решавамо тако што кренемо од почетне рунде и бројимо оне такмичаре које смо први пут ухватили.
Offline решење
Потребно нам је сегментно стабло. Да би решили све упите којима је почетна рунда S за сваког такмичара који је преписивао на некој од рунди иѕ сегмента [S,R] треба да на вредност прве рунде на којој ће бити ухваћен додамо 1. Да би ефикасно изградили структуру треба да решавамо прво све упите са S=R па S=R-1 итд. Када је S=R вредност R у стаблу биће једнака броју људи који су преписивали на тој рунди. За остале S није довољно само поставити вредност на број људи који су преписивали на тој рунди већ морамо и да смањимо вредност неких од следећих рунди. Ако је такмичар X преписивао на тренутној рунди и на некој од следећих треба да смањимо вредност следеће рунде на којој је преписивао. Овако у сваком кораку имамо описано сегментно стабло. Упите решавамо бинарном претрагом по решењу уз помоћ сегментног стабла. Сложеност овог алгоритма је O(Klog^2R).
Подзадатак 2
Овај подзадатак се решава тако што уместо обичног сегментног стабла користимо persistent segment tree. Тако можемо приступити претходним верзијама сегментног стабла и после целе изградње. Временска сложеност остаје O(Klog^2R) а меморијска се повећава на O((\sum_{i=1}^{N} S_{i})logR).
Подзадатак 3
Овај подзадатак захтева више размишљања. Потребно је смањити сложеност Offline решења са O(Klog^2R) на O(KlogR). Приметимо да сегментно стабло већ има израчунате вредности за неке сегменте. То можемо користити уместо бинарне претраге. Започнимо рекурзивну алгоритам у корену стабла. Ако је вредност левог сегмента већа или једнака броју такмичара које члан комисије треба да ухвати померамо се на лево подстабло, ако не померамо се на десно подстабло и памтимо да смо ухватили онолико такмичара колика је била вредност левог сегмента. На крају овог алгоритма налазимо се у листу који представља решење упита.
Подзадатак 4
Овај подзадатак се решава применом подзадатака 2 и 3, односно користимо persistent segment tree и описани алгоритам на њему да би смањили временску сложеност на O(KlogR) док меморијска сложеност остаје O((\sum_{i=1}^{N} S_{i})logR).
На линку испод је детаљно објашњена persistent segment tree структура података.
Задаци за вежбу
Овај трик није ништа ново у такмичарском програмирању. Постоји доста задатака који се решавају на сличан начин.
http://codeforces.com/contest/899/problem/F
Овај задатак може да се решава и као подзадатак 2.
http://codeforces.com/problemset/problem/786/C
Овај задатак захтева persistent segment tree и трик за смањење сложености.
8 Likes