Новинарски форум

Първо състезание

Първо състезание

от Мартин Тошев -
Number of replies: 1

   Здравейте, колеги,
   Тази неделя от 10:00 във ФМИ ще се проведе първото състезание за практикума по Дизайн и Анализ на Алгоритми. За състезанието ще се използва системата maycamp (http://judge.openfmi.net:9280).  Там има и задачи за подготвка от минали години (също и в http://arena.maycamp.com/). 
Допълнителни материали за подготовка:

  • (C++/STL) http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html#DownloadingTheBook
  • (topcoder tutorials) http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static
  • (informatika.bg) http://www.informatika.bg/index.php?page=info&topic=MAIN 


Както говорихме в събота от 10 до към 13-14 в някоя от компютърните зали ще направим warm-up, на които да изчистим всякакви проблеми, на които сте се натъкнали (С++, използване на IDE, алгоритми, структури и задачи) в хода на решаване на задачи (за целта се очаква да сте позапознати с основните класове и функции от STL, както и с алгоритмите до момента). На самото състезание ще може да използвате и лични лаптопи. Спорна подготовка.
   Поздрави,
   Мартин

 

 

In reply to Мартин Тошев

Re: Първо състезание

от Мартин Тошев -

   Поздравления за усилието на всички. Тестовете на задачите са качени в муудъл, ако някой иска да си тества допълнително решението. Кратки решения на задачите:

1) Палиндром - пазите си броя на всяка една буква от низа в масив (с размер 26 елемента), при което ако може да се построи палиндром, то не повече от 1 буква може да се среща нечетен брой пъти (и ако има такава - тя стои по средата на палиндрома)

2) Дървета - двоично търсене по отговора на задачата (между 0 и достатъчно голяма стойност) - в хода на двоичното търсене проверявате дали средния елемент удовлетворява условието на задачата. Трябва да се направят две двоични - съответно за растяща/намаляваща редица

3) Салса - сортирате мъжете и жените в два отделни масива с count sort още при четене и накрая прилагате процедурата от merge sort за сливане на две сортирани последователности,за да намерите търсения резултат. 

4) Бързане - обхождане в ширина, при което за всеки наследник на текущо обходения връх присвоявате родител и минимален път до него от първоначалния. Обхождането приключва когато върха N стане текущ. Задачата, разбира се, може и да се реши с модификация на Дейкстра.

5) Минимален път в граф - директно Флойд-Уоршал, след което заявките се изпълняват за константно време.

Поздрави,
Мартин