Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 28.03.2024 15:23:38 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
Оптимістична печера — карстова печера, яка знаходиться поблизу села Королівка Борщівського району Тернопільській області на території України. Вона занесена до Книги рекордів Гінесса як найдовша в світі гіпсова печера (Сумарна картографована довжина довжина її ходів складає 230,5 км).
Події
ПнВтСрЧтПтСбНд
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):
AVATARAlex_neo
AVATARWinner
AVATARinvarian
AVATARsvadsak lol

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

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 27-04-2010 23:19
Вже не вперше чую і по собі відчуваю, що чим ближче до кінця тим більше накопичується у всіх, за малим вийнятком, учасників змагання почуття програшу. Це недолік турнірів, які працюють по схемі накопичення балів за задачі за кожен тур.
От і в цьому змаганні ми кожного туру програємо і програємо, і в загальному заліку, той, хто програв найменше - перемагає. Це трохи підриває бойовий дух і бажання розв'язувати далі. От на ТСО напрклад, все навпаки. Там ти можеш програти лише один раз і вилетіти, а інакше ти перемагаєш і перемагаєш (проходиш далі), таким чином азарт після кожного раунду зростає.
Але давайте не забувати, що на кожному змаганні, як і на цьому, ми перш за все змагаємося з задачами, випробовуємо своє вміння і навики і вчимося чомусь новому. Не варто надавати занадто високої уваги тому в якому ви рядку таблиці. Надавайте на багато більше ваги саме своєму рядку. Якщо там додатні бали - це ваша перемога. Якщо там не 10 - то знайдіть свою помилку, оптимізуйте алгоритм, перепишіть все начисто і зробіть цю задачу. Це не змінить нічого в таблиці, але змінить багато для вас!
Не варто забувати, що змагаємося ми не з суперниками, бо на них ми не маємо впливу. Змагаємося ми з задачами і, перш за все, з собою!
Тож побільше вам маленьких і великих перемог, і, головне, не забувайте їх помічати!



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

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 27-04-2010 23:43
Ostap написав:
Тож побільше вам маленьких і великих перемог, і, головне, не забувайте їх помічати!

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


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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 27-04-2010 23:50
правильно Остап каже, як там прийнято цей тиждень говорити: "Ja mam tak samo".
От наприклад у можна сказати також забив, але не тому, що вже не виграю, або може не перепаде мені ще одна футболка, а тому, що на Дерева у мене реально немає ідеї (ну ніякої, аж цікаво дочекатись кінця і почути думки інших учасників), а іншу про Фірму, я написав, але точно не найкраще, також не дуже вийшло. Головне, що я пробував розв'язати задачки. Думаю, то не тільки Вам важко розв'язати дані задачі, а й тій тисячі полякам також.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 27-04-2010 23:52
Ostap написав:Це трохи підриває бойовий дух і бажання розв'язувати далі. От на ТСО напрклад, все навпаки.

брат по нещастю... Мені 18 нема, тебе з роботи не звільняють... Обоє без ТСО:) Це ж я б собі і кількість рейтед івентів підняв, і може трохи рейтинг. І практика така важлива... А, ще про футболку забув згадати!

Істинна перевага ТСО в тому, що там не треба багато думати:) Хоча б тому, що матч в часових межах досить короткий. Якщо про алго говорити, марафони не зачіпаєм.

Ostap написав:накопичується у всіх, за малим вийнятком, учасників змагання

А малі винятки напевно сидять і кривлять носом, бо, бачте, задачі були дуже легкі і нецікаві, так що в програші всі.


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

Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07
Опубліковано 28-04-2010 00:11
Кажись я збочинець, на 6B-FIR написав N*logN*logN, і воно ще і якось працює :)
Ramzes2 275493404 Ramzes2 (Cherkasy NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 00:16
Ramzes2 написав:
Кажись я збочинець, на 6B-FIR написав N*logN*logN, і воно ще і якось працює :)

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

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 28-04-2010 00:16
Ramzes2 написав:
Кажись я збочинець, на 6B-FIR написав N*logN*logN, і воно ще і якось працює :)

Кажись я не безнадійний, бо навіть уявляю, як там таке можна отримати. Бачу АС... непогано.
закралась думка: "а спорим не пройде на 10/10?";))
Цікаво, чи вони за квадрат хоч 1 бал дадуть... Бо на минулому турі найповніший перебір до МАА набирав 0.
А сьогодні я дуже й не думав, але була хіба ідея, як зробити щось близько N*logN в кращому випадку, яке можна спецтестами загнати на квадрат.


Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 28-04-2010 00:19
LeBron LeBron Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 00:18
LeBron написав:
Ramzes2 написав:
Кажись я збочинець, на 6B-FIR написав N*logN*logN, і воно ще і якось працює :)

Кажись я не безнадійний, бо навіть уявляю, як там таке можна отримати. Бачу АС... непогано.
закралась думка: "а спорим не пройде на 10/10?";))


а я якщо чесно то не знаю як там можна N*log*logN , ну звісно можна для надійності ще разок залогарифмити :)
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ramzes2
Користувач

Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07
Опубліковано 28-04-2010 00:18
LeBron написав:
закралась думка: "а спорим не пройде на 10/10?";))

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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 01:03
Змагання завершилось!!!

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

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 28-04-2010 01:05
Ого, в фірмі в мене повний перебір набрав аж 2 бали:)


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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 01:06
Я відправив тільки одну задачу
6B-FIR
і у мене за неї 8/10 балів
один РанТайм, що досить неочікувано
а інший ТаймЛіміт, хоча я думав, що їх більше буде

за сьогодні у мене тільки ці 8 балів
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
Ramzes2
Користувач

Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07
Опубліковано 28-04-2010 01:07
6B-FIR - 9 балів
і знову якась тупа помилка лише на одному тесті:
process exited due to signal 11 Segmentation fault (SIGSEGV)
Ramzes2 275493404 Ramzes2 (Cherkasy NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 28-04-2010 01:08
Моя ідея оптимізації в фірмі була така: зберігати для кожної вершини її предка глибини всіх степенів 2 і кількість нащадків всіх глибин степенів 2, тоді при додаванні у нас завжди logN, а при запиті опускаємось до найближчого степеня двійки, (наприклад, для глибини 13 - переходим на 12, потім на 8, і ми на місці), і вже на тому рівні перебираєм всі вершини (і сумуємо кількості відповідних їхніх потомків. На сильно розгалужених деревах повинно досить помогати, але легко завалюється до квадрату нерозгалуженими деревами з добре підібраними запитами.


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

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 28-04-2010 01:09
Ramzes2 написав:
LeBron написав:
закралась думка: "а спорим не пройде на 10/10?";))

не треба тут таких думок! Скоро побачим...

Ramzes2 написав:
6B-FIR - 9 балів
і знову якась тупа помилка лише на одному тесті:
process exited due to signal 11 Segmentation fault (SIGSEGV)

от і побачили...


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

Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07
Опубліковано 28-04-2010 01:10
LeBron написав:
Моя ідея оптимізації в фірмі була така: зберігати для кожної вершини її предка глибини всіх степенів 2 і кількість нащадків всіх глибин степенів 2, тоді при додаванні у нас завжди logN, а при запиті опускаємось до найближчого степеня двійки, (наприклад, для глибини 13 - переходим на 12, потім на 8, і ми на місці), і вже на тому рівні перебираєм всі вершини (і сумуємо кількості відповідних їхніх потомків. На сильно розгалужених деревах повинно досить помогати, але легко завалюється до квадрату нерозгалуженими деревами з добре підібраними запитами.

а якщо сюди ще всунути бінпошук і RSQ, то вийде мій N*logN*logN
Ramzes2 275493404 Ramzes2 (Cherkasy NU) Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 28-04-2010 01:15
А з приводу дерева - я робив дуже схожу задачу, там казочка була про підставні результати на спортивних змаганнях, так от там виходила ще суттєва додаткова умова, яка не дозволяла пиляти дуже далеко від листків (виходило максимум заглибитись від них на 2), і тому проходив напівжадний перебір, можна було просто згортати дерево до кореня, кожен раз беручи об'єднання проміжків всіх потомків, ну і якщо виходив нульовий інтервал - треба було пиляти тих потомків... Треба було може тут таке відправили, і подивитись з цікавості, чи хоч 1 бал візьме.

А як наш випадок розв'язується, хтось знає?

І ще, в фірмі повний перебір розрахований аж на 4 бали, в мене там ще й ВА, бо стек не занулював:)


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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 01:16
Задача 6B-FIR

Мій варіант розв'язку.
Перенумаровуємо вершини у порядку обходу дерева вглиб. Тоді вийде, що якщо ми беремо деяке піддерево, то всі номери у ньому будуть послідовні - це ключивий момент.
Далі маємо гарну структуру даних, яка для кожної різної глубини (їх 100000 всього) може докидувати вершину і казати скільки є вершин менших за дане значення.
Далі ми пробігаємось по всім запитам, якщо потрібно додати нову вершини, то ми визначаємо на якій вона глубині відносно корена і докидуємо до тої структури.
Якщо потрібно отримати кількість вершин, то ми визначаємо номер даної вершини (це найменший номер у даному піддереві) і найбільший номер у даному піддереві (ці дані прекалькулювати можна). Маючи ці дані, то ми для потрібно глубини визначаємо скільки є вершин із потрібного нам проміжку.
Отже тут ми маємо складність N - кількість операцій помножено на складність додавання до структури і отримання даних.

Я зробив цю структуру дуже тупою, яка просто пробігається по всіх наявних елементів, тому у мене складність вийшла загальна O(N*N), хоча для того потрібно було специфічний тест, і він був у цілому наборі тільки один.

Я якщо ту структуру зробити дерево інтервалів, то тоді склданість її буде logN, тому загальна складність O(N*logN). Тільки трохи незвично , що маємо 100000 дерев інтервалів і всі різної довжини.
Змінив(ла) webmaster, 28-04-2010 01:23
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Potyczki Algorytmiczne 2010
LeBron
Головний Адміністратор

Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09
Опубліковано 28-04-2010 01:17
Ramzes2 написав:
LeBron написав:
Моя ідея оптимізації в фірмі була така: зберігати для кожної вершини її предка глибини всіх степенів 2 і кількість нащадків всіх глибин степенів 2, тоді при додаванні у нас завжди logN, а при запиті опускаємось до найближчого степеня двійки, (наприклад, для глибини 13 - переходим на 12, потім на 8, і ми на місці), і вже на тому рівні перебираєм всі вершини (і сумуємо кількості відповідних їхніх потомків. На сильно розгалужених деревах повинно досить помогати, але легко завалюється до квадрату нерозгалуженими деревами з добре підібраними запитами.

а якщо сюди ще всунути бінпошук і RSQ, то вийде мій N*logN*logN

От в мене якраз з оцим всуванням була проблема, бо я мав тільки загальне уявлення, що науці відомі такі речі. Пошук це зрозуміло, а от ліпіння якої-небудь зручної бінарної структури, яку мені зразу навіть не до кінця ясно було як саме модифікувати в процесі - то після тижневого марафону для мене затяжко.


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

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-04-2010 01:49
webmaster написав:
Задача 6B-FIR

Мій варіант розв'язку.
...

Тут питають мене...
Складність мого алгоритму:
O(N*N)

але на приктиці складність буле значно менша.
Щоб завалити мій розвязок потрібно тест приблизно такий:
у кореня 50000 синів (прямих)
далі 50000 разів питаємо скільки у кореня синів
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Сторінка 9 з 11 << < 6 7 8 9 10 11 >
Перейти на форум:
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

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

торт

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

квитки в кіно

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

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

книги

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

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

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