| Автор |
RE: Відбір на Всеукр 2009 |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 07-03-2009 15:36 |
|
|
Я так ту фізику й мутив (лол, звичайно без ніяких дискримінантних хформул --- пропорційність кутів до швидкостей й без того зрозуміла), але чогось в мене не заканало... ХЗ чого... Мутив тринарником --- пробував попасти в кінці по іксу в точку L.
Olecksandr написав:
Стосовно другої задачі, там не було в ній бінарного пошуку, там насправді застовуються тільки 2 РМКю.
Лол, звичайно, подвійне RMQ зробити легше ніж RMQ + Binary Search.. 
Pascal not dead! |
    
|
| Автор |
RE: Відбір на Всеукр 2009 |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 07-03-2009 18:45 |
|
|
А, ладно, поняв шо ти мав на увазі під "подвійним RMQ" - RMQ з двома параметрами. Так там RMQ з двома параметрами, і крім того, щоб додати елемент треба знати його позицію в відсортованому масиві - а то робиться через бін. пошук. Hit me if I'm wrong. 
Pascal not dead! |
|
|
| Автор |
RE: Відбір на Всеукр 2009 |
Olecksandr
Модератор
Повідомлень: 151
Звідки: Lviv NU FAMI
Зареєстрований: 30.04.06 |
| Опубліковано 07-03-2009 21:28 |
|
|
По-перше відношення швидкостей та синусів кутів зовсім неочевидне, а як бачиш має не зовсім очевидне, але просто технічне доведення. По-друге цікаво чому попередньо написані формули називаються дискримінантними. Я чув про поняття дискримінанту, дискримінантної кривої, але аж ніяк не про формули... І для чого тернарний пошук в цій задачі для мене теж залишається таємницею, ні, звісно, я знаю як його туди можна "прикрутити", але для чого?
А по-третє поділись будь ласка секретом як постійно підтримувати масив відсортованим, для того щоби потім робити в ньому бінарний пошук і звісно при цьому розвязок має проходити по часу. В тому розвязку, що був авторським, РМКю було не те що подвійне, просто трималось 2 дерева відрізків  |
|
|
| Автор |
RE: Відбір на Всеукр 2009 |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 07-03-2009 22:04 |
|
|
Який ще постійно відсортований масив?  Та тупо сортуємо всі "дерева" по координаті і коли їх "появляємо" - шукаємо бінарником позицію даного "дерева" в відсортованому масиві. На відповідній позиції в дереві RMQ його й появляємо. В тебе ж RMQ не на мільярд елементів?
Pascal not dead!
Змінив(ла) ibm, 07-03-2009 22:06 |
|
|
| Автор |
RE: Відбір на Всеукр 2009 |
Olecksandr
Модератор
Повідомлень: 151
Звідки: Lviv NU FAMI
Зареєстрований: 30.04.06 |
| Опубліковано 08-03-2009 21:33 |
|
|
Та там координати дерев були в межах [0, 200000).
Мається на увазі що тобі треба мати 2 дерева відрізків, одне для сум координат, інше для обрахунку кількостей. І ніяких бінарних пошуків при заданих обмеженнях  |
|
|
| Автор |
RE: Відбір на Всеукр 2009 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 02-09-2009 05:53 |
|
|
|
Десь можна подивитись завдання в електронному вигляді, чи єдиний шлях - стукати комусь з учасників в аську/мило/скайп - нехай перексерять? |
|
|
Birthday(s):
