| Автор |
RE: SEERC 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 22-10-2016 12:48 |
|
|
|
Також обмеження задачі І (напевно робити потрібно саме її) |
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 12:53 |
|
|
В даний момент Володя пише якусь задачу, тоді як Андрій і Тарас обговорюють. Цікаво, яку задачу вони обрали наступною? Можливо С?
Змінив(ла) Witaliy, 22-10-2016 12:53 |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 12:59 |
|
|
Команда алготестерів забезпечені новими фірмовими футболками Алготестер:
Футболки є в різних варіаціях логотипу icpc, це тільки одна з них.
Змінив(ла) Witaliy, 22-10-2016 12:59 |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 13:01 |
|
|
Репортер Віталій відправився на місце подій зробити актуальні фотографії команд під час контесту.
Змінив(ла) Witaliy, 22-10-2016 13:02 |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 13:11 |
|
|
Змінив(ла) Witaliy, 22-10-2016 13:14 |
|
|
| Автор |
RE: SEERC 2016 |
MoRZe
Користувач
Повідомлень: 200
Звідки: LNU
Зареєстрований: 05.12.09 |
| Опубліковано 22-10-2016 13:21 |
|
|
VVT здають задачу I і піднімаються на 16 позицію в турнірній таблиці.
_______47____
Змінив(ла) MoRZe, 22-10-2016 13:22 |
 
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 13:31 |
|
|
|
Алготестери здали С, зараз вони посідають 2 місце! |
|
|
| Автор |
RE: SEERC 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 22-10-2016 13:37 |
|
|
|
Алготестери - єдина команда, що зробила задачу J! |
|
|
| Автор |
RE: SEERC 2016 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 22-10-2016 13:38 |
|
|
|
Це дає їм надію на перемогу. |
|
|
| Автор |
RE: SEERC 2016 |
Deretin
Модератор
Повідомлень: 13
Звідки: ЛНУ
Зареєстрований: 07.02.10 |
| Опубліковано 22-10-2016 13:47 |
|
|
А - потрібно покрити точки 3 квадратами однакового розміру. Знайти мінімальний розмір квадрату.
Розв'язок: бінаримо відповідь, далі один з квадратів обов'язково знаходиться в одному з кутів bounding box всіх точок, переберемо цей кут. Далі залишились всі точки, які ще не покриті потрібно покрити двома квадратами. Перебемо ще один кут, в якому розташований наступний квадрат.
Змінив(ла) Deretin, 22-10-2016 13:47 |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 13:52 |
|
|
|
Задача В: Побудуємо бор по всім стрічкам. Зафіксуємо одну стрічку та знайдем відповідь для всіх пар з першою стрічкою рівною зафіксованій. Для цього переберемо всі суфікси зафіксованої стрічки, знайдемо їх в борі, який є деревом. Для всіх вершин піддерева можна відняти довжину зафіксованого суфікса. Отже, закинемо в масив всі відповідні вершини суфіксів, а також других стрічок з пар. Посортуємо за часом входу, і, використовуючи сет, знайдемо для кожної пари максимальну довжину що можна відняти від суми довжин. Складність - O(n log n). |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 13:53 |
|
|
Фото із situation room:
 |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 13:58 |
|
|
|
Наразі Тарас кодить щось - можливо A. |
|
|
| Автор |
RE: SEERC 2016 |
MoRZe
Користувач
Повідомлень: 200
Звідки: LNU
Зареєстрований: 05.12.09 |
| Опубліковано 22-10-2016 14:02 |
|
|
За 15хв до заморозки становище наступне :
Algotesters (2 місце, 6 задач)
VVT (20, 4)
LogyCode (28, 4)
NULP_Nerdasaurus (35, 3)
_______47____ |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 14:02 |
|
|
|
I - потрібно розкласти число N на мінімальну кількість кубів. (N<=4*10^7). Один з можливих розв'язків(не факт, що правильний): для N<=10^6 знайдемо всі відповіді методом динамічного програмування. Далі переберемо 3 найбільших куби так, що залишок був меншим за 10^6. Якщо це все ще не правильно, можна зробити перебір з відсіканнями найбільших значень. |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 14:07 |
|
|
|
Задача Е виглядає доволі стандартно - побудуємо бор по всім заданим стрічкам (32000 вершин), для кожної пари (вершина бору, символ) знайдемо нову вершину бору (наприклад Ахо-Карасіком, можливо можна без нього). Тоді зробимо динаміку - [позиція][вершина бору], як перехід переберемо новий символ і, використовуючи прекальк, перейдемо в новий стан. |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 14:10 |
|
|
|
Алготестери здали А і вийшли на перше місце!!! |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 14:24 |
|
|
Зараз таблиця заморожена. Результати на цей момент:
1. Algotesters (7 задач)
21. VVT (4)
29. LogyCode (4)
Змінив(ла) Witaliy, 22-10-2016 14:24 |
|
|
| Автор |
RE: SEERC 2016 |
MoRZe
Користувач
Повідомлень: 200
Звідки: LNU
Зареєстрований: 05.12.09 |
| Опубліковано 22-10-2016 14:30 |
|
|
Ходять слухи, що розв'язок задачі B, описаний вище отримає WA3.
_______47____ |
|
|
| Автор |
RE: SEERC 2016 |
Witaliy
Користувач
Повідомлень: 300
Зареєстрований: 09.02.08 |
| Опубліковано 22-10-2016 14:37 |
|
|
|
Не розглянуто було випадок, коли одна стрічка є підстрічкою іншої. Такий випадок також неважко покрити, але для цього треба суфіксний автомат - зафіксуємо більшу стрічку, переберемо префікс. Тоді всі вершини на шляху до кореня (по оберненим лінкам) автомату будуть підстрічками. Далі простим деревом фенвіка можна для кожної пари сказати чи є одна підстрічкою іншох. |
|
|
Birthday(s):
