Weekly outline
-
Както знаете заради онлайн обучението намалихме броя на контролните, за това трябва да се промени и скалата. Това е новата скала:
\( \Large{T_{курс}=\frac{T_{контролни}}{4}+\frac{0.8Т_{домашни}}{10}} \)
Съответно оценката се формира спрямо точките ви за курса както следва:
[72т., 83т.] - 3.00 [84т., 95т.] - 3.50 [96т., 107.] - 4.00 [108т., 119т.] - 4.50 [120т., 131т.] - 5.00 [132т., 145т.] - 5.50 [146т., ∞ ) - 6.00
-
Книгата на Келеведжиев за ДП.
-
Няколко задачи за бързо сортиране. Препоръчително е да се пробвате да имплементирате алгоритмите, а не да ползвате вградената функция, за да свикнете с тях.
1) https://judge.openfmi.net/practice/open_contest?contest_id=33
· Drinking Game — приложение на HeapSort. Можете да решите задачата за 100 точки и с използването на приоритетна опашка.· PermSwap — намиране на броя на инверсиите в масив — приложение на MergeSort.
· Бързо сортиране — задачата се решава с използването на някой от бързите алгоритми (ако прецените, можете да се опитате да я решите и с бавните алгоритми за сортиране, за да видите колко по-бавни са те при голям вход).
2) https://judge.openfmi.net/practice/open_contest?contest_id=83
3) https://judge.openfmi.net/practice/open_contest?contest_id=72 — График (*).
4) https://judge.openfmi.net/practice/get_problem_description?contest_id=40&problem_id=124
5) https://judge.openfmi.net/practice/get_problem_description?contest_id=98&problem_id=314
-
Задачи за двоично и троично търсене:
1) https://judge.openfmi.net/practice/open_contest?contest_id=77 — E.Sysadmin.
2) https://judge.openfmi.net/practice/open_contest?contest_id=85 — Sequence.
3) https://judge.openfmi.net/practice/open_contest?contest_id=37 — всички задачи.
5) https://judge.openfmi.net/practice/open_contest?contest_id=10 — Алкохолици.
6) https://judge.openfmi.net/practice/open_contest?contest_id=3 — Exam.
8) https://judge.openfmi.net/practice/open_contest?contest_id=98 — Ферма.
10) https://judge.openfmi.net/practice/open_contest?contest_id=141 - Сортирания и Октопаки11) https://www.hackerrank.com/contests/practice-3-1 - Всички задачи са на тези теми, но обърнете внимание на последните 312) https://www.hackerrank.com/contests/practice-3-sda - Отново всички задачи са на тази теми -
-
-
Кода, който писах на дистанционното упражнение на 20.03 за вградените в stl структури. Кода съдържа кратки примери за използване на основните функции за всяка структура, както и кратък коментар за това какво прави.
-
-
Някой задачи за обхождания в графи:
https://judge.openfmi.net/practice/open_contest?contest_id=12 - задачи Ябълки и Школа
https://judge.openfmi.net/practice/open_contest?contest_id=15
https://judge.openfmi.net/practice/open_contest?contest_id=28 - зад. Рицари
https://judge.openfmi.net/practice/open_contest?contest_id=82 - зад. Още една редица
-
Кодът за обхожданията в графи, който писахме на упражнението на 27.03. Добавих 2та реда за които казах, за да се намери кой връх на каква дистанция е от началния (по брой ребра, в непретеглен граф). Също коментирах всичко (дори повече от колкото трябва), така че да се разбира.
-
-
Някой задачи за минимални пътища в графи:
https://judge.openfmi.net/practice/open_contest?contest_id=55&problem_id=157 - зад. Пътуване
https://judge.openfmi.net/practice/open_contest?contest_id=16&problem_id=39 - зад. Sober
https://judge.openfmi.net/practice/open_contest?contest_id=98&problem_id=316 - зад. Атака
https://judge.openfmi.net/practice/open_contest?contest_id=87 - Денивелация
https://judge.openfmi.net/practice/open_contest?contest_id=102 - Railways
https://judge.openfmi.net/practice/open_contest?contest_id=81 - Lovers
Забележка: Имайте в предвид, че в някой задачи за графи задачата МОЖЕ (но не задължително) да се реши и без да се създава явно графа (т.е ако примерно имате матрица и може да минавате в съседни квадратчета с формула може да изразите номера на съседа и да не създавате списък на съседство). Това се отнася за всякакви задачи за графи като цяло. На това най-често се казва Неявни графи.
-
Кода за алгоритъм на Дийкстра реализиран с приоритетна опашка, който писах на упражнението на 03.04
-
Алгоритъм на Белман форд, който написахме на упражнението на 03.04.
-
-
-
-
Задачи за минимални покриващи дървета:
https://judge.openfmi.net/practice/open_contest?contest_id=55 - Мрежа
https://judge.openfmi.net/practice/open_contest?contest_id=81 - Streets
https://judge.openfmi.net/practice/open_contest?contest_id=102 - space station
https://judge.openfmi.net/practice/open_contest?contest_id=82 - Пътища
https://judge.openfmi.net/practice/open_contest?contest_id=76 - cheating
https://judge.openfmi.net/practice/open_contest?contest_id=60 - Превъртял
http://judge.openfmi.net/practice/open_contest?contest_id=79
http://judge.openfmi.net/practice/open_contest?contest_id=88 - Хипертелепорт
http://judge.openfmi.net/practice/open_contest?contest_id=86 - Поддръжка
-
Кода за алгоритъм на Крускал, който писахме на упражнението на 24.04. Използва dsu с оптимизацията.
-
-
-
-
https://judge.openfmi.net/practice/open_contest?contest_id=63 - pairs
https://judge.openfmi.net/practice/open_contest?contest_id=2 - Разправия
https://judge.openfmi.net/practice/get_problem_description?contest_id=27&problem_id=80 - Beads
https://judge.openfmi.net/practice/open_contest?contest_id=62 - Первази
https://judge.openfmi.net/practice/open_contest?contest_id=30 - пермутации
https://judge.openfmi.net/practice/get_problem_description?contest_id=3&problem_id=7 - caribbean
https://judge.openfmi.net/practice/open_contest?contest_id=82 - джинджърс
https://judge.openfmi.net/practice/open_contest?contest_id=55 - полиноми 2
-
-
-
Това са примерни решения. На някой от задачите има повече от 1 решение, обикновено писани от различни хора.
-