Автор |
SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 09:16 |
|
|
Цього року вже вдруге півфінал світу проходить паралельно на двох сайтах - Вінницькому та Бухарестському. У змаганнях приймають участь аж 5 львівських команд. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 09:26 |
|
|
Офіційний сайт змагань http://acm.ro/ |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 10:19 |
|
|
Поточні результати https://olimp.vntu.edu.ua/standings |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 10:28 |
|
|
Найпростішою видається задача С, яку вже розв'язали 26 команд. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 10:34 |
|
|
У задачі С дано стрічку з числами від 1 до 2^K (K = 21) та необхідно виконати 21 згортань, в результаті чого числа будуть розташовані одне поверх іншого. Як результат потрібно вивести верхніх 1024 числа.
Власне через невелику кількість чисел, що необхідно вивести, задача є досить простою. Ми можемо працювати з тією частиною стрічки, яка буде зверху, якщо проаналізувати операції, починаючи з останньої. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 10:36 |
|
|
Через 35 хвилин змагань 4 команди розв'язали по 4 задачі. Львів'яни поки мають тільки по одній. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 10:42 |
|
|
Задача І: Дано дерево (до 50000 вершин) зі зваженими ребрами. Для кожної вершини необхідно знайти найбільшу відстань до деякої іншої вершини.
Задачу можна розв'язати знайшовши найдовшу та другу найдовшу відстань від вершини до листка (відстань вниз) та рекурсивно обрахувавши відповіді для кожної вершини (знаючи найдовшу відстань через батька - відстань вверх). |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 10:42 |
|
|
Дві команди КНУ мають по 3 задачі. Досить хороший темп на початку змагань. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 10:55 |
|
|
7in4es здають другу задачу та поки займають 10 місце в загальному заліку. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 11:00 |
|
|
У попередньому повідомленні "задача С" потрібно читати як "задача Е", яка не є найпростішою, тим не менше не видається дуже складною. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 11:01 |
|
|
За годину на верхівці турнірної таблиці команда КНУ з 4 задачами. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 11:09 |
|
|
Задача G: Є n (до 10000) послідовних моментів часу. В кожен момент міфічний герой задача Джо може купити довільну кількість ензиму, з якого він готує ліки. Термін придатності ензиму h (< 10000) моментів. Також для кожного моменту відома ціна одиниці ензиму. У кожен момент Джо має прийняти одиницю ензиму для якого ще не вийшов термін придатності.
Задачу можна розв'язати аналізуючи ціни ензиму починаючи від найдешевшої. Тоді для всіх ще вільних моментів де цей ензим ще буде придатним до вживання ми купуємо даний ензим. Технічна реалізація може буде здійснена на основі системи множин, що не перетинаються. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 11:13 |
|
|
Задача С: Необхідно знайти кількість простих чисел на інтервалі [n, m] (n < m < 10,000,000). Розв'язується звичайнісіньким решетом Ератосфена. Найпростіша задача змагань. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 11:14 |
|
|
Лідери змагань мають 5 вирішених задач. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 11:17 |
|
|
Команди ЛНУ;
7in4es - 3 problems, 8 place
Almost_The_Elephants - 1 problem
Tuck_Yeah! - 1 problem
Команди політехніки:
NULP_Prime - 1 problem
Liberior - 0 problems |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 11:34 |
|
|
B: Є послідовність 2*n (n <= 100,000) чисел. Якщо два числа стоять поруч, вони зникають, а послідовність природні чином звужується. Вам дозволяється міняти місцями сусідні числа. Необхідно визначити мінімальну кількість операцій необхідну для знищення усієї послідовності.
Очевидно, якщо одне з чисел Х стоїть між числами Y, а інше є назовні інтервалу (тобто ми маємо щось на кшталт ...Y...X...Y...X...), то ми маємо витратити одну операцію для того щоб поміняти X та Y місцями. Отже нам потрібно порахувати кількість таких пар. Очевидно, що знайдена кількість буде достатньою та оптимальною.
Зробити вищесказане можна наступним чином. Для кожного числа (скажімо X) потрібно порахувати кількість таких Y, що тільки один Y розміщений між двома X. За допомогою двох дерев відрізків ми можемо легко обчислити суму за час O(n*log(n)). |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 11:43 |
|
|
Перші три місця поки займають команди КНУ, зробивши 6, 5 та 5 задач відповідно. |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 11:57 |
|
|
А: Маємо граф з n (n <= 10000) вершинами та послідовність ступенів (кількість ребер інцидентних до кожної з них). Кожен елемент послідовності не перевищує 1000. Потрібно побудувати довільний граф, що задовольняє таким умовам, або встановити, що такого не існує.
Алгоритм Hakimi та теореми угорця Erdos стануть в пригоді. Оберемо вершину з найбільшим ступенем інцидентності та ставимо ребра до наступних з найбільшим ступенем вершин. Якщо подібна побудова завершиться успішно, то ми отримаємо результат, інакше відповіді не існує.
Орієнтовна кількість необхідних обчислень n*log(n) + 1000*n;
Змінив(ла) Shef, 13-10-2012 14:28 |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 11:59 |
|
|
Дві години змагань позаду.
7in4es займають 10 місце, маючи 4 задачі у своєму доробку (B, C, G, I). |
|
Автор |
RE: SEERC 2012 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
Опубліковано 13-10-2012 12:14 |
|
|
D: Дана таблиця маршрутизації мережевого обладнання та набір запитів. Кожен запис у таблиці - це маска та довжина префікса. Для кожного запиту потрібно визначити запис з найдовшим префіксом, що співпадає. Досить оригінальним є відсутність обмежень, хоча в умові сказано "a few milion packets".
Розв'язати задачу можна побудувавши дерево на основі таблиці маршрутизації та обирати найглибшу відповідну вершину для кожного запиту. Складність є лінійно залежною від кількості записів у таблиці та кількості запитів. |
|