Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 18.08.2022 22:10:38 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
Національна команда Ботсвани не виграла жодного міжнародного матчу за двадцять вісім років існування. У команді змінилося більше п’ятдесяти головних тренерів, чотири з яких були колишніми радянськими спортсменами.
Події
ПнВтСрЧтПтСбНд
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):
AVATARM@rk_o_LNU
AVATARIhor_Borachok

Перегляд теми
ACM Контестер | Змагання | Онлайн змагання
Сторінка 10 з 11 << < 7 8 9 10 11 >
Автор RE: Potyczki Algorytmiczne 2010
Ramzes2
Користувач

Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07
Опубліковано 28-04-2010 01:52
Спробую зробити розбір на задачу 6B-FIR

Спочатку я роблю перенумерування всіх номерів вершин в порядку обходу в ширину. Це нам дає таку властивість, що всі вершини, кількість яких треба буде рахувати в запитах, будуть мати послідовну нумерацію.
Потім для кожної вершини визначаються її предки на відстані степені двійки. Завдяки цьому для кожної вершини можна визначити її предка на будь-якій відстані за час logN.

Тепер починаємо послідовно оброблювати запити.
При запиті на підрахунок кількості вершин спочатку визначаються самий лівий і самий правий можливий нащадок (вони на момент запиту можуть ще не бути добавленими до дерева) на відстані k від даної вершини. Це виконується за допомогою бінпошука. Після цього просто взнається, скільки вершин уже є на даному проміжку (за допомогою RSQ).

При запиті на додавання вершини відповідно просто відбувається додавання даної вершини в RSQ.

Складність можна оцінити як:
Z*logN + P*logN*logN, де
Z - кількість запитів на додавання, і Р - кількість запитів на підрахунок кількості
Або простіше
N*logN*logN
Ramzes2 275493404 Ramzes2 (Cherkasy NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 02:01
Спробував локально на тесті, що у мій розв'язок отримав ТаймЛіміт
час виконання 3,906 s. (на достатньо повільній машині)
тобто даним розв'язком цілком реально було отримати 10 балів
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 02:05
Отже, у мене загальний результат стоновить 74 бали, із чим себе і вітаю!

Згадалось:
webmaster написав:
вже є результати
3B пройшла повністю
3A набрала 4 бали, ....

тепер разом маю +44, дуже гарно
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 02:10
Тут я подумав, що мій розв'язок 6B-FIR
Можна простіше пояснити.
Перенумеровуємо вершини у порядку обходом у глибину.
Далі ідемо по запитам. При додаванні закидуємо нову вершину до вектора, що відповідає глубині на якій знаходиться дана вершина (таких векторів, стільки скільки можливих глубин). При запитті на отримання даних пробігаємо по всім вершинам на потрібній глубині і визначаємо чи є дана вершина нащадком потрібної, при такій нумерації вершин це зробити просто.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ostap
Модератор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 28-04-2010 10:12
Розв'язок до задачі про банани 6B-BAJ:
По перше, ми не можемо зрізати гілку раніше ніж на ній достигнуть всі банани, бо недостиглі банани зрізати не можна (самі знаєте, що буває, якщо наїстися чогось недостиглого). Тобто якщо ми візьмемо гілку, на якій ростуть крайні гілки з бананами, то мінімальний час, коли ми можемо зрізати цю гілку - це максимум всіх Ai, для гілок, що ростуть на ній, позначимо його МА. Очевидно, що всі гілки, на яких банани зігниють до моменту МА (гілки з Ві < МА), ми мусимо зрізати по одній, тобто їх кількість ми додаємо до результату. Всі решта гілки, що на цій гілці ми можемо зрізати одним махом бензопили, просто зрізавши цю гілку. Але треба щоб ці банани не погнили, тому нам треба знайти найпізніший час, коли ми можемо зрізати цю гілку - це мінімум Ві серед гілок, що залишилися (відкинувши ті, що зрізали до часу МА), назвемо його МВ. Отже на відрізку часу [МА;МВ] ми можемо зрізати все що залишилося на гілці. Таким чином ми можемо вважати цю гілку, як крайню, на якій ростуть банани і яку треба зрізати в терміни [МА;МВ]. Тобто ми перейшли до підзадачі.
Таким чином починаючи від листків рухаємося до кореня, обрубуючи деякі гілки (збільшуючи результат), а деякі перетворюючи на крайні, аж поки на нашій вербі з бананами не залишиться одна гілка, яку просто під корінь ребаємо, вправним рухом сокири. А якщо по простому, в кінці ще додаємо до результату 1 за цю гілку.
Як видно, розв'язок лінійний, але вимагає деякої лісорубської майстерності :)


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ostap
Модератор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 28-04-2010 10:50
Спробую ще прийняти участь в конкурсі розборів до задачі 6B-FIR.
Складність мого розв'язку N*logN.
Наперед попереджаю, що мій розв'язок трохи технічно непростий. Отже, ось що потрібно робити.
Спочатку все зчитаємо і побудуємо все дерево, а потім будемо відповідати на запити.
По перше, кожен запит вимагає порахувати вершини, які знаходяться на одному рівні в дереві. Використаємо це і будемо обробляти дерево по рівнях, відповідаючи на запити відповідного рівня. Тому для кожного запиту збережемо рівень в дереві, до якого він стосується.
Щоб було просто визначити для якого запиту які вершини рахувати, перенумеруємо вершини в порядку їх додавання. А для кожного запиту ще збережемо останній номер доданої вершини, коли був зроблений цей запит.
Побудуємо ще одну індексацію для дерева - в порядку його обходу пошуком вглиб. При такій індексації всі вершини, що знаходяться в піддереві даної вершини будуть мати послідовні наступні індекси. Отже будемо мати dfs-індекси, також запам'ятаємо для кожної вершини останній dfs-індекс її піддерева. Для прикладу, дерево з умови в порядку обходу вглиб буде записано так: 12453. Як видно, піддерево вершини 2 йде відразу за ним (45). Отже, якщо номерувати все з одиниці, то dfs-індекс вершини 2 також 2, а кінчається її піддерево в індексі 4 (починається, очевидно відразу після самої вершини, в індексі 2+1=3).
Далі обробляємо всі вершини і запити по рівнях, для кожного рівня, шукатимемо відповіді для запитів, які рахують вершини саме з цього рівня. Всі запити і вершини з рівня сортуємо в порядку появи і проходимо по цьому списку (насправді сортуються окремо список вершин і список запитів і проходимо по них двома вказівниками, просто з одним списком пояснення більш наглядне. Більш того сортування відбувається не щоразу на рівні, а один раз просто першим парамертом сортування є рівень, а другим - порядок появи). Якщо попадається вершина, то додаємо її в RSQ на позицію її dfs-індекса. Якщо запит, то дістаємо з RSQ кількість доданих вершин на відрізку, що відповідає dfs-піддереву вершини з запиту.
Після обробки рівня очищуємо RSQ. Для цього просто на позиції, в які ми на цьому рівні додавали 1, додаємо -1. І переходимо до обробки наступного рівня.
В кінці, обробивши всі рівні, і всі запити, відповідно, залишається лише відновити порядок запитів як вони ішли у вхідному файлі, щоб в правильному порядку вивести відповіді.

Оскільки ми кожну вершину один раз додаємо в RSQ і один раз забираємо її звідти, кількість запитів до RSQ дорівнює кількості запитів в вхідному файлі, а решта операцій, як то побудова дерева, обхід вглиб лінійні і є кілька сортувань, то загальна акумульована складність N*logN.

Довідка: RSQ - структура даних, яка дозволяє виконувати над масивом чисел запити двох видів за логарифмічний час: додавати число до деякого елемента масиву і рахувати суму чисел на відрізку в масиві.


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ramzes2
Користувач

Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07
Опубліковано 28-04-2010 15:27
Ostap написав:
Спробую ще прийняти участь в конкурсі розборів до задачі 6B-FIR.
Складність мого розв'язку N*logN.

А який час максимальний час виконання?
Ramzes2 275493404 Ramzes2 (Cherkasy NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 21:32
Вже є остаточні рузультати!!!!
Тільки вони нажаль зведені, немає самих українців.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ostap
Модератор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 28-04-2010 22:40
Ramzes2 написав:
Ostap написав:
Спробую ще прийняти участь в конкурсі розборів до задачі 6B-FIR.
Складність мого розв'язку N*logN.

А який час максимальний час виконання?


Найгірший час на тесті:
9b OK 0.21s/1.00s


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 22:50
Зроблю підбірку результатів Українців:
(місце у загальному заліку, хто, скільки сумарно балів)

5 Vladyslav Simonenko 141
7 prgobet 140
15 Anton Raichuk 131
18 Dmytro Dzhulgakov 128
31 Daniil Neiter 121
37 shef 117
47 Anton Lunyov 109
61 Dima Sobolev 99
61 Evgeny Sobolev 99
64 Ostap Korkuna 98
94 Oleksandr Skoryk 85

це ті, що у ТОП100, сподіваюсь нікого не пропустив.

надиву однакові результати у братів Соболєв, навіть по задачам.
щось я не можу знайти "Dmytro Kozhevin".
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 23:55
Я щось не дуже правильно вмію рахувати, пише:
108 Bohdan Pryshchenko 81

що коли депортують, то ще бали докидуєш, типу, щоб з голоду не помер?
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 29-04-2010 07:57
webmaster написав:
Я щось не дуже правильно вмію рахувати, пише:
108 Bohdan Pryshchenko 81

що коли депортують, то ще бали докидуєш, типу, щоб з голоду не помер?

Не пали контору:)

А про Соболєвих - пора б знати, що в них завжди так...


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
DixonD
Модератор

Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06
Опубліковано 29-04-2010 09:59
Серед авторів задач Марека Цигана тільки впізнав...
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 29-04-2010 10:32
DixonD написав:
Серед авторів задач Марека Цигана тільки впізнав...

Ще здається коли ми були у Петрозаводську, то польський контест давав Jakub Onufry.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ostap
Модератор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 29-04-2010 11:01
webmaster написав:
DixonD написав:
Серед авторів задач Марека Цигана тільки впізнав...

Ще здається коли ми були у Петрозаводську, то польський контест давав Jakub Onufry.


То був Jakub Radoszewski (TopCoder handle jakubr)


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 29-04-2010 11:17
Ostap написав:
webmaster написав:
DixonD написав:
Серед авторів задач Марека Цигана тільки впізнав...

Ще здається коли ми були у Петрозаводську, то польський контест давав Jakub Onufry.


То був Jakub Radoszewski (TopCoder handle jakubr)

Ага є такий
Kierownik Jury: Jakub Radoszewski
ту частину я навіть не читав, от і пропустив
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 31-05-2010 22:48
Мені прийшла футболка. Поки одна, сподіваюсь, що інша прийде незабаром.
Футболка точно така як і минулого року, звісно дати тільки інакші.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 18-06-2010 12:35
мені прийшла друга футболка і вона на диво точно така сама як і попередня
:)

всім прийшли футболки? Чи може чиюсь УкрПошта конфіскувала за чітерство :)
Змінив(ла) webmaster, 18-06-2010 12:36
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ostap
Модератор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 19-06-2010 07:13
Мені прийшла, але я її ще не бачив. Правда по твоєму опису можу собі уявити :)


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
cupidon4uk
Користувач

Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09
Опубліковано 02-05-2011 14:35
Коли і де буде реєстрація на цю штуку в 2011 році?)


GoogleHireMe 557679737 mylyanyk.ivan [Lviv_NU] Надіслати приватне повідомлення
Сторінка 10 з 11 << < 7 8 9 10 11 >
Перейти на форум:
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

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

торт

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

квитки в кіно

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

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

книги

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

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

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