Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 16.08.2022 15:58:34 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
Код: ... float x = 1e8; while (x > 0) --x; ... може дати зациклення, використовуйте double. (Це тому, що через малу точність float операція "--x" не змінює x)
Події
ПнВтСрЧтПтСбНд
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):
AVATARAsofix
AVATARMysteryk
AVATARdimaion
AVATARFcdkbear
AVATARMagnentsy

Перегляд теми
ACM Контестер | Змагання | Онлайн змагання
Сторінка 1 з 2 1 2 >
Автор Lviv Training Evening
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 00:06
Тренування на базі acm.tju.edu.cn планують проводитись більш менш регулярно, тому тут будемо обговорювати змагання, задачки і розв'язки та вітати переможців.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
cupidon4uk
Користувач

Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09
Опубліковано 30-04-2010 18:03
хм... У мене шось не заходить... То тільки мені здається, шо там всьо дуж глючить, чи то в всіх ?


GoogleHireMe 557679737 mylyanyk.ivan [Lviv_NU] Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 30-04-2010 18:32
Так, це сайт справді глючить, це вже не преший раз, для заходу на сторінку потрібно декілька раз її обновити (в більшості випадків)
Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 02-05-2010 20:48
Наступне тренування в середу, 5 травня о 19:00 за Києвом. Посилання:
http://acm.tju.edu.cn/toj/vcontest/contest6070.html
Змінив(ла) Witaliy, 05-05-2010 16:37
Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Petya
Користувач

Повідомлень: 5
Зареєстрований: 27.03.10
Опубліковано 06-05-2010 15:49
класні змагання,цікаві задачки, шкода правда що нарроду так мало... класно було би якби хтось писав розбір всіх(або деяких) задач з змагання.
Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 06-05-2010 16:41
напишу розбір задач A, C та F:
A - робиться в лоб, тобто тримаємо масив із значеннями кожної лампки: включена чи виключена. Зміну і запит на відрізку робим простим проходом. Складність О(N*M)

C - Динамічне програмування з використанням бітових масок. нехай dp[i][j] - кількість способів ПРАВИЛЬНО (кожен сусідній відрізняється більше ніж на K) розставити всі що в бітовій масці I, при цьому закінчивши на корові J. Тому перехід буде здійснюватись з поточного стану за допомогою перебору всіх корів, які відрізняються від поточної (J) на більше ніж К і її ще немає в бітовій масці. Очевино, що відповідь буде сума по всіх dp[(2^n)-1][i], де і = від 1 до n. Детальніше про бітові маски тут:
http://acm.lviv.ua/fusion/readarticle.php?article_id=25

складність: O(2^N*N^2);

F - Динамічне програмування. Нехай dp[i] - мінімальна кількість яку можна заплатити за I одиниць ваги. спочатку всі значення dp рівні нескінченості, а dp[0] = 0. Тоді послідновно проходимся по всім пакетам, а для кожного з них пробуємо покращити результат в dp:
якщо dp[i+a[j]] > dp[i]+b[j]то присвоюємо dp[i+a[j]] = dp[i]+b[j]. Пи цьому по dp ми проходимся від першого до останнього, так як кожен пакет ми можемо купляти декілька раз. Також неважко доказати, що
для знаходження мінімального результату, який перевищує H достатньо не більше ніж H*2 (насправді там дещо менше, але в цій задачі це не суттєво). Тому складність розвязку O(H*N)

Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 06-05-2010 16:45
В першій можна просто симулювати - обмеження дозволяють.
В другій проходим весь масив "по черзі", і для кожної клітинки, якщо в неї нема вищих сусідів і вона ще не відмічена, як пройдена - пускаєм з неї ДФС, якщо сусідами з такою ж висотою. Якщо ніде не натрапим на перехід вище, то маєм топ, і +1 до лічильника, інакше до лічильника +0:) Ясно, що всі клітинки, які зачепили при ДФС, відмічаєм, щоб не провіряти ще раз. Складність N^2.
Третя - стандартний перебір. Тільки не факторіалом, а динамікою на бітових масках в стилі Комівояжера.
Четверта - ось цієї з ходу не знаю, є тільки припущення... Вони, мабуть, дуже смішні і далекі від правильних, тому тут озвучувати не буду. пояснення - я вчора контест не писав, бо знову не мав на нього вільного часу. тому сьогодні задачі вперше дивлюсь

П'ята: від кожного моменту, коли треба здати якусь роботу, відраховуємо момент, коли треба почати, щоб встигнути виконати все, що нам потрібно зробити до цього моменту. Вибираємо мінімум з одержаних значень (тобто відповідь для точки, яка в кінцевому результаті і стане причиною того, чому не можна посунути час початку ще трохи). Складність N^2. При більших обмеженнях можна написати бінарник - шукаєм бінарником саму відповідь. Провірка точки - пробуєм виконувати всі дії в жадному порядку, спочатку те, що треба раніше завершити, і дивимось, чи вкладемось. При обмеженні на кінцевий час у нас складність прямує до лінійної (бо, фактично, маємо N*const).
Шоста: я думав, тут найпростіше теж зажаднячити. Тепер бачу, що недобре, краще динамікою, як у Віталія.
Розумію, що трохи занагло писати розбір після першого прочитання і навіть не здававши, тільки за принципами "вона стандартна", "вона свічена" і "я таке колись робив", так що ввечері віднайду трохи часу і поздаю. Спробую поздавати.

===
З.І. Помилки, викликані тим, що задачі читав по разу, і то не всі, трохи повиправляв. Лишив ті частини, за котрі найменш соромно:)

Пішов ще раз читати всі задачі.



Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 06-05-2010 17:09
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
kobra
Користувач

Аватар користувача

Повідомлень: 45
Звідки: НУ "Львівська політехніка"
Зареєстрований: 29.03.08
Опубліковано 06-05-2010 20:25
D. Якщо розглянути вже якийсь небудь готовий остовний граф, то можна помітити, що час потрачений на його проходження рівний:
Подвійний час проходження кожного ребра + Сума(К-сть ребер що входять в точку * час перебування в точці) + Час перебування в початковій точці. Тобто якщо ми отримали якийсь граф, нам вигідно за початкову взяти точку з мінімальним часом очікування.

Граф будується наступним чином. Запускаємо Краскала, але перед тим змінивши ваги ребер. Вага ребра = Вага ребра*2 + час очікування в 1 точці + час очікування в другій точці. Ось і все.
Знаходимо вагу графа+час в мін. точці це і є результат.
newkobra 253273037 Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 09-05-2010 21:23
Наступний контест в середу, 12 травня, в 19:00 за Київським часом.


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Petya
Користувач

Повідомлень: 5
Зареєстрований: 27.03.10
Опубліковано 07-06-2010 16:36
ну і... 3 контести зрбили -- і все?
Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 07-06-2010 18:21
Кожен бажаючий може взяти на себе ініціативу у проведеннні та організації віртуальних контестів на китайському сервері. Це зробити досить просто, а якщо виникають якісь ускладення або потрібна допомога, то звертайтесь.
А краще завжди узгоджуйте зі мною, щоб все було найкраще.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 09-06-2010 18:30
Наступний контест завтра, 10 червня о 19:00. Посилання на змагання:
http://acm.tju.edu.cn/toj/vcontest/contest6246.html
Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
vlyubin
Користувач

Аватар користувача

Повідомлень: 24
Звідки: UW
Зареєстрований: 18.05.10
Опубліковано 09-06-2010 20:49
kruto!:)
Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 21-06-2010 19:12
Lviv Training Evening #11
Заплановано на середу, 23.06 о 19:00
http://acm.tju.edu.cn/toj/vcontest/contest6280.html

Lviv Training Evening #12
Субота, 26.06 о 19:00
http://acm.tju.edu.cn/toj/vcontest/contest6281.html

Успіху!
Змінив(ла) Witaliy, 21-06-2010 19:14
Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 24-06-2010 12:44
Спробую розібрати деякі задачі з контесту #11 :
Задача А: мабуть, саме стандартне динамычне програмування яке існує і яке описане в багатьох книжках. просто тримаєм стан dp[i][j] - максимальна кількість яку можемо набрати і завершити обхід в клітинці (i;j); результат для такого стану буде максимум з результатів для верхньої клітинки і верхньої-лівої.

Задача С: Теж стандартна задача на обхід в ширину. Детальніше про це можна знайти в Інтернеті, але суть така, щоб ми обійшли всі клітики послідовно закидуючи їх в чергу (за ходами коня)

Задача D: Зобразимо міста як вершини орієнтованого зваженого графа, а платні і безплатні дороги - ребра. Припустимо що в кожному місті нам дають -D грошей. тоді безплатне ребро буде мати вагу -D, а платне W[i]-D, де W[i] - плата за ребро. Тоді для того щоб знайти максимальний заробіток ми повинні знайти мінімальний шлях в графі з вериши S до всіх інших. Зауважу, що ребра будуть від'ємні, тому потрібно шукати мін. шлях такими алгоритмами як Форда-Беллмана. Для того щоб взнати чи зможемо ми заробити безлімітну кількість грошей потрібно визначити чи є в графі цикл від'ємної ваги. Це також можна зробити алгоритмом Форда-Беллмана. Цикл від. ваги буде тоді коли після N кроку ітерації щось в масиві відстанів зміниться (зманшиться).

Задача Е: На жаль, я цієї задачі під час контесту не зробив через проблеми з інтернетом, але думаю її можна зробити за допомогою ДП зі станом dp[i,j,k] - де i кількість монет що ми зіьрали вже, j - довжина останнього ходу, k - мій хід це чи ні.


Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 28-06-2010 18:45
Lviv Training Evening #13
Наступне, 13-те змагання відбудеться в середу, 30 червня о 19-00.

Всім успіху, незважаючи на номер змагання! :)
Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 01-07-2010 23:32
Lviv Training Evening #14
14-те тренувальне змагання відбудеться в суботу, 3 липня о 19:00
посилання:
http://acm.tju.edu.cn/toj/vcontest/contest6319.html
Успіху!
Змінив(ла) Witaliy, 02-07-2010 12:20
Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
cupidon4uk
Користувач

Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09
Опубліковано 04-07-2010 20:41
Коли наступні змагання? І чого так рідко організовуються? Зара, поки літо, я б їх щовечора робив... Але не маю доступу до головної сторінки, а форум не всі читають... Дайте мені змогу постити на головній сторінці і я б регулярно з кимось через раз організовував змагання(щоб і мені цікаво було взяти участь)... От... Ну то шо адміни скажуть? =)


GoogleHireMe 557679737 mylyanyk.ivan [Lviv_NU] Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 04-07-2010 21:20
думаю доступу до головної непотрібно, пробуй організовувати i пиши Русланові
Надіслати приватне повідомлення
Автор RE: Lviv Training Evening
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 04-07-2010 21:50
Віталій каже цілком правильно, змагання організовуєш, пишеш на форумі всі деталі і повідовляєш мені, а я вже якусь новинку напишу.
Але це не все.

Ти маєш "доступ" до головної сторінки, і всі мають "доступ".
Кожеш бажаючий може написату новину, яке може потрапити на головну сторінку, для цього достатньо натиснути на посилання "Публікувати новину" у панелі Навігації, і там всередині написати дійсно важлиу, або гарну новину, а я вже перегляну і прийму своє рішення чи публікувати, в загальному випадку, якщо щось не так, то звяжусь із автором, для вияснення деталей.

Так що, побільше ініціативи, а ми вже допоможемо із деталями.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Сторінка 1 з 2 1 2 >
Перейти на форум:
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

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

торт

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

квитки в кіно

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

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

книги

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

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

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