| Автор |
RE: Potyczki Algorytmiczne 2010 |
alt
Користувач
Повідомлень: 29
Звідки: УжНУ, ІТФ, КСМ
Зареєстрований: 30.04.07 |
| Опубліковано 23-04-2010 01:23 |
|
|
|
webmaster написав:
У мене пройшли дві задачі, тобто сумарно за другий раунд маю 20 балів, а разом маю 30 балів.
Яка в тебе асимптотика на задачу А (про монети), писав через set?
В мене 19/20. На задачі А не пройшов по часу один тест з останньої групи |
   
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 23-04-2010 01:34 |
|
|
Простіша задача як і було заплановано була задача про гриби
GRZ - Mushrooms
Є N галявин і маємо t четвертин години (тобто t*15 хвилин), все до 1млн. На кожній із галявин росте по Ai грибів. Коли ми приходимо на галявину, то скашуємо повністю всі гриби із неї, але вони можу заново вирости, а для цього їм потрібно 2 одиниць часу, тобто 30 хвилин. Ми можемо рухатись між сусідніми галявинами, вперед і назад, щоб перейти на сусідню галавину потрібно одну одиницю часу, тобто 15 хвилин. Починається наша подорож у першій галявині і нам потрібно за t одиниць часу зібрати якомого більше грибів.
Жадність вона і у Африці жадність.
Тут тільки один момент, що ми можемо між двома сусідніми галявинами бігати і збирати із них гриби, туди, назад. Вони якраз за цей час встигають вирости. Тому починаємо із першої і рухаємось до останньої клітинки, але на кожному кроці пробуємо весь час що залишився побігати між даною галявиною і попередньої, відповідно будемо мат результат - скільки ми назбирали, щоб прийти сюди і скільки ми назбираємо, щоб побігати взад-перед. Серед всім можливих таких результатів потрібно вибрати максимальний.
От і все.
Змінив(ла) webmaster, 23-04-2010 01:39 |
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 23-04-2010 01:53 |
|
|
Наступна задача поскладніше буде.
MON - Coins
Дано скільки разів кидали монету (N) і число К (до 1 млн), далі дана стрічка із символів 'R' та 'O', чи як випадала монета під багатьох кидань. Потрібно із цієї стрічки вибрати таку підпослідовність, щоб кількість 'O' була більша від кількості 'R' рівно у К разів, звісно довжина цієї підпослідовності повинна бути максимальною. Потрібно вивести довжину цієї підпослідовності.
Як робив я.
Біжмо від початку стрічки до кінця, маємо певний лічильник, який на початку дорівнює 0. Коли зустрічаємо символ 'O', то лічильник зменшуємо на 1, коли зустрічаємо символ 'R', то лічильник збільшуємо на К. Після кожного символу заносимо зберігаємо значення даного лічильника. І так до кінця.
Якщо на двох різних позиціях значення лічильників рівне, то це означає, що між цими позиціями є якраз така підпослідовність, яка нам підходить.
Оскільки нам потрібно знайди найдовшу підпослідовність, то для кожного унікального значення лічильника варто зберігати тільки перше його входження.
І коли ми проходимо по і-ії позиції, то дивимось чи не було раніше такого значення лічильника, якщо так, то звіраємо, чи дана довжина не буде кращою ніж вже якась попередня.
Вся складність як це акуратно закодити. Я використав структуру
map<long long, int>
Тобто складність вийшла, N*logN.
Найдовше працювало на одному із 10го теста, "0.45s/1.00s".
Тут кажуть, що є лінійний розв'язок, я його не знаю.
Змінив(ла) webmaster, 23-04-2010 01:55 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 23-04-2010 02:31 |
|
|
Лінійний розв'язок цієї задачі полягає у тому, що замість map треба використовувати hash_map. Ця структура (середньостатистично) має складність вставки і запиту О(1). Для неї звісно (як для квіксорта) існують тести, на яких трапляється багато колізій і швидкість операцій стає лінійною, а не константною, але такі тести підібрати надзвичайно важко (в загальному випадку підібрати набір тестів, який би завалив всі розв'язки з hash_map-ом неможливо).
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 23-04-2010 02:39 |
|
|
Альтернативний підхід до цієї задачі без крутих структур даних (для паскалістів  ):
Можна порахувати суми так як казав Брюс, загнати їх в масив пар (сума, позиція). Потім посортувати цей масив. Далі за один пробіг розглянути в кожній групі пар з однаковою сумою найбільшу і найменшу позицію, а точніше різницю між ними, що і є довжиною відрізка. Найбільша довжина дасть відповідь. Складність розв'язку - О(N*logN)
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 23-04-2010 07:03 |
|
|
В мене жахливий результат. За першу 5/10. Після школи буду розбиратись, що не так, на всіх невірних тестах в мене відповідь більша за правильну. Написав окремий виняток для одної галявини, а якщо галявин більше одної, то пробував всі галявини як базу для намотування кіл (доходим до певної галявини, далі рухаємось "вперед-назад-вперед-назад..." і вибирав максимальну відповідь.
За другу 7/10, бо я не мав навіть приблизного уявлення, як її робити, тому тупо захешував і не парив собі голову.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 23-04-2010 07:22 |
|
|
І ше зараз вшарив, шо досить було для захисту від колізій в хеш вкрутити провірку на правильність результату, і воно б точно проходило всі тести. Тільки питання, чи через надлишок колізій і потрібних провірок не було б ТЛ. Певно не було б
а до першої такі великі тести...
Словом, я той тур так писав, як перший тур НетОІ, не дуже стараючись. І тепер зрозумів, що старатись явно треба було.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 23-04-2010 07:46 |
|
|
Помилку в першій знайшов. Помилка тупа. Я один рядок не взяв в дужки і одна умова на нього не впливала. Як наслідок, я заходив навіть туди, куди зайти не міг.
З виправленою помилкою набрає 10/10
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 24-04-2010 00:40 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 23-04-2010 07:52 |
|
|
Якщо тобі від того стане легше, то
я теж набрав на грибах 6 з 10, бо бракувало однієї умови і я заходив туди, куди не міг зайти.
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 23-04-2010 09:52 |
|
|
|
я заходив навіть туди, куди зайти не міг
хлопці і як там, куди не можна заходити, що кажуть?
питання по новій задачі
3B - ZAJ - Squared words
яка має бути відповідь для тетів:
1
a
та
2
ab
та
3
aaa
дякую
Змінив(ла) webmaster, 23-04-2010 10:35 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
slavko
Користувач
Повідомлень: 2
Звідки: LNU
Зареєстрований: 14.01.07 |
| Опубліковано 23-04-2010 10:31 |
|
|
щодо попередньої задачі - coins (MON)
то в мене була досить цікава евристика, але не правильна.
Нехай функція f(t) повертає чи існує послідовність довжини (k+1)*t. тобто t штук 'R' і k*t штук 'O'. На перший погляд, інтуєтивно, ця функція здається монотонно незростаючою. тобто якщо f(t) = 1, тоді і для всіх t0<t f(t0) = 1. І тоді можна зробити бінарний пошук. Але насправді є тести де це не виконується, наприклад, n=15 k=2 OOOOORRORRROOOO. Тут f(5)=1, але f(4)=0, тобто не існує послідовності довжини (2+1)*4 = 12, але існує довжини 15.
Перебравши багато тестів, можна побачити що таких тестів буде мало. У бінарному пошуці я вибирав випадкових 9 точок (замісь одної, вибирав кращу із тих), і враховував що можуть бути глюки в монотонності.
Для малих тестів в мене для гарантії працював перебір n*n/k. Але була проблема в критерії застосування перебору, і на всіх тестах працював перебір і, звичайно, затаймило. в результаті за цю задачу 4 бали. Але коли виправив баг і перетестував вручну, то дуже цікаво, що така евристика (не правильна) не пройшла лише 2 підтести. і при збільшенні кількості точок в бінарному пошучі, були кращі результати. і ще дуже цікаво, при srand і початковій кількості точок пройшли всі тести вручну.
Змінив(ла) slavko, 23-04-2010 10:32 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
alt
Користувач
Повідомлень: 29
Звідки: УжНУ, ІТФ, КСМ
Зареєстрований: 30.04.07 |
| Опубліковано 23-04-2010 12:56 |
|
|
|
webmaster написав:
питання по новій задачі
3B - ZAJ - Squared words
яка має бути відповідь для тетів:
1
a
= 1
2
ab
=2
3
aaa
=1 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
Shef
Головний Адміністратор
Повідомлень: 291
Зареєстрований: 20.04.07 |
| Опубліковано 23-04-2010 14:53 |
|
|
|
Відомо, що для задачі Coins існує розв'язок складності O(n) у найгіршому випадку, тобто без використання жодних структур даних. Хто опише тут такий розв'язок - отримає бонус! |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 23-04-2010 16:04 |
|
|
Який бонус, якщо не секрет? Не знаю, чи є стимул потрати 20 секунд на роздуми...
В мене ось яка проблема, я глянув в підсумкову таблицю, і там мене нема на моїй позиції Тобто в мене в таблиці 12 балів (тільки за вчорашній тур), а за перший тур балів в мене нема. І в списку сабмітів в мене тільки сабміти вчорашнього туру. А вчора в мене було 10 балів, в списку були сабміти першого туру... Акаунт один і той самий (пас не пам'ятаю, тому передираю з одного й того самого листа, який в поштовому ящику лежить першим, акаунти сплутати таким способом не міг).
Або я дійсно таки сплутав якимось дивним чином акаунти, і тепер буде непросто догнати перші 128 "футболкових" місць, або в них якісь глюки... І все одно буде складно догнати ті 128 футболкових.
З.І. Полазив по милу, дійсно в мене все ОК, бо співпадає інфа в вхідних повідомленнях - після першого туру прийшло повідомлення про мої сабміти на моє ім'я, і після другого те ж саме... Мені ця ситуація не дуже подобається... Що робити?
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 23-04-2010 16:14 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 23-04-2010 16:18 |
|
|
пиши адміністраторам/організаторам, хай вони рішають, що у тебе за проблема
настурожує твої роздуми про плутання паролів... щось не дуже у тебе там один аккаунт
а футболки можна отримати і не потрапляючи у топ128, вроді вони після кожного туру рандомом роздають декілька футболок, серед тих, хто мав хоча б якісь бали на даному турі, тому шанс отримати є завжди. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 23-04-2010 17:52 |
|
|
webmaster написав:
пиши адміністраторам/організаторам, хай вони рішають, що у тебе за проблема
настурожує твої роздуми про плутання паролів... щось не дуже у тебе там один аккаунт
а футболки можна отримати і не потрапляючи у топ128, вроді вони після кожного туру рандомом роздають декілька футболок, серед тих, хто мав хоча б якісь бали на даному турі, тому шанс отримати є завжди.
Першу реєстрацію я запоров - дещо не так заповнив, а дещо не так зрозумів... В ній вказано зовсім посторонній мейл. Я не впевнений, але мені здається, що я на неї навіть не заходив. Що нічого не відправляв - це точно. Другу реєстрацію написав нормально і вказав для неї пошту на гуглемилі. Під тим профілем я й писав перші 2 тури (принаймні я так думаю). От лист з паролем у мене лежить на гуглемилі, і він там єдиний такий. А про плутання я переживав, бо ще треба було провірити, чи він дійсно єдиний і чи дійсно я вказував інший мейл при "пробній" реєстрації. Розігрують 10 футболок після кожного туру, при тому, якщо перший в мене "випарувався", то шанс ще зменшився і зараз десь між шансом на проходження на очний тур і шансом на те, що мені ту футболку на вулиці випадковий прохожий подарує. Втішило хіба те, що я побачив щойно таблицю за минулий рік, 10 балів дуже не врятують, бо далі завдання все складніші і складніші... і те, що вчитався в правила, футболок в 2 рази більше, 256.
У них там є "міжнародний" варіант? Бо мені з тою польською досить тяжко, я б краще на англійській взявся за вирішення проблеми. І ще, з приводу адмінів, я такого навіть не найшов Там є хіба публічні питання, мило для ручного подання заявки на реєстрацію та форум на польській. Навіть пошти нема. Хіба що зараз пошту адмінів пошукаю.
Я подивлюсь, чи сьогодні все буде ок, якщо ОК - то вже від настрою залежить, чи буду завтра пробувати щось там вирішити з тим туром, чи ні. Все одно треба сьогодні акуратніше написати, вчора на більш простих (ніж сьогодні) задачах я недобрав балів 5-6 через неакуратність і неуважність, а не через те, що далекий від програмування. Якщо не ОК - завтра сяду за оскарження, головне знати, кому скаржитись. Бо третього профіля в мене точно нема
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 23-04-2010 20:22 |
|
|
Хе Маю пару файних звісток.
Перша: відправив сорс на сьогоднішню (ту, яку вже треба здати) В, попередні не зникли. Значить шанс повторення вчорашньої проблеми мінімальний.
Друга: раз я відправив В, значить я знаю, як вона робиться. Ну й задача, я вбив 40 хвилин на пошуки нормального розв'язку, бо оцінив асимптотику дуже "приблизно", та ще й не звернув увагу на час (орієнтувався на 1 секунду). А потім зрозумів, що там константа вийде як коеф при другій похідній від моєї асимп.функи, взятий в -1 степені, отже, за 5 с проходить найтупіший розв'язок. Головне знов не зробити якусь дурницю...
Третя: я маю такий-сякий розв'язок до А. Він явно паде на макстесті, але зараз буду шукати оптимальніші, це вже краще за нічого
Четверта, яка мала бути найголовнішою, відміняється, бо я довів неправильність свого розв'язку до задачі Шефа
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 23-04-2010 20:42 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
MoRZe
Користувач
Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09 |
| Опубліковано 23-04-2010 23:26 |
|
|
Цікаво почути, як правильно робиться 3А.
А то я ні до чого крім перебору, перетворення в стрінги і подальшого порівняння не додумався
_______47____ |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 23-04-2010 23:33 |
|
|
Угу, дуже цікаво, з урахуванням того, що ще є півтори години часу, і можна написати нормальний розвязок ))
Я зараз намагаюсь зробити так, щоб перебір за N*M*CONST, де CONST близько 500, запрацював Поки що не йде. Повний перебір в мене вже зданий.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 24-04-2010 00:47 |
|
|
За 10 хвилин до дедлайну я задумався, що в В виводити для слів, в яких жодна буква не повторюється більше 1 разу... Конкретно задумався. В мене виводить N. Ніби логічно. Але ніде в задачі чи на форумі щось не побачив схожих питань.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
Birthday(s):
