Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 25.05.2019 06:05:37 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
За останніх 4000 років не була одомашнена жодна нова тварина.
Події
ПнВтСрЧтПтСбНд
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31

Birthday(s):
AVATARsquee
AVATARIraMykytyn
AVATARbumblebee
AVATARAndriy_Chervak
AVATARSchulz
AVATAROlehBlashko

Перегляд теми
ACM Контестер | Змагання | ACM SouthEastern European Region
Сторінка 2 з 2 < 1 2
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 11:19
XXL здають третю задачу і піднімаються на другу позицію!!
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 11:25
Анхарди також здають свою третю задачу і тепер посідають щасливе четверте місце.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 11:56
Нам нарешті дали доступ до задач.

С: нескладна динаміка на дереві

Е: сканлайн

В: дивна задача з годинником. Треба порахувати скільки трикутників котрі утворюються кінцями стрілок годинника містять вісь годинника в собі.

К: є два типи операцій: додати прямокутник, або додати точку. Після кожної операції треба порахувати скільки є пар (точка, прямокутник) таких що точка є в середині прямокутника. Можна робити двовимірним деревом відрізків за O(N log^2 N)

І: задано граф який утворюється інверсіями в перестановці. треба знайти кількість множин вершин котрі є одночасно незалежною і домінантною множиною. Такі множини утворюють зростаючі послідовності до котрих не можна додати жодного елемента. Кількість таких послідовностей можна знайти нескладною динамікою.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 11:57
Дві години змагання позаду. Зараз відкрито 5 задач. Команда на першому місці має чотири розв'язані задачі. Дві львівські команди мають по 3 задачі.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 11:58
В задачі F умова суперечить сама собі. В одному місці просять мінімізувати відповідь, в іншому вивести відповідь котра не перевищує 2*N.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 12:08
В задачі F просять преетворити одну послідовність в іншу двома операціями: замінити всі елементи на проміжку на максимум на цьому проміжку, або на мінімум на ньому. Можна помітити два факти: ми не зможемо поміняти відносний порядок чисел в послідовності, а також якщо застосовувати операції довжини 2 то ми можемо будь-який елемент посунути вправо або вліво. Тепер задача просто розв'язується двома вказівниками. Будемо йти по рядку який треба зробити. Поточний елемент можна взяти або зліва, якщо там елемент такий самий. Інакше треба взяти найближчий елемент справа в початковому рядку. Це дасть нам розв'язок котрий використовує не більше ніж 2*N операцій.
Змінив(ла) Andrew_Makar, 20-10-2018 12:12
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 12:35
Задача А: для заданого числа n <= 10^18 треба знайти кількість його розбиттів на суму двох паліндромів.

Є два варіанти: паліндроми мають одинакову довжину, або ні. Якщо одинакову, то можна вважати що ми будуємо один паліндром з цифрами до 18. Будемо будувати паліндроми з кінців. На кожному кроці в нас є два варіанти: або взяти якусь цифру, або її ж + 10. Таким чином треба перебрати 2^9 варіантів.

Якщо в паліндромів різні довжини, то ми знаємо першу цифру довшого паліндрома. Перенесемо її в кінець, і можемо знайти останню цифру другого паліндрому, яку перенесемо на початок, і тепер можемо визначити наступну цифру довшого паліндрома. Таким чином отримаємо ще 2^9 варіантів.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 12:39
Половина контесту вже пройшла. Наразі одна команда здала 5 задач, чотири команди здали по 4 задачі, 15 задач здали по 3 задачі. LNU_XXL і LNU_Unhard мають по 3 здані задачі і посідають 7 і 8 місця відповідно. Остані спроби хлопці робили вже більше години тому, тому слід очікувати що скоро будуть щось здавати.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 12:46
Задача J: в умові описано доволі складний процес перегонів двох персонажів по графу. Треба сказати в скількох місцях один з них може зачітити щоб перемогти. В загальному, нічого цікавого в задачі нема, треба просто уважно прочитати умову і просимулювати процес перегонів, запустивши кілька дейкстр.
Змінив(ла) Andrew_Makar, 20-10-2018 12:49
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 12:58
Анхарди двічі пробували J. Поки безуспішно.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 13:10
Хлопці боряться з задачею J. Треба її здавати і тоді переходити до задачі І, яка виглядає найпростішою з тих що хлопці не здали.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 13:25
https://livestream.com/ACM-ICPC/VNTU2018
Тут анхарди сидять на першому столі і команду добре видно.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 13:29
Анхарди здали І з другої спроби і вийшли на 8 місце! Хлопці вперед!

Зараз Данило дебагає J. Треба її здавати і потім робити ще як мінімум одну задачу щоб виходити на фінал.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 13:53


На фото: команда LNU_Unhard.

Чудеса операторської роботи на трансляції.
Змінив(ла) Andrew_Makar, 20-10-2018 13:54
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Andrew_Makar
Адміністратор

Повідомлень: 69
Звідки: ЛНВК "Школа І ступеня - гімназія"
Зареєстрований: 18.12.07
Опубліковано 20-10-2018 14:01
Задача D: задано зважене дерево. Треба обійти кожне ребро хоча б один раз мінімізуючи сумарну довжину пройденого шляху. Також можна "стрибати" між довільними вершинами з деяким штрафом.

Якщо ми не будемо стрибати то кожне ребро пройдемо двічі. Тепер кожен стрибок може нам зекономити деякий шлях, при чому кожне ребро не може бути зекономлено двічі. Відповідно для розв'язку достатньо для кожної кількості шляхів знайти множину шляхів такої кількості, яка максимізує їх сумарну довжину. Це можна зробити динамікою. Станами будуть вершина, кількість набраних шляхів і чи йде шлях зараз чи ні.
Andrew_Makar Andrew_Makar Надіслати приватне повідомлення
Автор RE: SEERC 2018
Deretin
Адміністратор

Повідомлень: 7
Звідки: ЛНУ
Зареєстрований: 07.02.10
Опубліковано 20-10-2018 14:05
H: Дано орієнтований граф, N вершин, М ребер, потрібно вибрати хоча б M/4 ребра та розфарбувати вершини в 2 кольори так, що вершина чорна тоді і тільки тоді, коли з неї є хоча б одне ребро в білу.

Припустимо, що граф неорієнтований, поділимо його на 2 долі так, щоб між долями залишилось як мінімум M/2 ребер. Це робиться жадно, розглядаємо вершини в будь-якому порядку і додаємо в ту долю, яка додає більше ребер.
Тепер розфарбуємо одну долю в чорний колір, а іншу в білий. Для всіх вершин стає все ок, крім тих чорних вершин, з яких зараз нічого не виходить в білі. Перефарбуємо їх в білий колір і видалимо ребра, які в них входили з білої долі. Зробимо аналогічну штуку, якщо ми свапнути кольори доль. Тепер множини ребер, які видаляються не можуть перетинатись(бо вони напрямлені в різні боки), тому розмір меншої з них <= M/4 і залишиться M/4 ребер.
Deretin RomaWhite[Lviv NU] Надіслати приватне повідомлення
Автор RE: SEERC 2018
Deretin
Адміністратор

Повідомлень: 7
Звідки: ЛНУ
Зареєстрований: 07.02.10
Опубліковано 20-10-2018 14:37
G: Дано табличку 2^n х 2^n, кожна клітинка чорна або біла. Вартість таблички дорівнює 1, якщо вона заповнена одним кольором, інакше розіб'ємо її на 4 частини і додамо їх вартості + 1. За кожну операцію змінюються кольори одного стовпчика або рядка. Потрібно після кожної операції казати вартість таблички.

Порахуємо скільки є квадратів розміру 2^k х 2^k, які однаково заповнені для всіх k (враховуються тільки квадрати на коректних місцях).
Щоб квадрат був однаково заповнений потрібно, щоб всіх його рядки були в однаковому стані і всі стовпці. Тому будемо підтримувати скільки є послідовностей з 2^k рядків, які в однаковому стані і аналогічно з стовпцями. Кількість це просто добуток цих значень.
Так можна кожну операції робити оновленням n значень, адже кожна клітинка належить тільки одному квадрату 2^k х 2^k.
Deretin RomaWhite[Lviv NU] Надіслати приватне повідомлення
Сторінка 2 з 2 < 1 2
Перейти на форум:
Банери
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

настільні ігри

торт

клавіатура, навушники, флешки і т.д.

квитки в кіно

квитки в аквапарк

квитки на пейнтбол

книги

футболки з логотипом змагання

Для участі в голосуваннях Ви повинні залогуватись.
Міні-чат +
Зараз на сайті -
Гостей: 5
На сайті немає зареєстрованних користувачів

Користувачів: 4,396
новачок: aitlanka
Powered by PHP-Fusion © 2003-2006
LNU ACMania © 2004-2011 e-mail: webmaster@acm.lviv.ua
21,747,462 унікальних відвідувачів
Our projects: ACM Contester, _College.
  пїЅпїЅпїЅпїЅпїЅпїЅпїЅ Orphus     bigmir)net TOP 100