Rešenja zadataka sa SIO 2019/2020 - dan 1
Дидо
Аутор: Иван Стошић
Текст и тест примери: Никола Пешић
Тестер: Никола Милосављевић
Текст решења: Иван Стошић
Заједничко за све подзадатке јесте то што треба проверити дужину изломљене линије која има облик као што је описано у задатку. Наиме, нека се та линија састоји од u сегмената дужине 1 и v дијагоналних сегмената дужине \sqrt{2}. Тада, треба да важи u+v\sqrt{2} \leq L односно v \sqrt{2} \leq L-u, тј. 2v^2 \leq (L-u)^2 и u \leq L.
Такође, потребно је да за дату изломљену линију одредимо двоструку површину између ње и x осе. То можемо урадити помоћу методе означених трапеза. За сваки сегмент те дужи, израчунамо површину трапеза који формирају та дуж и две вертикалне дужи које је спајају са x осом. При томе, површину трапезоида узимамо са позитивним знаком ако дуж иде слева на десно, у супротном је узимамо са негативним знаком. За дуж ((x_1,y_1),(x_2,y_2)), та двострука површина износи (y_1+y_2)(x_2-x_1). Површина испод целе изломљене линије једнака је збиру означених површина свих овако добијених трапеза.
У првом подзадатку довољно је рекурзивно изгенерисати све путање дужине до L, a затим проверити да ли оне стижу у циљну тачку и затим израчунати њихову површину.
Други подзадатак се може решити ако се у рекурзију додају неки од следећих услова за рани излазак:
- Ако смо превише удаљени од циљне тачке,
- Ако смо искористили смер дужи супротан од претходне.
Трећи подзадатак се може решити ако приметимо да је решење увек конвексна фигура. Неформалам доказ овог тврђења дат је на самом крају решења. Ово значи да смер у којем се крећемо почиње од “лево”, затим ротира у смеру казаљке на сату и поново се завршава у “лево”. Ово значи да се свако решење може описати са 9 ненегативних целих бројева, који означавају дужине дела пута на којима се крећемо у горе описаним смеровима. Овакви низову се могу пажљиво рекурзивно генерисати и за сваки може да се провери површина добијене фигуре. Временска сложеност решења је O(\binom{L}{9}) = O(L^9), што је довољно, с обзиром на јако малу скривену константу.
Четврти подзадатак се може решити применом динамичког програмирања. Нека је d_{x,y,u,v} највећи збир означених површина трапеза који се може добити неком путањом од (0,0) до (x,y) при чему смо искористили u сегмената дужине 1 и v сегмената дужине \sqrt{2}. Прелази су једноставни, за сваки од осам смерова, повећавамо u или v за један и коригујемо x,y координате, док нову површину рачунамо помоћу формуле дате у другом пасусу. Редослед израчунавања може бити растући по u+v. Коначно решење је максимална вредност d_{W,0,u,v}, где u,v задовољавају неједнакости из првог пасуса. Временска сложеност решења је O(L^4), али са релативно малом скривеном константом.
Пети подзадатак се може решити применом динамичког програмирања са другачијим начином рачунања површине. Да би се смањила сложеност, фигура се може градити са оба краја ограде одједном. Нека је d_{w,u,v} највећа површина фигуре која се може добити неком путањом од (0,0) до (w,0) при чему смо искористили u сегмената дужине 1 и v сегмената дужине \sqrt{2}. За прелазе једна опција је да додамо хоризонтални сегмент дужине 1 на неки крај ограде и тиме повећамо или смањимо w за 1, друга опција је да повећамо y координату на оба краја ограде додавањем сегмената и додамо одговарајућу површину која се добија између та 2 сегмента.
Сви могући прелази из стања d_{w,u,v} су:
- У стање d_{w+1,u+1,v}, на површину се не додаје ништа
- У стање d_{w-1,u+1,v}, на површину се не додаје ништа
- У стање d_{w+2,u,v+2}, на површину се додаје 2*w+2
- У стање d_{w+1,u+1,v+1}, на површину се додаје 2*w+1
- У стање d_{w,u+2,v}, на површину се додаје 2*w
- У стање d_{w-1,u+1,v+1}, на површину се додаје 2*w-1
- У стање d_{w-2,u,v+2}, на површину се додаје 2*w-2
Нама је потребна максимална вредност од ових прелаза.
Редослед израчунавања може бити опадајући по u+v. Коначно решење је d_{W,0,0}. Временска сложеност решења је O(L^3).
Изазов:
Да ли можете да решите задатак у временској сложености O(L^2)?
Доказ:
Нека је (p,q) најкраћа дуж чија унутрашњост цела лежи ван фигуре, док тачке p,q леже на ивици фигуре тј. на путањи. Уколико ову дуж заменимо једном најкраћом путањом (мерено у осмосмерној метрици) која је “испупчена” у односу на дуж p,q, добићемо путању строго мање дужине а фигуру строго веће површине.
Мрачна соба
Аутор: Павле Мартиновић
Текст и тест примери: Павле Мартиновић
Тестер: Алекса Милисављевић
Текст решења: Павле Мартиновић
У овом задатку је потребно избројати све подматрице дате матрице јединица и нула које имају својство мрачне собе. Матрица има својство мрачне собе је да низом потеза где у сваком потезу узмемо 2\times2 подматрицу и променимо сваки број у њој, можемо да доведемо да она садржи само нуле.
Подзадатак 1: N=1
У овом подзадатку, какву год под подматрицу изабрао, није могуће извршити ниједан потез, па је довољно само наћи колико има подматрица са свим нулама. Ово се лако имплементира.
Подзадатак 3: N,M\leq5
Да би се решио овај подзадатак, потребно је приметити да ако решење постоји, постоји и решење где се свака 2\times2 подматрица активира највише једном. Ово важи, јер ако неку 2\times2 подматрицу активирамо двапут, постижемо исти ефекат као да нисмо ниједном. Сада када знамо ово, можемо проверити сваку подматрицу у O(MN\cdot2^{(M-1)(N-1)}), проверавајући све могуће комбинације активираних 2\times2 подматрица. Овиме налазимо решење у O(M^2N^2\cdot2^{(M-1)(N-1)}).
Подзадатак 2: N=2
У овом подзадатку ћемо већ добити осећај како треба да изгледа мрачна соба. На почетку можемо да решимо случај N=1 за обе врсте, као у првом подзадатку и сада нам остају још само подматице које садрже обе врсте. Очигледно да би матрица 2\times P била мрачна соба, не смемо имати ниједну колону са различитим бројевима, јер ће они остати различити и кроз потезе. Стога можемо те подматрице које преостају да гледамо као низ дужине P са јединицама и нулама, где у једном потезу мењамо два узастопна броја.
Приметимо да операцијама мењамо број јединица за -2,0 или 2. Из овога закључујемо да се парност броја јединица не мења кроз операције, што значи да нам низ мора имати парно много јединица да би одговарао мрачној соби. Ово је и довољан услов и то можемо доказати следећим алгоритмом: идемо редом по свим паровима узастопних и уколико је први број један активирамо тај пар у супротном не активирамо. Индукцијом се лако покаже да кад завршимо првих k парова, првих k бројева у низу ће бити 0. На крају знамо да ће нам сви чланови низа, осим можда последњег, бити 0. Међутим како се парност броја јединица није мењала кроз операције, ако смо на почетку имали парно много јединица, последњи члан исто мора бити 0 јер би у супротном имали тачно једну јединицу, што је непаран број јединица.
Када смо нашли услов, само решење се тривијално имплементира.
Како изгледа мрачна соба?
Сада ћемо надоградити доказ из претходног дела на потребан и довољан услов да је матрица мрачна соба за сваку матрицу. Испоставља се да је потребан и довољан услов да у свакој врсти и свакој колони има паран број јединица.
Доказ да је потребан услов је јако сличан доказу малочас. У једном потезу у свакој врсти и свакој колони променимо број јединица за -2,0 или 2, а на крају треба да их је 0 у свакој колони и врсти.
Доказ да је ово довољан услов прати сличан шаблон као претходни такође, али је мало компликованији. Наиме, пролазићемо кроз све 2\times2 редом, кренувши од горњег-левог угла и идући редом по колонама па по врстама (обрадићемо прво целу једну колону, па следећу колону итд). У сваком тренутку ћемо гледати да ли је горње-лево поље наше матрице 2\times2 и активирати матрицу ако и само ако је на том пољу јединица. Опет се индукцијом релативно лако може доказати да ћемо имати нуле на свим позицијама које нису последња врста или последња врста. Међутим, јер знамо да су у сваком реду и свакој врсти број јединица паран, можемо да закључимо да су и на овим пољима нуле, чиме смо завршили доказ.
Подзадатак 4: N,M\leq50
Сада када смо доказали претходно тврђење решење у O(M^3N^3) се природно намеће, где сваку матрицу прођемо и видимо јел испуњава услов. С обзиром на малу константу овог решења, оно је довољно брзо за овај подзадатак.
Подзадатак 5: N,M\leq100
Оптимизација на O(M^2N^2(M+N)) није тешка. Довољно је убрзати проверу матрице X\times Y из O(XY) у O(X+Y). Ово је могуће урадити памћењем префиксних сума у сваком реду и свакој колони и онда вршећи проверу за сваку врсту/колону у O(1) одузимајући две парцијалне суме. Опет због мале константе ово решење је доволљно брзо за овај подзадатак.
Подзадатак 6: N,M\leq 300
Један начин да се овај подзадатак реши је да се претходни подзадатак убрза помоћу “std::bitset”. Алтернативни начин је да фиксирамо горњу и доњу врсту матрице које ћемо да бројимо. Можемо као из претходног подзадатка у O(1) да одредимо које колоне су добре и да то поделимо у класе узастопних добрих колона. Да би све врсте између њих биле добре треба да када срачунамо префиксне суме по модулу 2 треба да дају исти низ. Ово у суштини значи кад заменимо матрицу префиксним сумама по модулу 2 треба да нам се рам поклапа. Да бисмо видели да ли се леви и десни део рама поклапају брзо, могуће је користити хеш који се унапред израчуна. Сада за сваки могући хеш треба видети колко га има да окдговара неком датом блоку узастопних добрих колона. Сада ако за неки блок добрих узастопних имамо X њих који имају дати хеш, треба на реултат да додамо \binom{X}{2}. Да бисмо ово урадили потребно је хешеве поделити у скупове истих, што је најлакше сортом у O(N\log N). Ово нам даје O(N^3\log N) решење.
Подзадатак 7: N,M\leq 500
Решење за овај подзатак је сличан претходном, са једном кључном оптимизацијом. Наиме, поделу колона у скупове коју смо раније радили хешом и сортирањем, ћемо радити структуром података “trie”. Фиксираћемо само доњу врсту, док ћемо горњу померати нагоре за један по један, и све из једног скупа истих префиксних сума пропагирамо низ “trie” раздвајајући их у 1 или 2 скупа. Ово је доста слично сортирању низова путем “radix-sort”. Овако убрзавамо решење на O(N^3), што је довољно брзо за 100 поена.
Метро
Аутор: Душан Здравковић
Текст и тест примери: Димитрије Ердељан
Тестер: Алекса Милисављевић, Павле Мартиновић
Текст решења:
(ускоро)
jel u pripremi resenje?
Evo, samo još lektorisanje da prođe.