Segment trees, lazy propagation

Ако има една структура што не ја знаете, а мора да ја научите, тоа е segment tree

За време на подготовките пред регионалниот ACM натпревар во Романија, ова беше муабетот што го слушнавме најмалку 5 пати во рок од саат време. Деновиве ја обработивме структурата по предметот алгоритми и сложеност, при што имав шанса да спремам неколку задачи за лабораториските вежби. Со тоа, би ја искористил шансава да направам поопширен пост за segment trees, кој би бил корисен и на тие што никогаш ја немаат сретнато оваа структура. Подоцна во постот ќе ги објаснам двете задачи кои ги спремив за лаб.

Алгоритми и сложеност – Шахистот Беџо

Задачава ме мачи уште од националниот ACM натпревар кој беше одржан уште во септември, кога остана нерешена по повеќе од 10 погрешни решенија пратени од повеќе тимови. Уште од кога ја видов задачата на лабораториските вежби знаев дека е нерешлива за нас (фактот дека повторно не добив никаква идеја по скоро саат размислување го потврди тоа), но по доста гуглање и анализирање на решенија успеав да ја разберам идејата за да ја решам. 

Мендо – Училишен натпревар 2016

Бидејќи започнав традиција со минатогодишните натпревари, ќе продолжам и оваа година да постирам објаснувања за задачите од натпреварите на Мендо, повторно почнувајќи со училишниот натпревар.

По некоја слободна проценка би рекол дека овогодинешниов училишен натпревар беше полесен од оној лани, највеќе поради 5-тата задача која сега е делумно полесна (но бараше од вас да забележите нешто). Сепак имаше простор за грешка во другите задачи (посебно втора и трета) каде што погрешно сфаќање на задачата може да ви изгуби солиден број поени. Без да одолжувам повеќе, да преминам на самите задачи…

Тест за пракса во Microsoft

Благодарение на Ненад Божидаревиќ (инаку и една од причините зошто го започнав овој блог) открив дека Microsoft имаат свои канцеларии во Белград, Србија, каде што работат на Microsoft Office пакетот, Bing и SQL Server. Уште поинтересно е тоа што нудат пракси за студенти во регионот, што е одлична прилика за било кој талентиран програмер што би сакал да работи како софтверски инженер.

Аплицирав за летна пракса со CV во кое има 0 работно искуство и само наброени натпревари на кои сум учествувал. Недела дена подоцна, добивам покана за тест каде што се поканети ~100 кандидати (некои од нив пријавени за full time работа, не за пракса). Во продолжение ќе ги наведам моите впечатоци од тестот.

Предизвик по Веројатност и Статистика

За сите кои не слушаат веројатност / не студираат на ФИНКИ, се работи за оваа задача (потребно е да се логирате на мендо)

Да дефинираме состојба како даден момент во кој имаме проверено неколку компјутери и за нив знаеме која верзија ја имаат. Формално, состојба можеме да дефинираме како функција f(x,y) каде што x ни означува колку компјутери од тие што сме ги провериле ја имаат новата верзија а y ни означува колку компјутери од тие што сме ги провериле ја имаат старата верзија. За секоја дадена состојба f(x,y) знаеме дека имаме проверено вкупно x+y компјутери.

Codeforces Round #316

Конечно назад во прва дивизија. Интересен натпревар со уште поинтересни задачи и многу хакирање. Успеав да ги решам првите 3 задачи и да извадам додатни 750 поени со хакирање што ме стави на 43-тото место, едно повисоко од мојот најдобар резултат (44-то). За жал покрај септемвриската испитна сесија немам време да ги решам останатите две задачи, така да на кратко само ќе ги објаснам првите 3 задачи кои ги решив. 

Dijkstra со priority queue

Како што спомнав минатиот пост, алгоритмот на Dijkstra е (според мене) еден од основните алгоритми кој се користи за натпреварување. Најчесто научен како алгоритам со O(N²) сложеност, Dijkstra е перфектниот алгоритам за наоѓање на најкраткиот пат во граф со тежини од едно теме (изворот) кон сите други темиња во графот. Но што се случува кога N е многу голем број?

Последниот Codeforces натпревар имаше задача со граф од 100,000 темиња. O(N²) сложеност би резултирало во 10 билиони операции во најлош случај, што е премногу за да се изврши во 2 секунди. Во такви околности алгоритмот на Dijkstra можеме да го оптимизираме со priority queue, намалувајќи ја сложеноста на O(N*logN), што би резултирало во помалку до 2 милиона операции за истиот граф. Огромна разлика.

Во продолжение ќе ја разгледаме задачата и ќе објаснам како најлесно може да се искористи оваа оптимизација.

Codeforces Round #Pi

По долга пауза (некој вид на летен распуст) повторно започнувам со онлајн натпревари. Првиот на листа е 314-тиот Codeforces натпревар, посветен на бројот Пи. Како за натпревар организиран од учесник од втора дивизија, натпреварот беше прилично лесен и не бараше познавања од некои алгоритми надвор од стандардните (стандардните ги сметам BFS, DFS, Dijkstra, Динамичко, Binary search). Потешките задачи само имаа потежок начин на доаѓање до идејата.

За време на натпреварот успеав да ги решам првите 3 и бев многу блиску до точно решение на задачата D, каде што погрешно бев разбрал дел од задачата. Со тој резултат успеав да стигнам до 212-тото место што ме доближи до првата дивизија уште повеќе. Ова беа моите решенија на првите 4 задачи (задачата E ќе ја објаснам во посебен блог пост).

Најкраток пат во граф со негативни тежини, Bellman-Ford

Доколку не бевте запознаени досега, постои „скриен“ дел на Мендо наменет за ФИНКИ, поточно за предметот Алгоритми и податочни структури (кој се изучува втора година). Таму, покрај лабораториските вежби за тој предмет и неколку предизвици по Дискретна математика, исто така можете да најдете и интересна база на задачи за вежбање алгоритми (динамичко, графови, итн). Решавајќи ги задачите од таа секција наидов на една доста интересна задача за која морав да научам нов алгоритам кој е доста лесен и интересен, па решив да го споделам.

Дрва, Политички Партии (МОИ 15)

Неодамна добив една доста интересна задача за решавање, задачата Политичка Партија од овогодинешните МОИ. При првото читање на задачата, првото решение што ми текна е претставување на партијата како кореново дрво и greedy бришење на темиња (што се испостави да не работи во секој случај). Како и да е, бидејќи порано немав решавано задачи со дрва (или воопшто користено дрва), иако успеав да ја решам задачата само 16/20, искуството со дрва ми се покажа доста корисно. Во продолжение ќе го објаснам моето решение на задачата.