Rešenja zadataka sa SIO 2019/2020 - dan 1
Бројорб
Аутор: Душан Здравковић
Текст и тест примери: Душан Здравковић
Тестер: Иван Стошић
Текст решења: Иван Стошић
За почетак, докажимо да је број различитих потпалиндрома неког стринга мањи или једнак дужини стринга. Доказ индукцијом по дужини стринга. За стрингове дужине 1 тврђење очигледно важи. Нека је S стринг дужине n = |S| > 1 и нека је S' = S_1S_2\ldots S_{n-1}. Посматрајмо све суфиксе од S који су палиндроми. Сви осим најдужег суфикса се сигурно јављају и у S' јер су они уједно прави префикси најдужег суфикс палиндрома. Одавде следи да S има највише 1 потпалиндром више од S' што доказује тврђење. Стрингове који задовољавају једнакост ове теореме зваћемо пуним.
Корисно је приметити да, уколико је S пун стринг, тада је и сваки његов префикс такође пун стринг, што нам омогућава да овакве стрингове генеришемо рекурзивно, тако што на тренутни пун стринг додајемо карактер 0 или 1, све док вредност овог броја не достигне горњу границу, када излазимо из рекурзије. Ову рекурзију можемо убрзати на следећи начин:
- Уместо са стринговима, радити са бит маскама. Све потребне операције са стринговима могу се имплементирати као битовске операције на бројевима.
- Током рекурзије чувати скуп потпалиндрома за тренутни број. Унутар једног корака рекурзије овај скуп ће се променити за тачно један елемент.
- Проверавамо само најдужи суфикс палиндром новогенерисаног броја. Из доказа теореме знамо да је довољно посматрати само њега.
- Поред самог броја, чувати и обрнут запис тог броја у рекурзији како би се избегло његово обртање при тражењу најдужег суфикс палиндрома.
Са овим опсервацијама, сложеност рекурзивне функције може се спустити на O(m) по позиву, где је m највећа дужина бинарног записа бројева. Укупна сложеност целог алгоритма је онда O(mk), где је k број пронађених пуних стрингова. Како је k < 10^{10} чак и за последњи, највећи пример, време извршења целог програма је неколико десетина минута.
Шашаво одело
Аутор: Павле Мартиновић
Текст и тест примери: Павле Мартиновић
Тестер: Алекса Плавшић
Текст решења: Лазар Миленковић
Решења неких потпроблема
Најпре ћемо почети са неколико потпроблема који не воде нужно ка финалном решењу.
Свака тачка је повезана са највише две друге тачке.
Није тешко видети да је ово стабло заправо прост пут. Пошто сваки чвор има највише два суседа, боје које долазе у обзир су само 1 или 2. Знамо да оба краја пута морају имати боју 1, па није толико тешко размотрити све случајеве за остале бројеве у зависности од дужине пута [Помоћ 1].
N\leq20
Овај потпроблем могуће је решити једноставним бектрек алгоритмом. За сваки чвор испробамо све могућности за његове боје. Пробајте доказати да је укупна сложеност овакве имплементације одозго ограничена производом степени чворова и да овај производ никада не премашује 2^20 [Помоћ 2].
Решења потпроблема коришћењем динамичког програмирања
Идеја је рачунати матрицу динамичког програмирања где су могућа стања означена са dp[r][i][c]. Прва димензија r \in \{0, 1\} означава нулом да родитеља није потребно бојити истом бојом, а јединицом да је родитеља потребно обојити истом бојом. Друга димензија 1 \le i \le N означава чвор који се тренутно разматра, док на крају трећа димензија 1 \le c \le N означава боју која се тренутно разматра. Вредности у матрици биће 0 уколико је конфигурација изводљива и 1 уколико није. Претпоставићемо да је стабло укорењено у неком чвору (рецимо чвору 1) и обилазићемо стабло рекурзивно, тако да се dp вредност чвора рачуна након dp вредности његових наследника. Уколико је стабло могуће обојити вредност dp[0][1][c] биће 1 за неку од боја c.
N\leq500
За сваки чвор i и сваку боју c, пролазимо по свим наследницима чвора и проверавамо за сваког од њих да ли га је могуће обојити у c (овај тип наследника зовемо истобојни наследници за боју c), да ли га је могуће обојити у неку другу боју (овај тип наследника зовемо разнобојни наследник за боју c), као и да ли га је могуће обојити у исту и у различиту боју (овај тип наследника зовемо шарени наследник за боју c). На основу броја истобојних, разнобојних и шарених наследника, могуће је утвридити dp[0][i][c], као и dp[1][i][c].
N\leq3000
Мало пажљивија имплементација рачунања dp табеле довољна је за све поене на овом потпроблему. Наиме, за сваки чвор i, пролазимо по свим бојама c и по свим суседима. Укупна сложеност је \sum_{1 \le i \le N} \deg(i)^2 = O(N^2). Пробајте видети зашто [Помоћ 3].
Свака тачка је повезана са највише 10 других тачака.
Приметимо да највећа боја коју било који чвор може имати није никада већа од његовог степена. Уколико знамо да највећи степен никада не премашује 10, тада трећа димензија dp табеле има највише 10 колона. Решење из претходног потпроблема сада ради у сложености N \cdot d^2, где је d \le 10 највећи степен у стаблу.
Решење за све поене
Идеја из претходног потпроблема биће корисна и у овом потпроблему. Уколико за сваки чвор i направимо трећу колону dp табеле да буде величине \deg(i), тада ће укупна величина ове матрице увек бити линеарна по N. Такође, приметимо да за сваки чвор можемо одредити да ли ће бити истобојни, разнобојни или шарени наследник за боју c одмах након што смо израчунали све вредности његове dp табеле. Претпоставимо да сваки чвор садржи информацију о броју наследника сваког од три могућа типа за сваку од могућих боја. Када за неки чвор одредимо ког је он типа, једноставно можемо ажурирати бројач његовог родитеља у стаблу за сваку боју c. На тај начин, родитељ може у константној временској сложености одредити за сваку од боја колико има наследника ког типа па самим тим и која је dp вредност за ту боју.
Joш једно интересантно решење
Приметићемо да боје које су могуће за сваки чвор јесу само оне од 1 до \sqrt{N}, као и од N - \sqrt{N} до N. Пажљиво имплементирано решење потпроблема када је степен највише 10 и коришћење ове идеје било је довољно за све поене на овом задатку.
[Помоћ 1]: Посматрајте дељивост са 3.
[Помоћ 2]: Користите неједнакост између аритметичке и геометријске средине.
[Помоћ 3]: Колики је збир степенова свих чворова?
[Помоћ 4]: Шта се дешава ако важи да боја неког чвора није у том опсегу? Колико он има истобојних наследника и колико они укупно имају истобојних наследника?
Смештај
Аутор: Алекса Милисављевић
Текст и тест примери: Алекса Милисављевић
Тестер: Владимир Миленковић
Текст решења: Алекса Милисављевић
Подзадатак 1: N,M, Q \leq 500
У овом подзадатку довољно је симулирати решење, тако што ћемо у сваком упиту проћи кроз свих n особа и за сваку особу проверити која је слободна соба са најмањим индексом. Сложеност: O(NMQ).
Подзадатак 2: N,M \leq 1.000, Q \leq 20.000
У овом подзадатку можемо да радимо сличну симулацију, као и у претходном, само што ћемо у “std::set” убацити све слободне собе и потом за сваку особу изабрати или њену резервацију (уколико је има и мања је од првог елемента сета) или најмањи елемент у сету. Уколико изаберемо елемент из сета, избацујемо га, а убацујемо резервацију (уколико је има). Сложеност: O(QN \log M).
Подзадатак 3: N,M \leq 1.000, Q \leq 200.000
У овом подзадатку можемо да радимо сличну симулацију, али тако што ћемо, уместо чувања скупа слободних соба, у сваком тренутку памтити показивач на последњу слободну собу. Сложеност: O(QN).
Коју собу ће изабрати особа X?
Лема: Првих X особа ће попунити првих X нерезервисаних соба, уколико само посматрамо собе које су резервисале особе после особе X.
Ова лема се може лако показати индукцијом и раздвајањем на случајеве да ли је особа X+1 резервисала собу и где се та соба налази у односу на последњу заузету собу. Сада лако видимо да ће особа X да изабере или X-ту слободну собу, уколико посматрамо резервације соба после особе X или собу коју је она резервисала (ако је има). Одавде видимо и да ће за сваку особу увек бити бар једна слободна соба, тј. одговор никада неће бити -1.
Подзадатак 4: N,M,Q \leq 300.000, X_i \leq 30
У овом подзадатку је довољно за сваку собу запамтити која особа ју је резервисала. Потом у упиту за U_i \leq 30 симулирамо одабир собе као у подзадатку 3, а за преостале проверимо колико соба су резервисале особе са индексима већим од U_i. Сложеност: O(Q \max X_i).
Подзадатак 5: N,M \leq 8.000, Q \leq 300.000
За овај подзадатак је потребна структура података 2д сегментно стабло у којем памтимо за интервал особа [l,r] и интервал соба [x,y] колико соба из тог интервала није резервисала ни једна особа из интервала [l,r]. Потом бинарно претражујемо по решењу најмање t, тако да у интервалу [1,t] има бар U_i нерезервисаних соба, уколико посматрамо резервације особа из интервала [U_i + 1, N]. Сложеност: O(Q \log N \log^2 M).
Подзадатак 6: N,M \leq 100.000, Q \leq 100.000
У овом подзадатку користимо исту идеју као и у претходном, али због великог броја особа и соба, морамо да користимо имплицитно 2д сегментно стабло. Сложеност: O(Q \log N \log^2 M).
Подзадатак 7: N,M \leq 300.000, Q \leq 300.000
У овом подзадатку оптимизујемо идеју из претходног задатка. Наиме, можемо да приметимо да нам је \log од бинарне претраге вишак и да можемо да се “шетамо” по имплицитном 2д сегментном стаблу. Ово радимо тако што запамтимо скуп сегментних стабала која се односе на особе после особе U_i и потом у се у њима шетамо тако што пронађемо суму бројева слободних соба у левом подстаблу сваког. Уколико је та сума већа или једнака са k = U_i, онда идемо у то подстабло у сваком стаблу из скупа, у супротном идемо у десно и од k одузмемо суму из левих. Сложеност: O(Q \log N \log M).