Дев’ята лекція другого сезону відбудеться 25 листопада о 18 годині у конференц-залі на третьому поверсі.
Лекцію ведуть: Олександр та Мар’ян.
Тема: Вступ до теорії ігор.
На порядку денному:
- Ігри з вилученням об’єктів.
- Ігри на орієнтованих ациклічних графах.
- Матричні ігри.
- Гра Німа.
Ця тема дуже різнопланова і багато з чим перетинається. Такі штуки, як Нім чи SGF – це строго теорія ігор, але в загальному до цієї теми треба ще обходи графа, перебір, динамічне програмування…
Нагадайте стрічку на джаваскріпті, яка перетворюється в потенційно небезпечний код.
Що мається на увазі “потенційно небезпечний”?
Як на мене, то джаваскрипт взагалі потенційно небезпечний, як і будь-яка інша мова програмування з користувачем з правами адміна =)). Все залежить від програміста
Не забувайте про домашнє завдання:
1014. Гра (http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1014)
1050. Перерва (http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1050)
1091. Superman vs. Batman (http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1091)
1229. Неофіційні змагання (http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1229)
1320. John (http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1229)
Timus 1417. Space Poker 2 (http://acm.timus.ru/problem.aspx?space=1&num=1417)
Сорі за офф-топ, але я тут на дозвіллі робив ту задачку, яку Шеф на початку розказував. І я зіткнувся з проблемою. Я вивів формулу, і все вроді нормально, але вона (формула) не підходить для другого тесту з умови. Хтось може сказати, чому не проходить?
п.с. Задачка
http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1220&rid=4ceec918a7086
Ні, стоп… Той тест проходить, але не проходить шостий. Отут я вже дійсно не знаю де помилка…
http://acm.tju.edu.cn/toj/vcontest/contest7327.html
контест 18:00 субота
тут задача про яку я згадував на лекції:
http://acm.timus.ru/problem.aspx?space=1&num=1180
1. Всього швидше треба збільшити розмір масиву. В мене чомусь масив з розміром 1001(чого має бути достатньо) падає по тайм ліміту.
2. Перевір чи твоя формула правильна
Мене давно цікавить одна задачка. Шеф казав на лекції, що можна написати тут… Пишу..
Є автобус з кількістю місць N. M людей чекають на автобус на дорозі з координатою X[i](км), кожна людина їде деяку відстань L[i](км). Ціна проїзду – 1грн/км. Вважаючи, що водій не буде тримати в автобусі більше ніж N людей, порахувати яку максимальну суму він може заробити за 1 рейс.
Дорога – пряма.
Вхід:
N M
X[1] L[1]
X[2] L[2]
…
X[m] L[m]
N<100 M<1000 (X[i]+L[i])<10000
Наприклад:
тест1
2 3
1 100
3 200
2 400
відповідь: 600
тест2
5 7
1 17
2 11
3 54
17 3
21 40
1 100
14 5
відповідь: 230
а де цю задачу можна здати?
Не знаю. Вона в нас на ліцейському відборі була. Там були тупі тести, тому проходив перебір. Але мене цікавить нормальний розв’язок.
А шо, він вам потім не розказував її розв”язок? Може просто то й було розраховано на передір, а з обмеженнями викладач помилився?)))
Ну… В мене крутиться якась ідея з крутим якимось вимітанням – типу проходимо по тому відсортованому масиві, і, якшо в якийсь момент в нас маршрутка заповнена, то нам потрібно вирішити шо ми робимо – не беремо якогось одного пасажира, який вже є в автобусі(і тоді виключаєм його зі списку), або не беремо того, який хоче сісти. А відкидаєм ми тих,в кого найменша L[i]. Тоді просто сумуємо L[i] для тих пасажирів, які залишились в списку.
от, це мало б пахати…
А ше, мені дуже цікаво. Є якийсь критерій задачі “на теорію ігор”? Ну, тобто, ти дивишся на задачку і можеш сказати – оце – на теорію ігор. Є таке? Я просто чому говорю – інколи задачка буває сформульована у вигляді гри двох суперників, але воно ніяк не повязано з теорією ігор. Для прикладу – задачка з минулої області про розрізання паперу… Ну, я думаю, таких задач, насправді, багато.
І ше, ось ця задачка – на теорію ігор?
http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1043&rid=4cf13b267c7b6
Я його питався про ту задачку, а він сказав що не скаже. Сумніваюся що він робив в себе перебором. Він вроді такого ніколи не робить.
Купідон твій розвязок не пройде. Опишу контр приклад. В автобусі одне місце. Є три пасажирі. Перший сідає десь на початку і має проїхати якусь відстань 1000. Другий сідає десь перед тим як перший має виходити і має проїхати 1001. А третій сідає десь перед тим як має виходити другий і теж має проїхати 1000.
по твоєму алгоритму спочатку ми посадимо першого, але потім його викинемо бо другого брати вигідніше, і аналогічно третього ми не візьмемо. Хоча нам вигідно взяти першого, а потім третього.
Та задачка наскільки я пам’ятаю не є на теорію ігор.
CUPIDON, я погоджуюсь з kobra, що твоя задачка не на теорію ігор. Щодо визначення, яка задачка на теорію ігор, а яка – ні, мабуть треба здати їх хоч десяток в різних варіантах і потім вдосконалювати навик.
В загальному думаю, треба виходити з базових питань задачі (і можливо, елементарних залежних даних та питань) і співставляти їх з обмеженнями та типами задач на теорію ігор (про це я коротко розказував у вступі лекції, а детальніше можна почитати в багатьох книжках та сайтах). З перших же визначень дуже часто стане зрозуміло, чи поможе теорія ігор, чи ні. В найпростішому варіанті сказав би, що якщо задача на теорію ігор, то стратегій в (декількох) гравців є декілька і потрібно вибрати оптимальну комбінацію. Хоча, то дуже спрощений частковий випадок…
Ну, я свою помилку зрозумів. Хм… Тоді як то робити?!)
А стосовно задачі “Поле Чудес”. От тобі зрозуміло, шо вона не на теорію ігор, бо ти зробив її раніше. Але як я мав би здогадатись, шо це НЕ на теорію ігор?
І, до Щефа. Якщо ти “в замешптельстве” стосовно першої задачки(про маршрутку і пасажирів), то чи міг би ти розказати на наступний раз оцю про Поле Чудес?
Щодо “Поле Чудес” – я точно не знаю, як її робити. І взагалі не здав. Але явно вона не підходить до задач на теорію ігор. Думаю, там щось типу рангу матриці треба знайти чи якусь систему рівнянь розв”язати (що в принципі, те ж саме для такого питання).
Щодо автобуса, то в мене зразу виникло припущення про інтеграл, але так і не мав часу перевірити. Отже, малюємо графік кількості пасажирів від часу S(t), якщо брати всіх підряд, незважаючи на місткість автобуса. потім інший графік – кількість дозволених пасажирів (пряма y=N). А потім рахуємо інтеграл від F=min(N,S). Щодо реалізації, то легко то рахувати сканлайном, задавши +1 при додавання людини і -1 при закінченні проїзду. Якби питали кого треба брати, то такий метод не підходить, а чисто для кількості – мав би…
на мою думку основна причина чому ця задача не підходить до теорії ігор – це відсутність вибору ходів у гравця. Цілком логічно, що йому вигідно перебрати всі можливі четвірки, оскільки він нічого не втратить від цього. А щодо розвязку цієї задачі. Розглянь спочатку для прикладу 4 квадратики. Скільки на твою думку він зможе визначити значень і їх позицію? Після цього розглянь 5 квадратів і аналогічно попробуй визначити. Ну, а далі попробуй якось узагальнити))
Саша твій розвязок тоже не пройде. Той самий приклад, що я писав вище. В тебе видасть, що на всьому проміжку буде один пасажир, але насправді посередині автобус буде їхати пустим.
Так… Щось ти мегатест придумав… Всі розв”язки завалив =)
Жадний алгоритм тут наче ніякий не пройде… А динаміки в бітмаски влазять і не поміщаються в пам”ять. Навіть не знаю тоді =(
Розберемо цю задачу на лекції. Але перед тим хотілося б почути у кого ще які ідеї стосовно цієї задачі.
А чому б не так:
DP[i][j] – максимально скільки ми можемо заробити, якщо ми в точці i та в автобусі є j людей.
Звідси неважко вивести залежність, і з невеликими оптимізаціями (обчисланням максимуму на кожному кроці або RMQ (точно не знаю, але скоріш за все не потрібно його)) можна отримати O(N*M);
Що скажете?
Але ж нам важливо які саме люди знаходяться в автобусі, бо вони в різні моменти виходять. Що ти пропонуєш?
Шось мені нічого в голову не приходить, крім того, шо я вже писав.
Питання до Віталія : “звідси не важко вивести залежність”….
Я розумію, шо тобі то може легко, але для мене ця залежність не зовсім очевидна. Можна чуть детальніше?
Справді, добре не подумав.
Але попала ще одна ідея:
Розглянем всі поїздки як проміжки [Li, Ri]
Тоді нам треба вибрати максимальну суму проміжків, так щоб їх максимальна вкладеність не перевищувала N.
Тоді, я думаю, можна так (жаднік + ДП)
1. Динамікою знайдем макс. суму проміжків, що не перетинаються (їх вкладеність не перевищуватиме 1) і видалимо їх із проміжків.
2. Динамікою знайдем макс. суму проміжків (з тих що залишились), що не перетинаються (їх вкладеність не перевищуватиме 2) і видалимо їх із проміжків.
…
Так зробимо N раз. В рез. сумою буде відповідь. Чи не так?
CUPIDON:
Поки що той розв’язок відпадає.
Змушений розчарувати тих хто ще й досі вірить в розв’язок Віталія. Розглянемо наступний простий тест:
Є два місця у маршрутці та наступні відрізки для пасажирів
[1, 47], [50, 99], [48, 51], [44, 49].
В оптимальному розв’язку можна везти всіх.