27 мая завершился первый этап олимпиады Mail.Ru Group по программированию Russian Code Cup 2012. Всего в RCC’12 приняло участие более тысячи человек, из которых 200 лучших вышло в полуфинал соревнования, в отборочный раунд. Победителем первого квалификационного раунда стал студент мехмата ННГУ Владислав Епифанов из Нижнего Новгорода. Участниками было направлено 3391 решение, из которых 1066 были приняты системой как верные. 634 человека или 63% от общего числа участников, решили хотя бы одну задачу.

Russian Code Cup — индивидуальное соревнование по спортивному программированию, ежегодно проводимое Mail.Ru Group. Оно традиционно состоит из трех этапов: в начале лета проходят три квалификационных раунда, затем лучшие принимают участие в отборочном туре, первые пятьдесят победителей отборочного тура соревнуются в финале. Личного присутствия потребует только последний из них, остальные же проводятся онлайн. Все финалисты будут отмечены ценными подарками, а приз участнику, занявшему первое место, составит 10 000 долларов. За второе и третье место полагаются 5 000 и 3 000 долларов.

В статье я расскажу о задачах, которые предлагались участникам и о способах их решения. Краткий разбор задач опубликован на сайте сразу после завершения RCC, тут же я постараюсь разъяснить подробности настолько, чтобы решение было понятно даже начинающим программистам.

Linux Security Modules (LSM) — фреймворк, добавляющий в Linux поддержку различных моделей безопасности. LSM является частью ядра начиная с Linux версии 2.6. На данный момент в официальном ядре «обитают» модули безопасности SELinux, AppArmor, Tomoyo и Smack.

Работают модули параллельно с «родной» моделью безопасности Linux — избирательным управлением доступом (Discretionary Access Control, DAC). Проверки LSM вызываются на действия, разрешенные DAC.

Применять механизм LSM можно по-разному. В большинстве случаев это добавление мандатного управления доступом (как, например, в случае с SELinux). Кроме того, можно придумать собственную модель безопасности, реализовать ее в виде модуля и легко внедрить, используя фреймворк. Рассмотрим для примера реализацию модуля, который будет давать права на действия в системе при наличии особого USB-устройства.

Поглядим на схему и попытаемся разобраться, как работает хук LSM (на примере системного вызова open).

Если вы продаете онлайн-сервис, вам, наверное, хотелось бы видеть, что происходит на каждом этапе воронки продаж. Из анализа воронки можно сделать важные выводы: насколько понятен и удобен процесс установки и начальной настройки приложения, как много и какие клиенты становятся активными пользователями сервиса, какой процент переходит с бесплатной версии на платную. Кроме того, по динамике коэффициентов конверсии можно делать вывод об эффективности принимаемых мер для увеличения продаж.

Под катом вы найдете описание некоторых приемов работы с Excel, которые могут быть полезны при анализе массивов данных. Мы расскажем, как мы ведем управленческую статистику по сервису jivosite.ru с помощью сводных таблиц Excel и подключения к MySQL через ODBC на примере отчета по воронке продаж. Предлагаемый способ довольно прост и универсален, с его помощью можно строить красивые отчеты за считанные минуты.

В настоящей статье я хотел бы сделать обзор популярных алгоритмов для решения задачи нахождения максимальной общей подпоследовательности или LCS (longest common sequense). Так как акцент сделан на обучении, а не на реальном использовании, в качестве языка для реализации выбран Python, что позволит сократить количество кода и сконцентрироваться на основных идеях.

В оригинале название звучит как «How Not To Sort By Average Rating». Я подумал, что дословный перевод «Как не сортировать по усреднённому рейтингу» будет малопонятен и хуже отражает содержание статьи.

Постановка проблемы

Вы занимаетесь веб программированием. У вас есть пользователи, которые оценивают контент на вашем сайте. Вы хотите разместить высоко оцененный контент наверху, а низко оцененный — внизу. Для этого на основе пользовательских оценок вам нужно вычислить некий «рейтинг».

Неправильное решение №1

Рейтинг= (Число положительных оценок) - (Число отрицательных оценок)

Доброго времени суток!
Хотел бы с вами поделиться реализацией в MATLAB плотностного алгоритма для кластеризации пространственных данных с присутствием шума — DBSCAN (Density Based Spatial Clustering of Applications with Noise).

Особенности

Алгоритм DBSCAN был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы. Большинство алгоритмов, производящих плоское разбиение, создают кластеры по форме близкие к сферическим, так как минимизируют расстояние документов до центра кластера. Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы.

Вы участвовали в конкурсе параллельного программирования Acceler8 2011? Тогда этот пост — про вас.
Вы участвуете в проходящем сейчас конкурсе Аccelerate-2012? Тогда этот пост — для вас.
Вы принимали участие или только планируете участвовать в любом конкурсе спортивного программирования? А может, собираетесь начать свой первый самостоятельный проект? Тогда Вас, Штирлиц, я попрошу остаться с нами.

Этот пост — «разбор полетов» прошлогоднего конкурса Intel — Acceler8 2011, выполненный одним из членов жюри. Он прокомментировал ключевые конкурсные моменты, а также дал банальные и очевидные, но до сих пор актуальные советы по участию в подобных соревнованиях и по ведению проектов.

Итак,

Лично я, при всей моей вере в C++, считаю, что даже в редакции 2011, этот язык крайне недружелюбен в плане многозадачности и многопоточности. В качестве очередной попытки переубедить себя в этом я попробовал сделать многопоточный QuickSort.

В этом алгоритме получается после фазы разбиения запустить сортировки подчастей параллельно.

Вот мой наивный велосипед:

Введение

Структуры данных можно разделить на две группы: эфемерные (ephemeral) и персистентные (persistent).

Эфемерными называются структуры данных, хранящие только последнюю свою версию.
Персистентные структуры, то есть те, которые сохраняют все свои предыдущие версии, в свою очередь можно разделить еще на две подгруппы: если структура данных, позволяет изменять только последнюю версию, она называется частично персистентной (partially persistent), если же позволяется изменять любую версию, такая структура считается полностью персистентной (fully persistent).

Далее будет рассмотрено дерево отрезков и его полностью персистентная версия.
Весь код доступен на GitHub.

Под катом Вас ждет увлекательная история о том, как я сильно расстроился, познакомившись поближе с пользовательскими литералами (с нового стандарта), но при этом в последствии все же реализовал вышеупомянутую функцию, а также разобрался с constexpr, а позже еще и реабилитировал те самые литералы.

Мы уже писали о методах (Mobile First и Response Web Design), которые используем при разработке нашего сервиса. В этой статье я хочу поделиться с вами нашим опытом. То, что в теории кажется простым, на практике порой оборачивается кошмаром. Речь пойдет о том, как нам удается создавать универсальный веб-сервис, способный работать на большом количестве устройств.

Несколько месяцев назад на Гитхабе появилась очень неплохая коллекция паттернов и антипаттернов JavaScript и jQuery на все случаи жизни. Автор проекта Shi Chuan проделал отличную работу, собрав десятки примеров кода из книг и других источников. Репозиторий уже набрал почти полторы тысячи подписчиков и активно пополняется. Всё очень удобно разложено по категориям и откомментировано. Наслаждайтесь!

Это продолженеие статьи о помехоустойчивом кодировании, которая очень долго лежала в черновиках. В прошлой части нет ничего интересного с практической точки зрения — лишь общие сведения о том, зачем это нужно, где применяется и т.п. В данной части будут рассматриваться некоторые (самые простые) коды для обнаружения и/или исправления ошибок. Итак, поехали.

Гуляя по github'у я много раз видел в разных репозиториях одновременно и теги вида «v2.3.4» и коммиты с сообщениями типа «Bump version» и сменой номеров версии где-нибудь в lib/version.rb. И всегда мне казалось — что-то тут лишнее.

И когда пришло время задуматься и мне над расставлением номеров версий, я сказал: «Нет! Я не буду прописывать эти номера в файлы руками. Пусть это делает за меня моя система контроля версий!»

Вступление.

Прежде всего стоит сказать, что такое Код Хэмминга и для чего он, собственно, нужен. На Википедии даётся следующее определение:

Коды Хэмминга — наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления.

Другими словами, это алгоритм, который позволяет закодировать какое-либо информационное сообщение определённым образом и после передачи (например по сети) определить появилась ли какая-то ошибка в этом сообщении (к примеру из-за помех) и, при возможности, восстановить это сообщение. Сегодня, я опишу самый простой алгоритм Хемминга, который может исправлять лишь одну ошибку.

Начнём с описания ifttt.com

ifttt.com — это очень перспективный стартап, который в двух словах: Lets You Hack Together Web Apps, Without Coding Skills. Если детальнее, то это сервис позволяющий пользователям, без погружения в API огромного количества сервисов и каких либо знаний о разработке\языках программирования смешивать и автоматизировать различную активность друг с другом. В начале 2012 года получили посевные инвестиции в размере $1.5M.

В системе всего несколько сущностей, таких как задачи ( это правила ваших триггеров или реакций на внешнее событие), рецепты (это задачи, которые создали другие и поделились со всеми) и каналы ( это то, что с чем можно пытаться смешивать налаживая разные схемы выполнения задач, каждый канал следует привязать к ifttt.com ).


Экран задач выглядит так

Многие сталкивались с таким явлением как DDoS атака методом HTTP флуда. Нет, это не очередной туториал по настройке nginx, хочу представить свой модуль, работающий как быстрый фильтр между ботами и бэкэндом во время L7 DDoS атаки и позволяющий отсеивать мусорные запросы.

… или как я получил «Аленку» за консольное приложение

Существует довольно распространённое мнение, что выполнение различных тестовых заданий помогает очень быстро поднять свой профессиональный уровень. Я и сам люблю иногда откопать какое-нить мудреное тестовое и порешать его, чтобы быть постоянно в тонусе, как говорится. Как-то я выполнял конкурсное задание на стажировку в одну компанию, задачка показалась мне забавной и интересной, вот её краткий текст:

Представьте, что ваш коллега-нытик пришел рассказать о своей непростой задаче — ему нужно не просто упорядочить по возрастанию набор целых чисел, а выдать все элементы упорядоченного набора с L-го по R-й включительно!
Вы заявили, что это элементарная задача и, чтобы написать решение на языке C#, вам нужно десять минут. Ну, или час. Или два. Или шоколадка «Алёнка»

Предполагается, что в наборе допускаются дубликаты, и количество элементов будет не больше, чем 10^6.

К оценке решения есть несколько комментариев:

Ваш код будут оценивать и тестировать три программиста:

• Билл будет запускать ваше решение на тестах размером не больше 10Кб.
• В тестах Стивена количество запросов будет не больше 10^5, при этом количество запросов на добавление будет не больше 100.
• В тестах Марка количество запросов будет не больше 10^5.

Решение может быть очень интересным, поэтому я посчитал нужным его описать.

Итак, представьте ситуацию: у нас есть кроссплатформенный сервер который должен получать данные по UDP. Вооружившись Asio вы создаете сокет, создаете буфер для принимаемых данных и начинаете слушать.

udp::socket receiver(ios, udp::endpoint(udp::v4(), port));
char read_buf[buf_len];
udp::endpoint sender_point;
receiver.receive_from(buffer(read_buf, sizeof(read_buf)), sender_point);

Что произойдет если в полученной дейтаграмме будет больше данных, чем вы выделили для буфера?

Хотя я практически не смотрю телевизор, иногда появляется непреодолимое желание посмотреть что сейчас вещают в новостях. Часто это желание возникает когда дочка спит, и телевизор уже вне зоны доступа. Как вы понимаете выход один — IPTV.