| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 12:19 |
|
|
Penguins - 5 задач, 4 місце
Hallo_World - 4 задачі, 17 місце
FiredUp - 3 задачі, 19 місце |
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 12:20 |
|
|
|
Успішно здані задачі: A, C, D, E, F, H, J. |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 18-10-2014 12:31 |
|
|
LNU Penguins вириваються на перше місце здавши задачу J!
Не помиляється той, хто нічого не робить! |
  
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 12:49 |
|
|
Задача I:
Є дві програми, що складаються з ni <= 1000000 iнструкцій.
Також є m <= 10 компютерів.
Для кожної інструкції кожної програми та кожного компютера
відомий час її виконання на цьому компютері.
Для кожної програми наступна інструкція не може бути запущена
поки на завершиться попередня.
Інструкції програми можуть бути виконані на різних компютерах.
Необхідно знайти мінімальний час завершення обох програм. |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 18-10-2014 12:50 |
|
|
Задача G:
Дано граматику з правилами формату A->BC і A->a. Великі літери - нетермінальні символи, маленькі - термінальні. Також дано одну стрічку довжиною до 1000. Треба сказати чи ця стрічка може бути згенерована правилами граматики починаючи з символа S.
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 12:52 |
|
|
Задача B:
Задано циклічну стрічку довжини n <= 100000 з цифр 1-9.
Необхідно розбити її на k <= n шматків так
щоб найбільше число утворене ними було мінімальним. |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 12:52 |
|
|
|
На даний момент незайманими залишаються задачі G та I. |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 18-10-2014 13:05 |
|
|
Вже у 4 команд по 6 задач.
Перші три команди одна від одної на відстані одного штрафа (20 хвилин).
LNU Penguins на третьому.
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 13:09 |
|
|
За дві години до закінчення змагань:
Penguins - 7 задач, 1 місце
FiredUp - 4 задачі, 11 місце
Hallo_World - 4 задачі, 21 місце |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 18-10-2014 13:10 |
|
|
Неймовірно!
LNU Penguins та Flawless одночасно (2:51) здають по задачі і у обох команд зараз по 7 задач. Більш того, у них ще й однаковий штрафний час (635)!
Надзвичайно напружена боротьба за перше місце!
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 18-10-2014 13:14 |
|
|
Скріншот таблиці на 2:51: http://acm.lviv.ua/fusion/images/2_51_tie_for_the_first_place.png
Не помиляється той, хто нічого не робить!
Змінив(ла) Ostap, 18-10-2014 13:18 |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 13:32 |
|
|
Задача B (розвязок):
Нехай x = (n - 1)/k, z = n - x*k;
Тоді оптимальний розвязок буде містити
z стрічок довжини x+1
та k - z стрічок довжини x.
Побудуємо суфіксний масив
та організуємо бінарний пошук по найбільшому префіксу,
що формуватиме число з x+1 цифри.
Для кожної ітерації бінарного пошуку
ми перебираємо суфікси зліва направо
і для кожної остачі від ділення на х
зберігаємо найбільшу кількість чисел довжини х+1
яку ми можемо накопичити.
Якщо вийде зібрати принаймні z таких стрічок
то наше припушення бінарного пошуку було вірним.
|
|
|
| Автор |
RE: Southeastern European Region 2014 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 18-10-2014 13:41 |
|
|
Поки що лише одна команда (з низу таблиці) здала задачу G.
В задачі не уточнено скільки всього правил в граматиці, але ідея розв'язку швидше всього полягає в тому, що для кожної підстрічки потрібно визначити з яких нетермінальних символів вона може бути отримана - всього це 26*1000*1000/2 підзадач максимум. Щоб розв'язати одну з підзадач (символ X, підстрічка з i до j), потрібно перебрати всі поділи підстрічки на дві і спробувати застосувати до кожного поділу всі правила, які починаються з символа X.
За відсутності обмежень на кількість правил в тесті, максимальна кількість переходів - <довжина підстрічки>*26*26 - це досить багато, враховуючи, що можливих станів 13*10^6. Але, мабуть, варто відштовхуватися від того, що правил насправді не багато і просто ітерувати по правилах відсортованих по лівій частині.
Не помиляється той, хто нічого не робить!
Змінив(ла) Ostap, 18-10-2014 13:43 |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 13:48 |
|
|
За 90 хвилин до закінчення:
4 команди мають по 7 задач.
Penguins на першому місці.
Єдиною незданою залишається задача I. |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 18-10-2014 13:55 |
|
|
Оце так боротьба!
Дві команди зараз ділять перше місце, а інші дві - третє. Я ще такого не бачив!
http://acm.lviv.ua/fusion/images/3_37_tie_for_1-2_3-4.png
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 14:05 |
|
|
|
FiredUp здали задачу J та знаходяться на 13 місці. |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 14:07 |
|
|
|
Penguins здають задачу B та зміцнюють блокпост на вершині турнірної таблиці. |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 14:20 |
|
|
За годину до закінчення:
Penguins - 8 задач, 2 місце
FiredUp - 5 задач, 14 місце
Hallo_World - 4 задачі, 24 місце |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 14:24 |
|
|
|
Penguins здають задачу G та повертають собі перше місце. |
|
|
| Автор |
RE: Southeastern European Region 2014 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 18-10-2014 14:28 |
|
|
Майте на увазі, що інформація щодо
кількості зданих задач
є досить секретною та не відображається
у замороженій турнірній таблиці.
Проте джерело є надійним
та ексклюзивно надає інформацію
для користувачів нашого сайту. |
|
|
Birthday(s):
