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

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

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

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

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

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

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

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

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

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

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

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

Привет, Codeforces!

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

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

Опр. Пусть $$$p \gt 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, sadness и Sokol080808.

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

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

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

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

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

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

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

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

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

9. _supersonic_, 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. zhoukangyang

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, moonpieXXIV, JuicyGrape, shell_wataru, MGod, Phantom_Performer, tarattata1, alex.kudryashov, Restricted, abs0lute за фиолетовое тестирование раунда.

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

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

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

Всем удачи!

UPD: Разбор.