Всем привет! Приглашаю открыть сезон соревнований по алгоритмическому программированию чемпионатом RuCode.Final. Это отличная возможность потренироваться перед более крупными олимпиадами и чемпами и порешать интересные сложные задачки от компетентных составителей (преподавателей МФТИ, УрФУ и НИУ ВШЭ).

Как проходит чемпионат?

Соревнование проходит в формате, близком к ICPC: проходишь отборы (онлайн, только в высший дивизион), попадаешь на финал, который является 5-ти часовым контестом. В течение этого времени каждая команда должна решить наибольшее количество задач. Задачи можно решать на разных языках программирования, наиболее популярные — C++, Python. Побеждает команда, которая верно решит больше всего задач при минимальном штрафном времени.

Почему именно RuCode?

• Хороший академический уровень: задачи дивизионов A/B подходят для красного рейтинга на Codeforces.

• Возможность попасть на стажировку к крутым патнёрам чемпионата: МТС, Яндекс, Сбер. Для этого нужно показать одно из лучших решений.

• Неплохие призы: игровая консоль, умная колонка, смарт-часы, много мерча.

• Кто поступает в вуз и займет призовое место, получит дополнительные баллы за индивидуалные достижения.

• Через пару часов после контеста начинается разморозка с великолепным комментатором, главный судьей Moscow Workshops ICPC Олегом Христенко aka Snark.

От университета может участвовать неограниченное количество команд и составу команды не обязательно быть из одного вуза.

Чемпионат RuCode пройдёт на площадках в более чем 20 городах России и онлайн.

Отборы в дивизион A/B проходят до 23 сентября! Финальный контест состоится 20 октября.

Привет, Codeforces!

Сегодня я расскажу о непопулярной технике в теории чисел.

Определение и элементарные свойства

Опр. Пусть $$$p > 2$$$ простое число, тогда квадратичным вычетом по модулю $$$p$$$ назовём все $$$1 \le x \le p - 1$$$, такие, что уравнение $$$a^2 \equiv x \pmod{p}$$$ имеет решения и квадратичным невычетом иначе. Обратите внимание, что $$$0$$$ не является ни квадратичным вычетом, ни квадратичным невычетом.

Теорема: Квадратичных вычетов и крадратичных невычетов поровну.

Теорема: Обозначим за $$$B$$$ квадратичный вычет, а за $$$H$$$ квадратичный невычет, тогда:

С помощью этих двух теорем уже можно решить 103428K - Tiny Stars.

Как проверить, число вычет или невычет?

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

Критерий Эйлера

$$$a$$$ является квадратичным вычетом по модулю $$$p$$$ тогда и только тогда, когда $$$a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$$$, и квадратичным невычетом тогда и только тогда, когда $$$a^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$.

Следствие: $$$-1$$$ является квадратичным вычетом тогда и только тогда, когда $$$p = 4k + 1$$$, для какого-то натурального $$$k$$$, и квадратичным невычетом тогда и только тогда, когда $$$p = 4k + 3$$$, для какого-то натурального $$$k$$$.

Очевидно, что сложность проверки числа $$$O(\log_2p)$$$.

int power(int a, int x, int mod) {
    int res = 1;
    while (x != 0) {
        if (x % 2 == 1) {
            res = 1ll * res * a % mod;
        }
        a = 1ll * a * a % mod;
        x /= 2;
    }
    return res;
}

bool check(int a, int p) {
    return power(a, (p - 1) / 2, p) == 1;
}

Нахождение $$$i$$$ по модулю $$$p$$$

Опр. $$$i$$$ это такое число, что $$$i^2 = -1$$$ $$$\implies$$$ $$$i$$$ по модулю $$$p$$$ назовём такое число, что $$$i ^ 2 \equiv -1 \pmod{p}$$$.

Алгоритм: Если $$$p = 4k + 3$$$ для какого-то натурального $$$k$$$, то такого $$$i$$$ не существует. Если $$$p = 2$$$, то $$$i = 1$$$. Иначе рассмотрим квадратичный невычет $$$a$$$, по критерию Эйлера нам известно, что $$$a^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$, тогда $$$a^{\frac{p - 1}{4}} \equiv i \pmod{p}$$$. Осталось лишь найти квадратичный невычет, для этого возьмём случайное $$$1 \le a \le p - 1$$$ и проверим его за $$$O(\log_2p)$$$, если это квадратичный вычет, то берём другое случайное $$$a$$$. Так как вычетов и невычетов поровну, то нам понадобится $$$O(1)$$$ таких проверок, а значит ожидаемое время работы алгоритма $$$O(\log_2p)$$$.

mt19937_64 mt(123);

int power(int a, int x, int mod) {
    int res = 1;
    while (x) {
        if (x % 2 == 1) {
            res = 1ll * res * a % mod;
        }
        a = 1ll * a * a % mod;
        x /= 2;
    }
    return res;
}

bool check(int a, int p) {
    return power(a, (p - 1) / 2, p) == 1;
}

int find_i(int p) {
    if (p % 4 == 3) {
        return -1;
    }
    if (p == 2) {
        return 1;
    }
    while (true) {
        int a = mt() % (p - 1) + 1;
        if (!check(a, p)) {
            return power(a, (p - 1) / 4, p);
        }
    }
}

Привет, Codeforces!

Я рад пригласить вас поучаствовать в Codeforces Round 959 при поддержке NEAR (Div. 1 + Div. 2), который пройдет в 18.07.2024 17:35 (Московское время). Вам будет предложено 8 задач и 2 часа на их решение. Он будет рейтинговым для всех участников.

Тема раунда — компьютерные игры!

Задачи для раунда готовили EJIC_B_KEDAX, zwezdinv, green_gold_dog, molney, azureglow и Sokol080808.

Мы от всей души хотим поблагодарить всех, кто оказал помощь в подготовке этого раунда:

1. Нашего координатора 74TrAkToR за полезные советы и помощь в подготовке задач!

2. Qwerty1232 за красную заинтересованность в тестировании раунда.

3. turmax за красно-чёрное тестирование раунда.

4. makrav, arbuzick, Anonymous_Noob, Hyperbolic за красное тестирование раунда.

5. ivan.alexeev, alenenok, Kihihihi, azureglow, pakhomovee, plagues, IzhtskiyTimofey, FelixArg, XaRDKoDblCH, meowcneil, AndreyPavlov, djm03178, MylnikovNikolay за жёлтое тестирование раунда.

6. Mr_Ell, krigare, marzipan, TimVen74, coder8080, MichsSS, PieArmy, tvladm, Vladosiya, bashem за фиолетовое тестирование раунда.

7. Algolagon, PoDuReMaN, zarubin, IgorA, leoper, kovir_aleksey_korroy, Kosya, Vamperox за синее тестирование раунда.

8. MakGeoKar, viteli за бирюзовое тестирование раунда.

9. Sonya_2009, ishaandas1 за зелёное тестирование раунда.

10. MikeMirzayanov за прекрасные системы Codeforces и Polygon.

Я также поздравляю green_gold_dog с днём рождения и желаю ему удачи на IOI.

Этот раунд проводится при поддержке NEAR!

NEAR была основана в 2017 году Ильёй Полосухиным, одним из создателей технологии трансформеров, и Александром Скидановым как попытка создать систему, которая бы решала задачи по спортивному программированию. О том, что получилось тогда, можно почитать здесь.

В итоге NEAR сделала большой поворот на 180° и начала работу над протоколом блокчейна, который запустила в 2020 году.

В этом году NEAR сформировала новую лабораторию, NEAR.AI, задача которой — создание будущего, в котором технологии искусственного интеллекта открыты и доступны всем, а не контролируются небольшим количеством мега-корпораций.

Одним из направлений работы является обучение моделей мыслить рационально, и задачи по спортивному программированию — это отличное окружение для этой задачи. В этом контексте NEAR приглашает всех участников Codeforces с рейтингом 1400 и выше помочь нам описать решения задач по спортивному программированию. Мы хотим описать решения большого количества задач разной сложности и платим за это сравнительно большое количество NEAR. Присоединиться к системе можно по этой ссылке.

Спасибо NEAR за предоставление следующих призов победителям:

• 1-е место: 512 Ⓝ;
• 2-е и 3-е места: 256 Ⓝ каждому;
• с 4-го по 7-е место: 128 Ⓝ каждому;
• и так далее;
• с 512-го по 1023-е место: 1 Ⓝ каждому.

Разбалловка: $$$500-1000-1250-2000-2000-2500-2750-3750$$$

Удачи!

UPD: Разбор

UPD2: Поздравляю победителей:

1. tourist

2. ecnerwala

3. orzdevinwang

4. Egor

5. jiangly

Привет, Codeforces!

Во 20.06.2023 17:35 (Московское время) начнётся Codeforces Round 881 (Div. 3).

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

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 7 задач и 2 часа и 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

• принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)

• не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи были придуманы и написаны: zwezdinv, EJIC_B_KEDAX, molney, Sokol080808, meowcneil, Vladosiya.

Также большое спасибо:

1. Vladosiya за координацию нашей работы.

2. MikeMirzayanov за системы Polygon и Codeforces и тестирование раунда.

3. tute7627 за красно-чёрное тестирование раунда.

4. ace5, sevlll777, oursaco, lightseba, gmusya, pavlekn, vrintle, tolbi за жёлтое тестирование раунда.

5. diskoteka, moonpie24, SashaT9, shell_wataru, MGod, Phantom_Performer, tarattata1, alex.kudryashov, Restricted, sdyakonov за фиолетовое тестирование раунда.

6. Alex239, MrEssiorx, olyazyryanova, marzipan, Pa_sha, Rudro25, azureglow, IHateGeometry, ivan.alexeev, krigare за синее тестирование раунда.

7. Guevara74, ctraxxd за бирюзовое тестирование раунда.

8. sahal, exhausted, viteli, prohamer80 за зелёное тестирование раунда.

Всем удачи!

UPD: Разбор.