Блог пользователя EJIC_B_KEDAX

Автор EJIC_B_KEDAX, история, 6 недель назад, По-русски

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

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

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

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

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

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

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

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

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

Автор EJIC_B_KEDAX, история, 3 месяца назад, По-русски

Привет, Codeforces!

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

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

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

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

Доказательство

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

$$$B \cdot B = B$$$
$$$H \cdot B = H$$$
$$$H \cdot H = B$$$
Доказательство

С помощью этих двух теорем уже можно решить 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)$$$.

Код

Нахождение $$$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)$$$.

Код

Полный текст и комментарии »

  • Проголосовать: нравится
  • +101
  • Проголосовать: не нравится

Автор EJIC_B_KEDAX, 4 месяца назад, перевод, По-русски

Привет, 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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -247
  • Проголосовать: не нравится

Автор EJIC_B_KEDAX, история, 16 месяцев назад, По-русски

Привет, 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: Разбор.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +377
  • Проголосовать: не нравится