| Автор |
Lviv Training Evening |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 28-04-2010 00:06 |
|
|
|
Тренування на базі acm.tju.edu.cn планують проводитись більш менш регулярно, тому тут будемо обговорювати змагання, задачки і розв'язки та вітати переможців. |
   
|
| Автор |
RE: Lviv Training Evening |
cupidon4uk
Користувач
Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09 |
| Опубліковано 30-04-2010 18:03 |
|
|
хм... У мене шось не заходить... То тільки мені здається, шо там всьо дуж глючить, чи то в всіх ?
|
|
| Автор |
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 |
|
|
| Автор |
RE: Lviv Training Evening |
kobra
Користувач
Повідомлень: 45
Звідки: НУ "Львівська політехніка"
Зареєстрований: 29.03.08 |
| Опубліковано 06-05-2010 20:25 |
|
|
D. Якщо розглянути вже якийсь небудь готовий остовний граф, то можна помітити, що час потрачений на його проходження рівний:
Подвійний час проходження кожного ребра + Сума(К-сть ребер що входять в точку * час перебування в точці) + Час перебування в початковій точці. Тобто якщо ми отримали якийсь граф, нам вигідно за початкову взяти точку з мінімальним часом очікування.
Граф будується наступним чином. Запускаємо Краскала, але перед тим змінивши ваги ребер. Вага ребра = Вага ребра*2 + час очікування в 1 точці + час очікування в другій точці. Ось і все.
Знаходимо вагу графа+час в мін. точці це і є результат. |
|
|
| Автор |
RE: Lviv Training Evening |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 09-05-2010 21:23 |
|
|
Наступний контест в середу, 12 травня, в 19:00 за Київським часом.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
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 |
|
|
Кожен бажаючий може взяти на себе ініціативу у проведеннні та організації віртуальних контестів на китайському сервері. Це зробити досить просто, а якщо виникають якісь ускладення або потрібна допомога, то звертайтесь.
А краще завжди узгоджуйте зі мною, щоб все було найкраще. |
|
|
| Автор |
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 |
|
|
Коли наступні змагання? І чого так рідко організовуються? Зара, поки літо, я б їх щовечора робив... Але не маю доступу до головної сторінки, а форум не всі читають... Дайте мені змогу постити на головній сторінці і я б регулярно з кимось через раз організовував змагання(щоб і мені цікаво було взяти участь)... От... Ну то шо адміни скажуть? =)
|
|
|
| Автор |
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 |
|
|
Віталій каже цілком правильно, змагання організовуєш, пишеш на форумі всі деталі і повідовляєш мені, а я вже якусь новинку напишу.
Але це не все.
Ти маєш "доступ" до головної сторінки, і всі мають "доступ".
Кожеш бажаючий може написату новину, яке може потрапити на головну сторінку, для цього достатньо натиснути на посилання "Публікувати новину" у панелі Навігації, і там всередині написати дійсно важлиу, або гарну новину, а я вже перегляну і прийму своє рішення чи публікувати, в загальному випадку, якщо щось не так, то звяжусь із автором, для вияснення деталей.
Так що, побільше ініціативи, а ми вже допоможемо із деталями. |
|
|
Birthday(s):
