Archive

Archive for the ‘Математика’ Category

Розв’язання задачі MappingABC з TopCoder

Тут я розгляну розв’язок задачі MappingABC з TopCoder. Це задача з першого дивізіону другого рівня складності, тому вона вимагає певний рівень учасника для розв’язання.

Основне спостереження, яке допомагає в розв’язанні – це те, що для того, щоб порахувати всі прийнятні рядки ми можемо розбити рядок на три підрядки: до першого A – [0, FA], між першим A і останнім C – [FA, LC] і після останнього C – [LC,t.size()-1]. Ми рахуємо лише ті рядки в яких у [FA, LC] трапляється B.

Введемо дві множини для позначення символів які трапляються лише зовні [FA, LC] і інші, відповідно \mathcal O і \mathcal I. Тоді кількість прийнятних рядків така:
\prod_{s\in \mathcal O}\mbox{bitcount}(s) + \Big( \prod_{s\in \mathcal I}\mbox{bitcount}(s) - \prod_{s\in \mathcal I}\mbox{bitcount}(s \& 5) \Big).

Дивись коментарі в сирцевому коді для подальших роз’яснень.
Читати далі…

Категорії:C++, Комбінаторика Позначки:, ,

Розв’язання задачі BearEmptyCoin

Нещодавно спробував одну з задач першого дивізіону на топкодері. Задача виявилось надто складною для того, щоб я її самостійно розв’язав, навіть зрозуміти код, який вільно доступний, я не зміг. Отже, шукав допомоги в інтернеті. На запит “BearEmptyCoin” Google мені видав кілька посилань власне на topcoder.com і посилання на три блоги, китайською, корейською і японською мовами:) За допомогою Google перекладача, який досить невміло перекладає з цих мов, мені вдалось якось докопатись до істини. Тому, зараз я можу поділитись поясненням розв’язку із вами.

Формулювання

Маємо чесну монету, чисту з обох боків. Цією монетою ми гратимемо в гру. На початку рахунок 0, гра триватиме K раундів. Кожен раунд такий:
1. Вкидаємо монету.
2. Якщо верхній бік порожній, то записуємо на нього число, яке забажаємо.
3. Додаємо до рахунку число записане на верхньому боку монетки.
Для перемоги потрібно, щоб кінцевий рахунок був S.

На вході ми маємо K, S. Нехай P – ймовірність виграшу у разі слідування найоптимальнішій стратегії. Можна показати, що P помножена на 2^K є цілим числом. Повернути це число.
Читати далі…

Кількість відмінних двійкових дерев з n вершинами

Кількість відмінних двійкових дерев з n позначеними вершинами

Для двійкового дерева з n вершинами, кількість ребер становить n-1. Отже, цю задачу можна звести до кількості варіантів розташування n-1 ребер у n вершин. Ребро можна зробити або лівим, або правим. Читати далі…

Категорії:Математика Позначки:

Похідна кватерніона

Чому кватерніони, а не матриці повороту

З багатьох причин одиничні кватерніони, чотириелементні вектори, ліпший вибір ніж матриці повороту. Для симуляції руху твердого тіла найголовнішою причиною вибору кватерніонів є числовий самоплив. Припустимо, що ми відслідковуємо за орієнтацією твердого тіла за допомогою формули

\dot R(t) = \begin{pmatrix} 0 & -\omega_z(t) & \omega_y(t) \\ \omega_z(t) & 0 & -\omega_x(t) \\ -\omega_y(t) & \omega_x(t) & 0 \end{pmatrix} R(t),

тут R(t) є матрицею поворота, а вектор \omega(t) описує обертання тіла. Напрямок \omega(t) дає напрямок вісі обертання, а його довжина говорить про швидкість обертання.

По мірі того як ми оновлюємо R(t) згідно з цією формулою, ми неминуче отримуємо числовий самоплив. Числова помилка накопичуватиметься у коефіцієнтах матриці, і зрештою на екрані тіло відображатиметься скошеним.
Читати далі…

Категорії:Математика Позначки:

Адаптивний крок у чисельних методах розв’язування диференціальних рівнянь

Який би метод ми не використовували, головне завдання полягає у виборі хорошого кроку. Ідеально, ми хочемо вибрати h якомога більшим, але не настільки великим, щоб отримати надмірну помилку, або навіть гірше, спричинити нестабільність. Якщо ми оберемо фіксований крок, ми зможемо просуватись настільки швидко, наскільки нам дозволить найгірша секція x(t). Чого б нам хотілось, так це змінювати крок під час обчислень. Кожного разу коли ми можемо збільшити крок без введення завеликої помилки, ми повинні робити це. Відповідно, коли крок потрібно зменшити, щоб уникнути надмірної помилки, ми також повинні це робити. Це і є ідеєю адаптивного (пристосовного) крокування: зміна кроку h під час розв’язування звичайного диференціального рівняння (ЗДР).

У цій статті ми розглянемо пристосовне крокування для метода Ейлера. Базова ідея така. Припустимо, що ми маємо певний крок h, і ми хочемо знати як сильно ми можемо змінити його.
Читати далі…

Многочлени і перетворення Фур’є

Прямолінійний метод додавання двох многочленів вимагає \Theta(n) часу, а для множення — \Theta(n^2). Оскільки множення многочленів має значну практичну важливість, у цій статті ми покажемо як швидке перетворення Фур’є допомагає скоротити час на множення двох многочленів до \Theta(n \lg{n}).
Читати далі…

Як відрізнити випадкову послідовність від псевдовипадкової.

Прожилки

Чи була послідовність з H та T наведена нижче згенерована підкиданням збалансованої монети 100 разів чи її хтось набрав на клавіатурі в манері, що нагадує випадкову?

HTTTHTHTTHTTHTHTHTHT

TTTHHTHHTHTHTTHHHTHT

HHTHHTTTHHHTHTTHHHHT

THTTHHTHTHTHTHTTHTHH

HTTHHHTHTHHHTHTHHHTH

Тут напевне і не скажеш. Однак. Ця послідовність має характерну рису, яка притаманна для “випадкових” послідовностей згенерованих людьми і незвичайна для насправді випадкових послідовностей: а саме, тут немає тривалих прожилок з H або T. Насправді, жоден символ не з’являється більш як чотири рази поспіль. Наскільки це правдоподібно? Якщо ми підкинемо збалансовану монету 100 разів, яка ймовірність то, що ми не матимемо п’ять аверсів підряд?
Читати далі…