burunduk3's blog

By burunduk3, history, 15 months ago, In Russian,

Вступление

Недавно мне рассказали про некое «преобразование Монтгомери», которое якобы сводит вычисления по произвольному модулю к вычислениям по модулю 2k. Звучит интересно: во всяких вычислениях по простому модулю самое долгое место — как раз взятие по модулю после каждой операции. Но как именно преобразование работает, не рассказали. Повезло, что я живу в эпоху интернета и любую интересующую меня тему могу с тем или иным успехом загуглить.

Read more »

 
 
 
 
  • Vote: I like it  
  • +145
  • Vote: I do not like it  

By burunduk3, 4 years ago, In Russian,

Коварные стрелочки

Типичный посетитель сайта codeforces.com, наверное, знает, как искать минимальное (или даже максимальное) остовное дерево (а то и остовный лес). Умеет писать алгоритм Прима, алгоритм Крускала. Кое-кто может быть даже в курсе, что всё это частные случаи алгоритма Борувки, который в 1926-м году рассказывал, как оптимально электрифицировать Моравию (регион Чехии). Вот только правильно работают эти алгоритмы исключительно для неориентированных графов

Read more »

 
 
 
 
  • Vote: I like it  
  • +67
  • Vote: I do not like it  

By burunduk3, 4 years ago, In Russian,

Привет

Некоторое время назад я наткнулся на персистентные структуры данных и, в частности, на описание персистентной очереди на вики-конспектах ИТМО. Всё бы хорошо, только как-то сложновато: чтобы реализовать одну маленькую очередь используется пять (в другом варианте — шесть) стеков.

Кратно напомню историю проблемы, уложусь всего в четыре стека и заодно немного расскажу про персистентность вообще

Read more »

 
 
 
 
  • Vote: I like it  
  • +144
  • Vote: I do not like it