| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 24-04-2010 00:56 |
|
|
За 5 хвилин до дедлайну
Я вже питав на цьому форумі про такий випадок і Альт мені дав відповідь:
2
ab
=2
хоча ти трохи дивно написа:
жодна буква не повторюється більше 1 разу
так вона повторюється максимум 1 раз, чи взагалі не повторюється?
Змінив(ла) webmaster, 24-04-2010 00:57 |
   
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
Ramzes2
Користувач
Повідомлень: 65
Звідки: Черкаський національний університет
Зареєстрований: 16.04.07 |
| Опубліковано 24-04-2010 01:04 |
|
|
Класні змагання, година ночі, а скіки знайомих в онлайні  |
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 24-04-2010 01:06 |
|
|
вже завершився 3 раунд змагань
хоча результатів ще не має, але я вже почну писати розбір задач
3B - ZAJ - Squared words
Дано стічку довижини N (N <= 1000) і потрібно із цієї стрічки викинути якомого менше буква щоб стрічка складалась із двох однакових частин, тоді вона буде "квадратною", наприклад стрічка "shefshef" є квадратною, як і "brusbrus".
Родиться дуже просто.
Перебираємо середину, для кожної середини маємо дві підстрічки, одна та що зліва середини, а інша, та що справа середини. От і пробуємо із них утворити однакові стрічки викидаючи зайві символи. Це стандартний алгоритм на пошук максимально однакових підпослідовностей.
Отже складність виходить N*N*N, що при обмеження 5сек є цілком прийнятною.
Змінив(ла) webmaster, 24-04-2010 01:08 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 24-04-2010 01:11 |
|
|
вже є результати
3B пройшла повністю
3A набрала 4 бали, майже всі тести дали ТЛ, що і очікував, один бал дістався навіть із часом "6.02s/7.00s". Хоча на одному тесті ВА, взагалі дивно, але не обідно, бо на іншому тесті із цієї групи ТЛ
отже, сьогодні у мене +14
тепер разом маю +44, дуже гарно
П.С. зараз напишу розбір 3А |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
alt
Користувач
Повідомлень: 29
Звідки: УжНУ, ІТФ, КСМ
Зареєстрований: 30.04.07 |
| Опубліковано 24-04-2010 01:13 |
|
|
|
Писав (точніше оптимізовував) цілу ніч вчорашню А - в результаті 0. Досить несподівано |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 24-04-2010 01:16 |
|
|
webmaster написав:
хоча ти трохи дивно написа:
жодна буква не повторюється більше 1 разу
так вона повторюється максимум 1 раз, чи взагалі не повторюється?
Мав на увазі "зустрічається не більше 1 разу".
webmaster написав:
Родиться дуже просто.
Перебираємо середину, для кожної середини маємо дві підстрічки, одна та що зліва середини, а інша, та що справа середини. От і пробуємо із них утворити однакові стрічки викидаючи зайві символи. Це стандартний алгоритм на пошук максимально однакових підпослідовностей.
Отже складність виходить N*N*N, що при обмеження 5сек є цілком прийнятною.
Так і робив, навіть якимось дивом 10/10, найгірший час менше 2.5. Тут хоч тести дали досить красиво градуйовані, краще видно різницю, ніж в попередньому турі - є і на розв'язок повним перебором, і на розв'язок за N^5, і на розв'язок за N^4.
З приводу 3А - так і не вдалось нормально реалізвати свою ідею, вирішив обмежитись повним перебором, довго думав, на скільки його оцінять, на бал чи на два?.. В результаті 2/10
А моя ідея перебору була така: пробуєм даний підрядок поставити в число на всі позиції по черзі (справа, потім зі зсувом на 1 розряд вліво, на 2 і т.д.) для всіх проміжків по черзі і бінарником знаходим для кожного випадку значення кількості підходящих чисел до нижньої межі і до верхньої (до верхньої включно). Додаємо до відповіді для даного фрагменту різницю значень
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 24-04-2010 01:20 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 24-04-2010 01:28 |
|
|
Розбір задачі
3A - FRA - Fragments
Дано стрічку із цифр Х і нам порібно сказати скільки разів ця стрічка зустрічається у записі всіх чисел із заданої множини А. Множина А задається проміжками [a1,b1]...[an,bn], також проміжків може бути до 5000. Всі числа від 1 і до 10^19 (приблизно). Але це ще не все.... Нам дають багато тих Х і для кожного із них потрібно сказати відповідь, а тих Хів може бути взагалі 500 000.
Зрозуміло, що навіть просто порахувати для кожного Х на кожному проміжку, то вже виходить O(n*m)=5000*500000=2500000000.
Але що ж робити, будемо, для початку, працювати так.
Також перед початком написав повний перебір, який там бавиться із стрічками, переміщує у середині підстрічки і т.д., ну те що сказано в умові так воно тупо і робить.
Далі приступаємо, до написання більш розумного розв'язку.
Нехай у нас буде функція F, яка для заданого зразка Х і деякого числа N говорить скільки той зразок зустрічається разів у числах із проміжку [1,N]. Тоді ми можемо легко пробігтись по всім заданим проміжкам нашої множини і легко порахувати результат, для прикладу візьмем [ai,bi], тоді res = F(bi,X) - F(ai-1,X).
Складність цього розв'язку О(n*m)*O(F*), зрозуміло, що наша F має бути досить шустра.
І її можна зробити такою. Назвемо цей алгоритм порозрядним перебором, тобто біжимо по розрядам числа і дивимось, чи відрізняються відповідні розряди, якщо так, то ми можемо відразу дати певний результат суто арифметичними операціями, багато є задач де таке потрібно робити, і вони мені не подобаються. Отже у мене складність цієї функції вийшла 18*18, меншою її зробити, мабуть не вийде.
Отже загальна складність виходить
18*18*5000*500000=810000000000
одним словом - багато, але хоч щось.
Зараз напишу розбір кращого розв'язку. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 24-04-2010 01:29 |
|
|
|
LeBron написав:
Так і робив, навіть якимось дивом 10/10, найгірший час менше 2.5.
У мене найгірший час 0.88s/5.00s.
Я пробував у них у системі на найгіршому тесті, сам, то тоді мені дало 0,77. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 24-04-2010 01:38 |
|
|
Розбір задачі, спроба 2
3A - FRA - Fragments
Складність 18*18*5000*500000 , взагалі не підходить потрібно, щось із цим робити.
І є розв'язок кращий.
Але у мене вийшло як у тих казочках: "по вусам текло, по бороді текло, а у рот не попало", от і я не зміг то діло реалізувати, хоча декілька спроб робив.
Суть у тому, що ми всі зразки Х можемо зберегти у префіксному дереві (я назав так), тобто якщо у двох стрічках є однаковий превікс, то і їхні предки також будуть спільними. І для зручності це дерево буде 10арне, тобто із кожного елемента можна потрапити у 10 інших, тобто взалежності від цифри.
Тоді ми коли будемо у тій функції F порозрядно рухатись, то ми можемо відразу по цьому дереві рухатись.
От наприклад якщо вийде так, що для всіх зразків, що починаються на "22" ми можемо їх використати Р разів, то значить нам не потрібно вже всі іх перебирати, щоб кожному встановити це, а ми можемо тільки елементу у дереві, який відповідає за префікс "22" поставити значення. А потім вже для кожної стрічки із дерева повитягувати результати.
Сподіваюсь ідею можна вловити із того, що я написав. Але може щось змінюватись від реалізації, ще раз повторюсь у мене вийшло це реаліувати.
Складність:
5000*18*18*10=16200000 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 24-04-2010 01:39 |
|
|
В мене, якби я написав своє нормально (я там задуже з прапорцями намудрував, так і не дописав), виходить щось на зразок 18 (позицій)*54(ітерації в бінарник)*2(для обох чисел, верху і низу)*5000*500000, тобто ще гірше, ніж твій варіант. А порозрядка це взагалі знущання, я пам'ятаю, як пробував її писати для першої задачі другого дня на ВсеУкрі, це явно не моє.
webmaster написав:
LeBron написав:
Так і робив, навіть якимось дивом 10/10, найгірший час менше 2.5.
У мене найгірший час 0.88s/5.00s.
Я пробував у них у системі на найгіршому тесті, сам, то тоді мені дало 0,77.
Free Pascal v C++
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 24-04-2010 01:44 |
|
|
|
webmaster написав:
Суть у тому, що ми всі зразки Х можемо зберегти у префіксному дереві (я назав так), тобто якщо у двох стрічках є однаковий превікс, то і їхні предки також будуть спільними. І для зручності це дерево буде 10арне, тобто із кожного елемента можна потрапити у 10 інших, тобто взалежності від цифри.
Тоді ми коли будемо у тій функції F порозрядно рухатись, то ми можемо відразу по цьому дереві рухатись.
От наприклад якщо вийде так, що для всіх зразків, що починаються на "22" ми можемо їх використати Р разів, то значить нам не потрібно вже всі іх перебирати, щоб кожному встановити це, а ми можемо тільки елементу у дереві, який відповідає за префікс "22" поставити значення. А потім вже для кожної стрічки із дерева повитягувати результати.
Сподіваюсь ідею можна вловити із того, що я написав. Але може щось змінюватись від реалізації, ще раз повторюсь у мене вийшло це реаліувати.
Складність:
5000*18*18*10=16200000
До такого я не додумався
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 24-04-2010 01:52 |
|
|
|
LeBron написав:
А порозрядка це взагалі знущання, я пам'ятаю, як пробував її писати для першої задачі другого дня на ВсеУкрі, це явно не моє.
Той розв'язок, що я не зміг реалізувати, то він взагалі "порозряку" робить над деревом.
Змінив(ла) webmaster, 24-04-2010 01:52 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 24-04-2010 02:04 |
|
|
Я краще йду спати, бо я ту систему не зрозумію. Тільки що побачив, що якщо в адресі дописати ЮА, то буде нормально - на англ.мові. Так от, якщо я заходжу з оцим ЮА - в мене є результат першого туру, але нема другого і третього. А якщо без нього (так як лазив останні 2 дні) - є результат другого і третього туру, але нема першого. Логін і пароль ті самі. Відповідно, я є в обох рейтингах - і в укр./англ., де здавав в перший день, і в пол., де здавав в наступні 2... Це в них така система, щоб українці для зручності окремо бачили свої показники (без поляків)? Треба було здавати задачі в обох "режимах"? Заплутався... Мені нічого не загрожує в плані порушення правил за те, що я там начудив? Тепер можна просто дозмагатись в польському режимі, з місцем в загальному рейтингу, футболкою (от спокою мені не дає та футболка, хочеться мати пам'ять про останні тижні навчання в школі), правом на очний тур?..
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 24-04-2010 02:05 |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 24-04-2010 02:10 |
|
|
В українській версії по англійськи пише таке:
In case of problems with registration please contact us at contest@adbglobal.com.
Звернися до них, хай тобі скажуть, що робити. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
MoRZe
Користувач
Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09 |
| Опубліковано 24-04-2010 07:09 |
|
|
Ну що ж.
Маю 10 балів за третій раунд.
з них 10 за задачу В і 0 за А.
Робив В так, як казав brus, але сумнівався, що вона пройде бо не побачив що ТЛ=5с.
Ну а з Ашкою я такого начудив що вона в них запрацювала лише на двох тестах, а на іншших RE.
_______47____ |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 24-04-2010 07:40 |
|
|
Нажаль мій розв'язок на 3А набрав лише 4 з 10. Я не врахував, що деякі вхідні дані, а саме фрагменти які ми шукаємо, не влазять в інт64. Коли виправив проблему з 19-цифровими фрагментами і випадок коли останній відрізок закінчується на 10^19, пройшов усі тести.
Оцінка складності розв'язку: О((M+19*19/2*N*2*3)*logM) ~ O((M+1000*N)logM) ~ 105*10^6 операцій.
Насправді код невеликий - менше 200 стрічок, але пояснити трохи важко. Ну спробую. На крайніх випадках зупинятися не буду їх у цій задачі достатньо. Опишу основну ідею.
Посортуємо всі шаблони і будемо розглядати шаблони кожної довжини окремо. Для кожної довжини шаблону треба перебрати зсув справа, з яким буде зустрічатися шаблон. Тепер треба пройтися по всіх межах А і В. Для межі В будемо додавати до результату кількість входжень від 1 до В, для межі А - віднімати. Отже нехай нам треба знайти для межі В, скільки разів (абстрактний) шаблон довжини L зсунутий вліво на К позицій зустрічається в числах від 1 до В включно. (Наприклад якщо К=2, то шаблон 56 зустрічається в числі 25678 зсунутий вліво на К).
Нехай межа має вигляд:
ХХХYYYZZZ
Тут цифр "Z" є К штук (це різні цифри, просто я так позначив групу)
цифр "Y" є L штук.
Тоді всі шаблони, менші за YYY будуть зустрічатися на цьому місці (К вліво)
(XXX + 1) * 10^K разів
Шаблони які рівні YYY
XXX * 10^K + (ZZZ + 1) разів
Шаблони більші за YYY
XXX * 10^K разів
Правда випадок шаблонів, які починаються з нуля трохи інакший, але підхід такий самий.
Оскільки всі шаблони посортовані, то три випадки будуть зустрічатися у трьох групах шаблонів. Нам треба тільки бінарним пошуком пошукати дві межі між цими трьома групами. (Для випадку, коли ХХХ немає, тобто ця частина рівна нулю, треба буде ще шукати межу групи тих шаблонів, що починаються з нуля, тому в оцінці складності останній множник - 3 - це три бінарних пошуки).
Потім треба до кожної з груп додати (чи відняти, якщо це ліва межа відрізка) відповідний результат. Звісно не треба пробігатися по всіх шаблонах з групи, бо це дуже довго. Є класичний алгоритм, який дозволяє в кінці знайти суму для кожного елемента масиву, якщо по ходу виконання ми можемо додавати якесь число до набору послідовних елементів (Є така задача: дано відрізок, його зверху покривають великою кількістю менших відрізків і в кінці треба сказати для кожної цілочисельної точки на початковому відрізку скількома відрізками вона покрита).
В кінці треба відновити порядок шаблонів, так як вони йшли у вхідному файлі і вивести відповіді. Все.
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
| Опубліковано 24-04-2010 08:24 |
|
|
webmaster написав:
LeBron написав:
Так і робив, навіть якимось дивом 10/10, найгірший час менше 2.5.
У мене найгірший час 0.88s/5.00s.
Я пробував у них у системі на найгіршому тесті, сам, то тоді мені дало 0,77.
В мене найгірший час 1.08s/5.00s. Це або в них комп дуже шустрий, або тести криві. Бо щось подібне під макс тест мені давало на моєму компі під 4.5s після оптимізацій. Що саме цікаво, і для мене трохи дивно, що заміна написаної функції Max на аналогійний дефайн покращило час у 4-5 разів на моїй машині |
![dixond[злий_пес]acm[на]lviv[на]ua](../themes/Brasil-Fusion/forum/msn.gif)
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 24-04-2010 10:03 |
|
|
|
Ostap написав:
Посортуємо всі шаблони і будемо розглядати шаблони кожної довжини окремо. Для кожної довжини шаблону треба перебрати зсув справа, з яким буде зустрічатися шаблон. Тепер треба пройтися по всіх межах А і В. Для межі В будемо додавати до результату кількість входжень від 1 до В, для межі А - віднімати. Отже нехай нам треба знайти для межі В, скільки разів (абстрактний) шаблон довжини L зсунутий вліво на К позицій зустрічається в числах від 1 до В включно. (Наприклад якщо К=2, то шаблон 56 зустрічається в числі 25678 зсунутий вліво на К).
Ця частина може підійти тим, хто не зрозумів як робити порозрядно.
А далі алгоритм прикольний, і що само цікаво він інакший ніж той, що запропонував я. Можливо навіть існюють ще інакші алгоритими. Прикольна задачка. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
| Опубліковано 24-04-2010 10:41 |
|
|
|
Ostap написав:
Нажаль мій розв'язок на 3А набрав лише 4 з 10. Я не врахував, що деякі вхідні дані, а саме фрагменти які ми шукаємо, не влазять в інт64. Коли виправив проблему з 19-цифровими фрагментами і випадок коли останній відрізок закінчується на 10^19, пройшов усі тести.
Ну от це западло автори зробили і без того задача вже досить складна. Виходить мій явно таймлімічений розвязок набрав стільки балів як і твій.
Я цей момент не помітив також. |
|
|
| Автор |
RE: Potyczki Algorytmiczne 2010 |
alt
Користувач
Повідомлень: 29
Звідки: УжНУ, ІТФ, КСМ
Зареєстрований: 30.04.07 |
| Опубліковано 24-04-2010 12:02 |
|
|
|
alt написав:
Писав (точніше оптимізовував) цілу ніч вчорашню А - в результаті 0. Досить несподівано
Скачав тести, скачав надісланий мною розвязок, протестував на своїй машині - АС на всіх тестах, макс. час - 6.4 сек |
|
|
Birthday(s):
