| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 25-04-2010 02:40 |
|
|
як і казав, косметичні правки і задача 4В готова і проходить всі тести
Ну тоді вже я і розкажу свій спосіб розвязання цієї задачі, за один прохід
Сортуємо, хто б сумнівався  , за якоюсь координатою, нехай Ох.
На початку маємо два набори точок, ті що зліва і ті що справа, відповідно їх перед тим потрібно правильно ініціалізувати. Над цими наборами можемо виконувати такі операції: додати нову точку, видалити існуючу точку, взнати мінімум по Оу і взнати максимум.
Ми будемо пробігатись тільки по різним Хксам, тобто обробляти порціями.
Для певної порції, що має координати Хі, працюємо так. Спочатку всі точки із цієї порції викидаємо із масива що справа (доречі, це я якраз забув зробити), далі пробігаємось по всім точкам і дивимось чи може бути дана точка стартовою, всю потрібну інформацію ми можемо отримати із двох наборів. Потім докидуємо до лівого набору дану порцію.
Ось це посуті і весь алгоритм.
Тепер тільки вся складність яку б то таку структуру організувати, щоб легко можна було дадавати елементи, видаляти і знаходити мін та макс.
Позну із set<pair<int,int> >, тільки тут перший аргумент буде координата Оу, а другий Ох. Додавати легко і видаляти також. Вся красота сета у тому, що він завжди є посортований, тому якщо ми беремо перший елемент, то він є мінімальним, а якщо останній, то він максимальний. Тому всі потрібні операції виконуються зі складністю O(log(N)).
Але як я говорив раніше, цей спосіб трошки на пару мегабайть, не вклавсі у память.
Інший спосіб це мати посортований масив координат Yків, і знати для кожної точки, де його відповідна координата Yк у даному масиві. Коли видаляємо, то ми просто помічаємо, що ця позиція не використовується. Далі коли нам потрібно знайти мінімальний Yк, то ми рухаємось поки не знайдемо, координату, яка поки використовується. Так ми тільки один раз пробіжимось по даному масиві.
Ця штука порівняно до самого алгоритму виглядає занадто складною, але користь її у тому, що зручний алгоритм не довелось змінювати. |
   
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
| Опубліковано 25-04-2010 03:06 |
|
|
Hу в мене як згадувалося вже, одне сортування для масиву і чотири цикли по різних напрямках.
Я більше часу сидів, щоб сортування нормальне написати(переписати) і пришвидшити ввід. В результаті сортування вийшло набагато швидше за стандартне, тому задачка пройшла із запасом. |
 ![dixond[злий_пес]acm[на]lviv[на]ua](../themes/Brasil-Fusion/forum/msn.gif)
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 25-04-2010 10:33 |
|
|
Остап нагадав дуже гарний спосіб - дивитись на форум, на Польський форум (http://www.konkurs.adb.pl/user.phtml?op=cforum). Там вони (учасники) тести викладають.
Після такого провалу, тепер я точно буду звірятись, але то не означає, що у них у всіх правильні відповіді.
Змінив(ла) webmaster, 25-04-2010 11:00 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 25-04-2010 11:04 |
|
|
|
LeBron написав:
з оф. правил контесту, змініть хтось час в новині на сайті, бо не співпадає.
виправив, дякую
6-ий тур починається
26 квітня - 17:00
по середньоєвропейському часі
Змінив(ла) webmaster, 25-04-2010 11:05 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
| Опубліковано 25-04-2010 12:40 |
|
|
|
Ага, я вже на гриби звірявся - все сходилося, тільки чомусь на системних не зійшлося |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 25-04-2010 12:54 |
|
|
DixonD написав:
Ага, я вже на гриби звірявся - все сходилося, тільки чомусь на системних не зійшлося
Вже хтось з поляків на форумі питався, як то так - в нього все з форуму пройшло, а на системці 2/10...
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
| Опубліковано 25-04-2010 13:09 |
|
|
|
Прикол, в тому, що в мене деякі зі системних на компі сходяться, які в них були фейл. Я думаю, то шось з виведенням і різними компіляторами... |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
| Опубліковано 25-04-2010 13:11 |
|
|
Здаю "козла" - вибиває на семплі "WA:Read 4.0982041311, expected 0.0000000000".  |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 25-04-2010 13:55 |
|
|
оце так я і зробив!!!!!
взяв тести до задачі МАА із форуму і створив задачу у нас на сайті під номером 2000
щоб спробувати свій розвязок достатньо відправити його на задачу із номером 2000, помер потрібно вписати у поле "Задача"
звісно тести можуть бути не правильні і на даний час там тільки малі тести, якщо хтось хоче додати ще тести, то відправте мені тест на brus07[at]gmail[dot]com
Змінив(ла) DixonD, 25-04-2010 16:42 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 25-04-2010 14:57 |
|
|
та вся детективна історія із нелегальним перетином і подальною департацією Леброна на Україну наштовхнула на одну думку:
кожну задачу можна сабмітити 20 разів максимум, а якщо ще нелегально у Польщі посабмітити, то виходить 40 разом
контрабанда
Звісно це все проти правиль змагання!
Змінив(ла) webmaster, 25-04-2010 15:00 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
| Опубліковано 25-04-2010 15:13 |
|
|
Ні, максимум можна посабмітити 40*k раз, де k-кількість створених ботів |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 25-04-2010 16:14 |
|
|
webmaster написав:
та вся детективна історія із нелегальним перетином і подальною департацією Леброна на Україну наштовхнула на одну думку:
кожну задачу можна сабмітити 20 разів максимум, а якщо ще нелегально у Польщі посабмітити, то виходить 40 разом
контрабанда
Звісно це все проти правиль змагання!
Мене ще не вивезли.
webmaster написав:
оце так я і зробив!!!!!
взяв тести до задачі МАА із форуму і створив задачу у нас на сайті під номером 2000
щоб спробувати свій розвязок достатньо відправити його на задачу із номером 2000, помер потрібно вписати у поле "Задача"
Це для лінивих, які тести з форуму вручну провірити не можуть. Я взагалі розслабився, здавати ж можна до завтрашньої ночі зараз той циферблад тестую, чи коректно працює, і чи я всі константи правильно вбив, а за карту другу ще й не берусь дуже. За А взагалі не берусь ніяк.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 25-04-2010 17:50 |
|
|
|
З'явились результати за 4 раунд |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
| Опубліковано 25-04-2010 18:13 |
|
|
|
Вітаю з футболкою! |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 25-04-2010 19:28 |
|
|
Я теж! Цікаво, чи за місце в 256 потім ще одну дадуть, чи ні (я того в правилах не вичитав).
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 25-04-2010 19:54 |
|
|
Як вони миттєво реагують! Прийшла відповідь на моє
Hello. I have a problem with participating in this competition.
на пошту,
We will do it before publishing the final ranking. Stay tuned.
Best wishes,
Szymon Acedański
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 25-04-2010 21:41 |
|
|
|
LeBron написав:
Я теж! Цікаво, чи за місце в 256 потім ще одну дадуть, чи ні (я того в правилах не вичитав).
Минулого року я дістав дві футболки.
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 25-04-2010 21:52 |
|
|
DixonD написав:
Вітаю з футболкою!
класно, 2 нещасних бали, що я набрав за 4 тур, конвертнулись у Футболку, гарний курс у Польщі.
Ура!!!!
Змінив(ла) webmaster, 25-04-2010 21:52 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 26-04-2010 00:00 |
|
|
Додав задачу 2001
це 5B - WYS
П.С. після завершення змагання, ці задачу будуть видалені, оскільки ми не маємо права публікувати задачі і не претендуємо на авторство, це просто використавуємо даний сервіс як тестувальку систему |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
| Опубліковано 26-04-2010 00:59 |
|
|
Цитата з форуму:
Ja nie umiem albo czytać, albo liczyć: ile koszulek zostało wylosowanych po
każdej rundzie, a ile być powinno?
Czy organizatorzy indeksują tablice tak jak używane przez nas języki
programowania, od zera? ;-)
|
|
|
Birthday(s):
