Спортивное программирование *

Привет, Хабр! Я к вам с хорошими новостями: 28 ноября стартовала регистрация на чемпионат VK Cup! В этом году он посвящён только разработке (но не расстраивайтесь — дизайнерский трек мы перенесли в программу чемпионата VK Design Cup).

Классическое олимпиадное программирование пройдёт на площадке Codeforces — регистрируйтесь. К остальным трекам – мобильной разработке, машинному обучению и разработке на Go и JavaScript можно присоединиться на платформе All Cups.

Все полезные подробности о чемпионате — уже восьмом — читайте под катом.

В сентябре 2022 проходил хакатон «Машинное обучение на графах» от компании ВК на платформе «Цифровой прорыв». В хакатоне участвовала команда Лаборатории машинного обучения Альфа-Банка: Александр Сенин, Георгий Смирнов и Валерий Смирнов.

Мы заняли 1 место в хакатоне, далее подробно расскажем, как нам удалось победить.

Многие знакомы с алгоритмами дерева отрезков и корневой декомпозиции. Однако, не многие задаются вопросом о том, почему они устроены именно так, как они устроены :), и нельзя ли немного изменив их получить выигрыш во времени работы или затрачиваемой памяти. Одно из таких изменений я бы и хотел рассмотреть в этой статье, ведь я сам только недавно задумался об этом, хотя знаком с этими алгоритмами уже более 4 лет.

Математика говорит, что это невозможно, но нам всё равно!

В статье Пример как писать тесты в Yandex.Contest были даны рекомендации по для успешного прохождения тестов компании Яндекс. Один из тестов - поиск наибольшего числа заказов для заданной площади прямоугольника, мы решали простым перебором всех заказов, что увеличивает сложность поиска решения в геометрической прогрессии. Но есть более изящное решение. Однако такие решения приходят не сразу - задача прорабатывается на подкорке некоторое время (несколько дней), а потом вдруг, когда едешь в метро или гуляешь с собакой, бац и решение готово почти мгновенно.

Привет, меня зовут Данил Астафуров, я стажёр в команде лаборатории машинного обучения в Альфа-Банке, работаю над кредитным скорингом. В этом году я поучаствовал в соревнованиях «Цифровой прорыв: сезон искусственного интеллекта», на котором занял второе место. Это единственный технологический проект от АНО «Россия — страна возможностей». 

Соревнование длилось месяц и я был на первом месте с первого решения. Но за неделю до конца соревнования участников стал резко больше и меня обогнали. Отрыв от второго места был почти 0.1 (хотя там можно было скрыть лучший результат). Занятость стажера не давала отвлекаться, поэтому было решено, что пусть идёт всё своим чередом. Сейчас, спустя время, я могу разобрать своё решение и понять, как всё же можно было добраться до первого места.

Делюсь своим опытом как проходить тесты в Яндекс Контест. Уже после прохождения теста, который я провалил, решил повторить чисто для проверки сколько времени уйдет на написание кода, если уже знаешь что писать.

Суффиксное дерево (Suffix Tree, ST) – это структура данных, которая позволяет "проиндексировать" строку за линейное время от её длины, чтобы потом быстро находить подстроки (за время О(длина искомой подстроки)).

Тема построения Suffix Tree и его применения хорошо раскрыта в Интернет (википедия, статья на хабр про алгоритм Вейнера, язык Си, и статья на хабр про алгоритм Укконена). Но всегда есть соблазн поучаствовать в соревновании "написать проще и яснее", хотя шансов мало. Тем не менее, рискну.

Несмотря на сложность, алгоритм построения ST умещается в 35 строк на python (см. ниже метод _build_tree). Их буквально можно выучить и воспроизводить по памяти как некое произведение искусства, как воплощенный в набор символов труд человеческой мысли, причём не одного человека, и первые из них точно гении. :) Есть соблазн, всматриваясь в код, прикоснуться к великому и чему-то научиться.

Год назад ВСК получила незабываемый, позитивный опыт проведения олимпиады по программированию внутри своей компании. Известный факт: не все начинания, даже успешные, в итоге имеют свое продолжение. Но, благодаря энергии и настойчивости нашего DevRel и неравнодушных коллег из разных подразделений ВСК, в июле состоялась 2-я IT-олимпиада ВСК, которая, уже традиционно, объединила в online-режиме площадки 3-х регионов (Москва, Волгоград и Томск).

В этот раз наши аппетиты выросли, что было заметно по расширению границ мероприятия:

1. В отличие от 2021 года, кроме соревнований по программированию, мы провели состязания в навыках среди аналитиков и администраторов серверов приложений.

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

3. Среди участников были и внешние – сотрудники крупного партнера нашей компании.

4. Общее количество участников увеличилось почти в 2 раза.

Привет! В мае прошел очередной, уже 11-й, PHDays, а вместе с ним и The Standoff, и мы, как обычно, не остались без кейсов интересных атак.

В этот раз мы решили не описывать отдельные техники и тактики по матрице MITRE ATT&CK, ведь ни одна атака не возникает на пустом месте: всегда есть конкретный вектор проникновения в систему, путь продвижения по инфраструктуре и в конечном счете реализованное недопустимое событие. Предлагаем сосредоточиться на этом, так что приготовьтесь к полноценному расследованию!

Собеседования в крупные IT-компании почти всегда содержат алгоритмическую секцию — даже если вы собеседуетесь на позицию, в работе на которой алгоритмы возникать вряд ли будут. Ниже мы приводим пример задачи, с которой вы можете столкнуться на вашем следующем интервью. Мы расскажем, как эта задача решается, но мы настоятельно рекомендуем вам читать решение только после того, как вы попробуете решить задачу самостоятельно: во-первых, это отличная тренировка; во-вторых, вы лучше запомните решение, если придумаете его сами (не отказывайте себе в этом удовольствии!); в-третьих, даже если вы подумаете над задачей, но не решите её, время не будет потеряно: прочитав потом решение, вы лучше его поймёте и оцените его красоту.

Меня зовут Абай Баймуканов, я – разработчик-алгоритмист международной IT-компании Relog. Уже несколько лет увлекаюсь олимпиадными программированием, поэтому в этой статье хотел бы поделиться своим видением по этому поводу.

Быть олимпиадником по спортивному программированию довольно весело и интересно. Но быть жюри и составителем задач для самих олимпиад – достаточно ответственное и не менее интересное дело. Спортивное программирование - это те же математические задачки на логику, которые всего то нужно решить. Но программирование, в отличие от любого другого предмета, уникально тем, что решение нужно еще и реализовать в виде компьютерной программы.

Здесь есть свой нюанс: программа может работать настолько долго, сколько не существует даже вселенная, а может сработать за долю секунды. Причем в обоих случаях результат будет один и тот же. Любой олимпиадник стремится к тому, чтобы его программа была как можно эффективнее. Для этого существуют алгоритмы и структуры данных - методы, позволяющие сделать определенные программы более эффективными с точки зрения необходимого времени или памяти компьютера.

Спектр сложности у задач по спортивному программированию достаточно широкий: от задач для новичков до задач мирового уровня для вундеркиндов. Большинство соревнований проводится практически одном и том же формате, то есть дается несколько задач, на их решение 5 часов и за это время нужно решить как можно больше.

На школьных олимпиадах обычно за каждую задачу можно получить от 0 до 100 баллов и общим результатом будет суммарный балл за все задачи, у студентов в результат идет просто количество решенных задач, а если есть участники, решившие одно и то же количество задач, то они группируют по убыванию штрафа. Чем дольше решаешь задачу или чем больше на них нужно попыток решить, тем больше штрафов за нее получишь.

Привет! Я Люба Давыдова из компании БКС. Занимаюсь развитием ИТ бренда в компании. Расскажу об одном из наших последних мероприятий.

В декабре мы с партнерами из «Сколково» провели свое первое онлайн-соревнование для разработчиков. Мы решили поделиться опытом организации мероприятия и примерами тематических задач.

С 14 по 16 ноября 2021 года на киберполигоне The Standoff происходило третье противостояние между атакующими и защитниками. Сражения прошли в стремительно развивающемся городе-государстве F. Реализовывать недопустимые события ринулись десять суперскилованных команд атакующих, а на бастионах защиты их встречали пять команд защитников. Как обычно, сторонним пристальным наблюдателем всего происходящего на киберарене был security operations center (SOC).

Несколько команд экспертного центра безопасности Positive Technologies — PT Expert Security Center (PT ESC), в том числе и наш отдел обнаружения вредоносного ПО — не смогли удержаться и таки засунули свои носы сенсоры в гущу событий. С помощью песочницы PT Sandbox мы старательно изучали все файлы, которые влетали в инфраструктуру противостояния, и, вооружившись различными технологиями, искали вредоносный код. По традиции знакомим вас с результатами анализа. А вспомнить, как это было полгода назад, вам поможет прошлый рассказ.

• расскажем, как настроить «Яндекс.Контест»;
• приведём задачи;
• покажем, во сколько нам обошлась олимпиада (сразу признаемся: сумма вышла настолько смехотворной, что мы спрячем её под кат).

15–16 ноября в рамках крупнейшего российского киберполигона пройдет конкурс The Standoff Digital Art, участникам которого предложат взломать цифровые картины современных представителей российского диджитал-арта: Desinfo, Meta Rite, Артём Ткач, volv_victory, Anomalit Kate и Loit.

Каждая картина представлена в виде уникального NFT-токена, который предстоит испытать на прочность исследователям безопасности со всего мира. Чтобы завладеть картиной, им придется найти уязвимости в смарт-контрактах путем анализа исходного кода. Те, кто первыми успешно реализуют атаку, получат 🎁🎉 ценные призы от компаний Positive Technologies и ГК Innostage.

Конкурс пройдет в онлайн-формате. Присоединяйтесь к трансляции на сайте standoff365.com, чтобы увидеть это.

UPD: разбор заданий с конкурса уже готов! Читайте его здесь.

В прошлой статье мы писали, что давно пора снова собрать русскоязычное сообщество rust-разработчиков, и поэтому в декабре проведем RustCon Russia. Так вот, при подготовке конференции мы поняли, что есть два разных сегмента тех, кому интересен Rust. Первые — это те, кто уже пишут на нем. Вторые - те, кто только начал изучать или подумывает об этом. Питонисты, плюсеры, рубисты - все, кто понял, что у раста есть очень крутые преимущества, и пора бы изучить их подробнее.

В-общем, анонсируем RustCon Contest — индивидуальные соревнования по программированию на rust, где опытные разработчики могут внести вклад в открытые rust-проекты, а начинающие - попробовать rust на вкус на простых и чуть более сложных задачках. И те, и другие могут выиграть билет на RustCon, получить фирменный мерч или приличную скидку. Подробности под катом.

С какого возраста можно обучать ребенка программированию и какой язык лучше выбрать? Как попасть на самые крутые IT-направления в лучшие вузы? Становятся ли дети разработчиков разработчиками? Как попасть на стажировку в Яндекс или на работу в Google?

Обо всем этом нам рассказывает Михаил Рубинчик — лидер и главный тренер по спортивному программированию в Уральском федеральном университете и основатель онлайн-школы по спортивному программированию SPGuide. Подробности под катом

Как происходит проверка решения

source.cpp:
#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
}

Есть задача "Двенадцатая степень":

Перед Васей написаны целые числа от 0 до 2021. Он произвольно разбивает их на пары, внутри каждой пары суммирует, а все полученные суммы перемножает. Может ли у него получиться двенадцатая степень натурального числа?

Конкурс!

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

Порог входа в конкурс (по сложности) потихоньку растет, но до сих пор не стал запредельным. Еще не поздно решить задачу, прочитать условия конкурса, начать участвовать — и победить. Успехов :)