Чуть больше года назад я писал пост. За это время появились некоторые улучшения. Вы можете попробовать тестовую версию тут.

Улучшения интерфейса (текущая версия v0.1.6):

1. Добавлена русская локализация. Спасибо за это контрибьютеру.
2. Добавлена бесконечная прокрутка посылок. Теперь не нужно ждать несколько секунд, пока прогрузятся и отрисуются все 10к+ посылок :) Добавлен поиск посылок по задаче и участнику.
3. Добавлена темная тема.
4. Добавлена подсветка синтаксиса для Golang.
5. Добавлены уведомления для подтверждения почты и формы восстановление пароля через почту.

Улучшения бекенда (текущая версия v0.2.4):

1. Добавлено итерирование по длинному списку посылок. Добавлена фильтрация посылок по участнику, задаче и вердикту.
2. Добавлено подтверждение почты и восстановление пароля через почту.
3. На соревнование можно зарегистрировать скоуп (группа виртуальных пользователей), чтобы автоматически добавить всех пользователей скоупа в соревнование.
4. Добавлена базовая поддержка групп пользователей (группы для реальных пользователей). На данный момент не полностью реализована, но будет использоваться для раздачи доступа к контестам, задачам и скоупам.
5. Переделан кеш пакетов задач и rootfs-образов компиляторов.
6. Исправлены баги и корректно обработаны ситуации с паниками, приводящими к полному падению системы.
7. Добавлены лимиты на количество посылок и сообщений за период времени (по умолчанию 3 единицы в минуту).

Планы на версию интерфейса v0.2:

1. Довести интерфейс администратора до совершенства: избавиться от всех формочек ввода ID в пользу нечеткого поиск по участникам, задачам.
2. Улучшить отображение ошибок.
3. Поддержать красивый отчет ошибок компиляции (подсвечивать конкретные строки с ошибками).

Планы на версию бекенда v0.3:

1. Улучшить отображение ошибок во время сборки пакета задачи.
2. Реализовать интерфейс перетестирования посылок с фильтрами по задаче, вердикту, участнику и т.д.
3. Доделать группы пользователей.
4. Поддершать парсинг ошибки компиляции для разметки решения.
5. Под вопросом: Поддержать мультигенераторы polygon (зачем использовать такое).
6. Под вопросом: Поддержать pipelines в генераторах, например: gen 12 34 | convert > $ (зачем использовать такое).

Совсем недавно у меня возникла необходимость решить такую задачу:

Для заданных $$$a$$$ и $$$m$$$ найти все такие $$$x$$$, что: $$$x^2 \equiv a \pmod{m}$$$.

Спустя некоторое время поиска по интернету и тщательному разбору каждого случая, я получил решение, которое работает для любых $$$a$$$ и $$$m > 0$$$ за время $$$O(\sqrt{m})$$$, либо за время $$$O(\log^2(m))$$$ если $$$a$$$ и $$$m$$$ взаимнопростые (при наличии факторизации $$$m$$$).

Ниже приведу рассмотренные мной случаи и ссылки на статьи (или обсуждения) для алгоритмов:

1. $$$x^2 \equiv a \pmod{p}$$$, $$$a \ne 0$$$, $$$p$$$ — нечетное простое (ссылка).
2. $$$x^2 \equiv a \pmod{p^k}$$$, $$$a \ne 0$$$, $$$k > 0$$$, $$$\gcd(a, p) = 1$$$, $$$p$$$ — нечетное простое (ссылка).
3. $$$x^2 \equiv a \pmod{2^k}$$$, $$$a \ne 0$$$, $$$k > 0$$$, $$$\gcd(a, 2) = 1$$$ (cсылка).
4. $$$x^2 \equiv 0 \pmod{p^k}$$$, $$$k > 0$$$, $$$p$$$ — простое. Заметим, что в таком случае $$$x^2$$$ должен делиться на $$$p^k$$$. Тогда $$$x$$$ должен делиться на $$$p^{\lceil\frac{k}{2}\rceil}$$$. Отсюда получаем, что $$$x = i \cdot p^{\lceil\frac{k}{2}\rceil}$$$, $$$0 \le i < p^{\lfloor\frac{k}{2}\rfloor}$$$.
5. $$$x^2 \equiv p^s \pmod{p^k}$$$, $$$k > 0$$$, $$$0 < s < k$$$, $$$p$$$ — простое. Решения существуют только для $$$s = 2 \cdot t$$$. Доказывается от противного. Тогда очевидно, что $$$p^t$$$ является одним из решений ($$$(p^t)^2 = p^s$$$). Найдем оставшиеся решения. Пусть $$$x = p^t + y$$$, тогда $$$x^2 = p^s + 2 \cdot p^t \cdot y + y^2$$$. Заметим, что $$$2 \cdot p^t \cdot y + y^2$$$ должен делиться на $$$p^k$$$. В таком случае $$$x = p^t + i \cdot p^{\max(\lceil\frac{k}{2}\rceil, k - t - (p = 2))}$$$.
6. $$$x^2 \equiv q \cdot p^s \pmod{p^k}$$$, $$$k > 0$$$, $$$0 < s < k$$$, $$$\gcd(q, p) = 1$$$, $$$p$$$ — простое. Пусть $$$x_1$$$ решение для $$$x^2 \equiv q \pmod{p^k}$$$, а $$$x_2$$$ решение для $$$x^2 \equiv p^s \pmod{p^k}$$$. Тогда $$$x = x_1 \cdot x_2$$$ будет являться решением исходной задачи.

Последние три случая пришлось выводить самостоятельно, поэтому ссылок нет. Доказательства пока поленился оформить в этом посте, хотя в целом они не очень сложны.

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

Также приведу полную реализацию на Python (функция, решающая общий случай — discrete_sqrt):

def _bin_pow(a, b, m):
    c = 1
    while b > 0:
        if b % 2 == 1:
            c = c * a % m
        a = a * a % m
        b //= 2
    return c


# x^2 = a (mod p)
def _tonelli_shanks(a, p):
    assert a % p != 0
    assert p > 2
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    assert s > 0
    if _bin_pow(a, (p - 1) // 2, p) != 1:
        return []
    z = 2
    while _bin_pow(z, (p - 1) // 2, p) != p - 1:
        z += 1
        assert z < p
    c = _bin_pow(z, q, p)
    r = _bin_pow(a, (q + 1) // 2, p)
    t = _bin_pow(a, q, p)
    while t != 1:
        i = 1
        while i < s and _bin_pow(t, 2 ** i, p) != 1:
            i += 1
        assert i < s
        b = _bin_pow(c, 2 ** (s - i - 1), p)
        r = r * b % p
        t = t * b * b % p
        c = b * b % p
        s = i
    return sorted([r, p - r])


# x^2 = a (mod p^k)
def _generalized_tonelli_shanks(a, p, k):
    assert a % p != 0
    assert p > 2
    assert k > 0
    ans = []
    m = p ** k
    d = _bin_pow(a, (m - 2 * m // p + 1) // 2, m)
    for x in _tonelli_shanks(a, p):
        ans.append(_bin_pow(x, m // p, m) * d % m)
    return sorted(ans)


# x^2 = a (mod 2^k)
def _discrete_sqrt_2(a, k):
    assert k > 0
    assert a > 0
    if k == 1:
        return [1]
    if a % 8 != 1:
        return []
    ans = set()
    for x in [1, 3]:
        for i in range(3, k):
            j = ((x * x - a) // (2 ** i) % 2 + 2) % 2
            x = x + j * 2 ** (i - 1)
        ans.add(x)
        ans.add(2 ** k - x)
    return sorted(list(ans))


# x^2 = 0 (mod p^k)
def _discrete_sqrt_zero(p, k):
    assert p > 1
    assert k > 0
    ans = [0]
    x = p ** ((k + 1) // 2)
    for i in range(1, (p ** k) // x):
        ans.append(x * i)
    return ans


# x^2 = a (mod p^k)
def _discrete_sqrt_prime(a, p, k):
    assert p > 1
    assert k > 0
    if a == 0:
        return _discrete_sqrt_zero(p, k)
    q, s = a, 0
    while q % p == 0:
        q //= p
        s += 1
    if s == 0:
        if p == 2:
            return _discrete_sqrt_2(a, k)
        return _generalized_tonelli_shanks(a, p, k)
    if s % 2 != 0:
        return []
    xq = _discrete_sqrt_prime(q, p, k)
    x0 = p ** (s // 2)
    d = p ** max((k + 1) // 2, k - s // 2 - (1 if p == 2 else 0))
    ans = set()
    for i in range((p ** k) // d):
        for x in xq:
            ans.add((x0 + i * d) * x % (p ** k))
    return sorted(list(ans))


def _ex_gcd(a, b):
    x, xp = 1, 0
    y, yp = 0, 1
    while b != 0:
        q = a // b
        a, b = b, a - q * b
        x, xp = xp, x - q * xp
        y, yp = yp, y - q * yp
    return (a, x, y)


def _factorize(n):
    assert n > 0
    ans = []
    i = 2
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        ans.append(i)
        n //= i
    if n > 1:
        ans.append(n)
    return ans


# x^2 = a (mod m)
def discrete_sqrt(a, m):
    assert m > 0
    ans = [0]
    mans = 1
    fm = _factorize(m)
    it = 0
    while it < len(fm):
        jt = it
        while jt < len(fm) and fm[jt] == fm[it]:
            jt += 1
        p = fm[it]
        k = jt - it
        pk = p ** k
        x = _discrete_sqrt_prime(a % pk, p, k)
        g, x1, _ = _ex_gcd(mans, pk)
        assert g == 1
        nans = []
        for r0 in ans:
            for r1 in x:
                nans.append(((r0 + x1 * (r1 - r0) % pk * mans) % (mans * pk) + (mans * pk)) % (mans * pk))
        ans = nans
        mans *= pk
        it = jt
    return sorted(ans)

Привет всем. Хочу рассказать про свою разработку — тестирующую систему Solve с открытым исходным кодом. Да, можно сказать Yet Another Online Judge :) Но не стоит сразу расходиться, у нее есть некоторые крутые моменты и может быть вам захочется поднять собственную инсталляцию для проведения какого-нибудь соревнования.

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

Для кого этот пост

1. Для тех, кто хочет проводить соревнования по СП.
2. Для тех, кто готовит задачи преимущественно в великолепной системе Polygon.
3. Для тех, кто хочет запустить свою систему без разработки с нуля (например огранизации).
4. Для тех, кто просто интересуется.

Зачем вообще писать еще одну систему

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

1. Приятный, современный, а самое главное понятный интерфейс. Как для участника, так и для администратора. Если это не так, сделано все возможное, чтобы его можно было с легкостью заменить.
2. Отзывчивый интерфейс. Странички должны отстреливаться как пуля.
3. Актуальные технологии и подходы. Вообще, система больше заточена для запуска в облаках, но для небольших соревнований (порядка 2-3 сотен участников) вы вполне можете обойтись одной физической машинкой, возможно стоящей у вас дома, в университете либо где-то еще.

Если вы возьмете существующую тестирующую систему, то скорее всего она не будет соответствовать какому-то из этих пунктов (а может сразу нескольким). Не сказать, что это преимущества, скорее просто другие подходы.

Ключевая функциональность

1. Поддержка пакетов Polygon. Чтобы добавить задачу, вам нужно просто скачать пакет задачи из Polygon и загрузить его в систему. В дальнейшем будет добавлена поддержка автоматического скачивания пакета по URL задачи полигона.
2. Поддержка форматов соревнований ICPC и IOI. Тут все стандартно — работает так же как и везде, есть заморозка.
3. Поддержка контейнеризованных компиляторов. Очень полезная функциональность. По умолчанию система поставляется без единого компилятора. Компиляторы добавляются путем загрузки .tar.gz корневой файловой системы через API системы. Для удобства есть отдельная утилита с уже готовыми образами компиляторов.
4. AWS S3. Если вам надо надежно хранить все ресурсы (пакеты задач, архивы компиляторов, исходники решений), или же вы хотите запустить сразу несколько инстансов системы, данная опция будет для вас полезна. Если же вам все это не надо, то можете использовать локальный диск для хранения всех данных, это подходит для проведения небольших контестов и сборов.
5. Поддержка Scope Users — аналог внутренних пользователей Я.Контеста.
6. Поддержка интерактивных задач — как же без них. К сожалению, полигон не умеет автоматически строить нормальный протокол взаимодействия. Поэтому тут по старинке, чтобы получить нормальный PDF надо ручками задать input и output для семплов.

Как все это выглядит

Структура системы

Сама система разделена на 3 части:

1. Репозиторий бекенда Solve: https://github.com/udovin/solve
2. Репозиторий фронтенда Solve: https://github.com/udovin/solve-web
3. Репозиторий с утилитой для Solve: https://github.com/udovin/solve-tools

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

Как попробовать

Поднять бекенд можно по инструкции в репозитории: https://github.com/udovin/solve/blob/master/README.md

Поднять фронтенд можно командой npm install && npm start в репозитории (необходимо наличие node): https://github.com/udovin/solve-web

Загрузить набор компиляторов можно выполнив команду: go build . && ./solve-tools compilers create в репозитории: https://github.com/udovin/solve-tools

Можете также воспользоваться Docker образами: udovin/solve и udovin/solve-web. При этом udovin/solve необходимо запускать с опцией --priviledged (иначе Docker смонтирует /sys/fs/cgroup в read-only, и запуск решений не будет работать). При запуске через докер c --priviledged настоятельно рекомендуется не использовать --user root (по умолчанию должно запуститься от пользователя solve, но можете это указать явно для повышения безопасности). В теории также возможно запустить через rootless-docker.

Какие требования

Операционная система: Linux 5.11+.

Настроенные cgroup2. Как настроить можно почитать тут: https://rootlesscontaine.rs/getting-started/common/cgroup2/

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

PS. По вопросам вы всегда можете написать в л.с.

The XI BSUIR Open Programming Championship will be held from March 15 till April 29, 2023 (Minsk, Belarus).

Undergraduates and postgraduates of BSUIR, scholars, students from other universities and countries are invited to participate in the Championship.

The competition will take place in several rounds:

• Quarterfinals (distance, problems in Russian and English) — March 15 — March 20 (both included);
• Semifinals (distance/onsite semi-final, russian and english problems) — April 6;
• Students Final — April 22 (Belarusian State University of Informatics and Radioelectronics, Minsk);
• Schools Final — April 29 (Belarusian State University of Informatics and Radioelectronics, Minsk).

Quarterfinals are required only for BSUIR and school teams but other registered teams can also take part in it. Semifinals are required for all teams. BSUIR and school teams from Belarus take part onsite, other teams — online. Semifinals and Finals will be in ICPC format (5h contest).

To participate in the Championship teams need to be registered prior to April 3, 2023. Participation is free of charge — have fun.

The finalists are 30 (or more by jury decision) students teams, showed the best results in the qualifying rounds, but no more than:

• 7 teams of undergraduates and postgraduates of BSUIR;
• 2 teams from each of the universities of Belarus and abroad.

And 25 school teams showed the best results in the qualifying rounds.

University teams, which include at least two ICPC finalists 2022-2023, as well as high school teams, which include at least two winners of the final stage of the National Belarusian Olympiad in Informatics 2023, are allowed to participate in the finals of the Championship without passing the qualifying rounds.

Open BSUIR Programming Championship is held by the ICPC rules. During the Championship, the teams will be given 5 hours to solve 8 to 12 programming problems.

More information about the championship, as well as the problems and results of previous years, you may find at acm.bsuir.by.

here's a link there to a telegram channel and discussion, where you can talk to other participants and team up.

A little bit of last year video:
https://www.youtube.com/watch?v=nFZpkUFAO6Q
https://www.youtube.com/watch?v=07E0APqaB20

Привет всем. Наверное каждый зарегистрированный на CodeForces хоть раз слышал о таком замечательном сайте, как e-maxx. Там можно получить довольно подробную информацию по алгоритмам и реализацию на C++ — для копипаста (что не совсем хорошо) или усвоения особенностей реализации алгоритма в неидеальном реальном мире.

Алгоритмов то много, но вот про Link-Cut Tree ничего небыло, а это очень интересная структура и довольно простая. На самом деле, разобраться с ней было не так то и просто с первой попытки, но со второй все стало на свои места. После этого захотелось посмотреть на примеры реализации, выбрать лучшие решения и реализовать самостоятельно. Но вот с примерами возникли проблемы — я не смог найти внятной реализации (может быть плохо искал?). После десятка переписываний кода и долгого дебага я получил довольно внятную структуру данных, которую можно использовать как замену HLD.

Я поддержал следующие операции (все работают за $$$O(\log n)$$$ амортизировано):

$$$link(x, y)$$$ — соединить вершину $$$x$$$ с вершиной $$$y$$$ (в случае, если вершина x не является корнем, дерево будет переподвешено).

$$$cut(x)$$$ — удалить ребро от вершины $$$x$$$ до родителя.

$$$distance(x, y)$$$ — найти расстояние между вершинами.

$$$depth(x)$$$ — найти глубину вершины $$$x$$$.

$$$lca(x, y)$$$ — найти LCA вершин $$$x$$$ и $$$y$$$.

$$$parent(x)$$$ — найти родителя вершины $$$x$$$.

$$$root(x)$$$ — найти корень дерева, где находится вершина x.

$$$path(x, y)$$$ — проверить наличие пути между вершинами x и y.

$$$evert(x)$$$ — переподвесить дерево за вершину $$$x$$$.

Следующие операции переподвешивают дерево за вершину $$$y$$$:

$$$query(x, y)$$$ — посчитать сумму значений в вершинах на пути от $$$x$$$ до $$$y$$$.

$$$update(x, y, v)$$$ — прибавить $$$v$$$ к каждой вершине на пути от $$$x$$$ до $$$y$$$.

Исходный код здесь.

На данный момент не гарантирую, что в данной реализации нет багов, если кто и найдет, то пожалуйста расскажите, как они воспроизводятся.

Хочется услышать критику со стороны сообщества (и о том, что я плохо искал или написал плохой код).

Не хотел создавать данный пост — надеялся, что кто-то другой сделает, но нет :) На этой неделе проходят областные олимпиады в Беларуси. Все как обычно, два тура по 4 задачи, 5 часов на их решение. Здесь предлагаю обсудить задачки, решения и так далее.

Первый тур

Условия задач, обзорный лист.

Задача 1. Олимп-Сити

Задача 2. Дружелюбные соседи

Задача 3. Поворот плиток

Задача 4. Садовник

Решение на C++.

Второй тур

Условия задач, обзорный лист.

Задача 1. Доставка почты

Задача 2. Контрольная работа

Задача 3. Текстовый редактор

Задача 4. Послание инопланетянам

На этой неделе (26-30.03.2018) проходит республиканская олимпиада в г. Минске. Как обычно будет два тура, на которых будет предположительно по 4 задачи. К сожалению задачи будут, наверное, сильно сложными для меня, поэтому предлагаю обсудить решения в комментариях к этому посту. А можно обсудить не только задачи :)

Желаю удачи всем участвующим школьникам!

Привет всем. На этой неделе (8-12 января 2018 года) проходит областная олимпиада по информатике в Беларуси. Олимпиада проходит во всех областях (а их у нас всего шесть) в одно и то же время с одним и тем же набором задач. Здесь можно обсудить олимпиаду, ознакомиться с уловиями задач (надеюсь, что все участники олимпиады ознакомятся с условиями на самой олимпиаде) и, может быть, если я смогу решить, с решениями.

Всем участникам желаю удачи!

Very interesting contest.

But, how to solve task L, G and J?

Thanks in advance.

Very interesting contest.

But, how to solve task K, L and H?

Thanks in advance.

С 9 по 12 января 2017 года будет проходить областная олимпиада по информатике. Первый тур олимпиады состоится 10 января, второй — на следующий день. Постараюсь разместить здесь условия и решения задач как можно скорее, естественно не раньше начала самих туров :) В комментариях предлагаю обсудить задачи, поделиться идеями по поводу их решения, мыслями...

Всем участникам желаю удачи!

UPD. Первый тур завершен. Ниже можно почитать, как же получить полные баллы по задачам.

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

Привет, Codeforces!

Меня зовут Иван Удовин. Хочу сказать, что Codeforces Round #344 будет проведен в этот четверг (3 марта 2016 г. в 19:35). Это наш первый раунд, но это не означает, что задачи будут скучными и неинтересными. Авторы задач: я (wilcot) и Илья Хейфец (xfce8888). Говорим спасибо Алексею Вистяжу (netman) и неизвестному человеку (он не захотел, чтобы его добавляли в анонс). Также я хочу сказать спасибо Федору Коробейникову (Mediocrity) за отличную идею по задаче E.

Мы благодарим Глеба Евстропова (GlebsHP) за его помощь в подготовке соревнования, Марию Белову (Delinur) за перевод условий на английский язык, и, конечно, команду Codeforces и Михаила Мирзаянова за уникальные платформы Codeforces и Polygon.

Раунд будет состоять из пяти задач. Главные герои: Блейк — основатель компании «Blake Technologies» и Крис — работник этой компании.

Разбалловка стандартная: 500, 1000, 1500, 2000, 2500.

Желаю всем удачи на соревновании, высокого рейтинга и побольше задач с Accepted.

PS. Разбор можно просмотреть здесь.

PPS. Поздравляем победителей:

Div. 2:

1. lovelive

2. Murtazo.Ali

3. chychmek

4. chrome

5. Batman

Div. 1:

1. Um_nik

2. chffy

3. natsugiri

4. ershov.stanislav

5. AndreiNet