Това са идеи за решаването на част от задачите, които сме разглеждали в часовете предложени от един колега, водил курса минали години:
·
Drinking
Game – приложение на HeapSort. Можете да решите задачата за 100 точки и с
използването на priority_queue.
· PermSwap – намиране броя на инверсиите в масив – приложение на MergeSort.
· Бързо Сортиране – задачата се решава с използването на някой от бързите алгоритми. Моят съвет е да пробвате да я решите и с бавните алгоритми за сортиране, за да видите колко по-бавно се държат те с толкова голям вход.
· contest_id=83 – задача, подобна на Шоколади. Разликата е, че тук трябва да използвате някое от бързите сортирания.
График – това е малко по-трикова задача, чието решение на пръв поглед не изглежда особено интуитивно. Решава се като първо всяко събитие се сортира в нарастващ ред по край (забележете – „край‘) и, ако 2 събития имат еднакъв край, се сортират по начало. След това започваме от първото събитие - вземаме го и гледаме следващото, ако то не се засича с предното, вземаме и него, ако се засича, не го вземаме и продължаваме напред по същия начин.
· contest_id=40&problem_id=124 – задачата се решава с директно прилагане на Counting Sort
· contest_id=98&problem_id=314 – намиране на K-тия по големина елемент с Quick Select
· contest_id=85 – Evil – задачата има подобно решение на задачата График.· SysAdmin - задачата се решава с Binary Search по отговора. В какви граници може да бъде нашият отговор? Т.е. какви са минималните и максималните възможни дължини за тези поне K парчета кабел с еднаква дължина? Минималната възможна дължина за всяко от тези парчета е 1 (=left), а максималната е 100,000,000 (=right) (може вместо 1*10^8, да ползвате дължината на най-дългото парче кабел от входа, но така ще направите линейно повече операции, за да го намерите). Имайки този range от възможни отговори, правим Binary search в него. На всяка стъпка хващаме mid = (left+right)/2, като след това, линейно по входните парчета кабел, проверяваме колко парчета кабел с дължина mid можем да изрежем от тях. Ако се получава < K, трябва да намалим дължината (за да се увеличи бройката) и съответно right = mid-1. Ако се получава >= K, запомняме текущия отговор (mid) и пробваме с по-голяма дължина, т.е. left = mid+1. Update-ваме mid, т.е. mid = (left+right) / 2, и повтаряме същите стъпки докато left <= right. Накрая печатаме отговора.
· contest_id=85&problem_id=265 – типична задача за двоично търсене. В задачата има нещо, което липсва и това е
колко най-малко може да бъде някое от тези N числа. Приемете, че може да е най-малко 0, не съм
гледал тестовете, но с 0 начална стойност за left в двоичното минава. Решението с двоично е
следното: правим двоично по L, т.е. в началото left = 0, right = 2000000, защото възможните стойности за L са в интервала [0, 2000000]. Пробваме със средата, т.е. mid = 1000000, ако стане, ни интересува дали ще се удовлетвори условието в
задачата при left = mid+1,
ако не стане, right=mid-1. Ако стане, пробваме дали ще стане с
по-голямо число, защото в задачата се търси максималното L, което удовлетворява изискването да
съществува подредица от K
последователни членa, всеки по-голям или равен на L. Ако не стане, пробваме с по-малко, тъй като е
сигурно, че с по-голямо няма да стане . Проверката дали текущото mid става за отговор на задачата се прави с
линейна сложност по N.
· Сума - В тази задача е важно да забележим малкия брой суми, за които трябва да проверяваме, а именно <= 10. За всяка една сума (sum[i]), проверяваме, във вече сортирания масив от N елемента, дали може да се получи като сбор на 2 елемента от него по следния начин: вземаме първия елемент (a[0]), намираме разликата между сумата и текущия елемент - diff = sum[i] - a[0], и търсим diff с двоично търсене в масива с N елемента, като внимаваме да не счетем, че сме намерили diff, а реално да сме намерили a[0]. T.e. ако sum[i] = 2, а a[0] = 1 и трябва да търсим diff = sum - a[0] = 2 - 1 = 1, трябва да изключим от търсенето a[0].
· Exam – Задачата си заслужава поради няколко причини: първо – не се търси явно минимум или максимум, а бройка; второ – трябва добре да се помисли относно граничните случаи, тъй като в нея ограниченията са доста големи. Решението на задачата е следното: Правим двоично търсене от F (=left) до 10^9 (=right), т.е. по факултетните номера. За всеки mid (това е някакъв ФН) гледаме каква е сумата на аритметичната прогресия от F до mid (разликата на арит. прог. в тази задача е 1). Ако сумата стане по-голяма или равна на N, тогава запомняме стойността на mid (само ако има нужда, т.е. ако намерената стойност за mid е по-малка от досега намерената) и update-ваме десния край на интервала, т.е. right. В противен случай update-ваме левия край на интервала, т.е. left. Продължаваме докато left <= right (ако работим с интервал затворен от двете страни). Крайният ни отговор е запомнената стойност на mid минус F плюс 1.