Зимова школа з програмування, день 3
День розпочався, як і більшість попередніх: з пісні Circle of Life з бродвейського мюзиклу, яку швидко припинило вимикання сигналу будильника в мобільному:-) Та й ця ніч була тепліша завдяки підвищенню температури труб через прийдешні морози.
Лекція розпочалася з «відпалу» львівської команди, капітан якої був автором цього дня.
Усе почалося з представлення «перекладача», який в основному перекладав завдання з місця на місце, але на лекції він перекладав капітана команди з української англійською для гостей з Грузії та Росії. Після веселої промови, що супроводжувалася перекладом, було оголошено, що задачі будуть дуже легкі й лекції з алгоритмів не буде. Але цінну інформацію для багатьох учасників змагання було надано — на дошці написали, як у Сі відкрити файли для читання й запису. Наша команда погодилася, що ця лекція виявилася кориснішою за попередню. Під кінець виступав тренер грузинської команди, який вручив усілякі дипломи тій самій команді з міста лева, яка на у них на змаганнях посіла перші місця, але не встигла забрати документи, що це підтверджують.
На самих змаганнях було дано 7 задач різної складності, в умовах яких розповідалося про кумів, сало й горілку. Звісно ж, усі умови були державною мовою. Це рішення пройшло краще, бо хоча б деякі задачі частково розв'язали — дві завалювалося на 11-му тесті, а одна чи парочка на першому чи другому. У підсумку результат той самий, шкода, що дають очки лише за проходження програмою всіх тестів, а не за кожне проходження одного з тестів, як на решті змагань.
Про задачі писати не буду, відзначу лише моменти, які варто було б знати. Найбільше часу я витратив на задачу, яку треба було розв'язувати Угорським алгоритмом, тепер усе ж треба з ним розібратися. Так само не вистачало знань формул комбінаторики й спрощення формули, що складається з факторіалів. Одну задачу треба було розв'язувати добутком матриці в степені на вектор, ну і задачі на роботу з графом не обійшлося. Потрібні були знання властивостей рядів і робота з трійковою системою числення для однієї задачі.
На розборі розв'язання задач було розказано методи їх розв'язання, але частина рішень посилалася на «загальновідомі» алгоритми та властивості, а частина рішень була представлена найскладнішими способами. Загалом, після дорозв'язування той самий результат, але, схоже, що рейтинг цього дня дуже схожий на рейтинг попереднього — лише в перших 22 команд є якісь результати, не рахуючи бали за дорозв'язування, бо їх не запам'ятовував. Але ще підбиття підсумків не почалося, наступний абзац наберу під час їх оголошення.
Згідно з нагородами, перемогла команда з університету ім. Шевченка. Найкращим розв'язанням задачі й найшвидшим виявилося розв'язання четвертої задачі, про горілку, зробила, хоч як це дивно, команда Львівського національного університету ім. І. Франка. Автор задачі, за сумісництвом тренер і капітан цієї команд, відзначив, що здивований, звідки взялося настільки оригінальне й швидке розв'язання.
Поки що ясно, який день претендує на звання найвеселішого.
Редагувалося 22.02.2008