Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Можно ввести несколько слов — все они попадут в требования к поиску. Кроме того, осуществляется поиск по словоформам и, если повезет, по синонимам. Поддерживается поиск по названию, автору и специальный синтаксис запросов. Примеры:

  • 305 — ищет все посты, содержащие 305, найдет посты про Раунд 305
  • andrew stankevich contests — можно писать сразу много слов, будут искаться все
  • user:mikemirzayanov title:сазанка — ищет все посты в названии со словом "сазанка" авторства MikeMirzayanov
  • "vk cup" — можно использовать кавычку, чтобы искать точные совпадения
  • title:educational — искать в названии

Результаты

1.
Автор MikeMirzayanov, 13 дней назад, перевод, По-русски
Codeforces Round 1134 (Div. 4) Привет, Codeforces! Я рад пригласить вас на раунд [contest:2290], который пройдёт [contest_time:2290]. После довольно долгого перерыва я снова взялся за подготовку задач — на этот раз в паре с ИИ-агентами. Для меня это эксперимент по возвращению в подготовку задач, и мы вместе посмотрим, насколько ИИ окажется успешным напарником в этой деятельности. Жду на раунде и участников четвёртого дивизиона, и всех, кто решит поучаствовать вне конкурса! <div style="height:1em;"></div> <spoiler summary="Почему я решил стать автором этого раунда (немного лирики и графоманства)"> Да, я прямо сейчас надиктовываю эти слова в телефон, чтобы позже облечь их в форму перед вами. Мы живём в удивительное время, когда очень многое меняется. Я программирую уже больше 25 лет и на протяжении всего этого времени каждый день писал код, каждый день решал задачи. Сначала это были больше задачи по программированию — они настолько меня увлекали, что весь мир вращался вокруг этих задач, я был по...

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

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

2.
Автор geranazavr555, история, 6 лет назад, По-русски
Трансляции на Codeforces Всем привет! Сегодня на Codeforces появилась поддержка трансляций (стримов)! Спасибо Геннадию [user:tourist,2020-10-21] Короткевичу за отличную идею! Поддерживаются две популярные платформы &mdash; Twitch и YouTube. Пока возможность добавлять трансляции на Codeforces открыта красным участникам и по индивидуальным приглашениям. Позднее, мы, возможно, откроем эту возможность большему числу пользователей. Идея состоит в том, чтобы стримеры могли анонсировать свои трансляции на аудиторию Codeforces. Для этого трансляцию нужно добавить на сайт, используя специальный раздел в профиле. Обратите внимание, что при добавлении Twitch-трансляции вам надо указать просто URL вашего канала, а при добавлении YouTube-трансляции &mdash; её уникальную короткую ссылку (ссылку на видео youtu.be/…). Незадолго до старта трансляции в сайдбаре справа появится уведомление о предстоящей трансляции, которое будут видеть все посетители сайта. Если вы указали название трансляции только на русском язы...

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

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

3.
Автор MikeMirzayanov, 9 лет назад, По-русски
Codeforces: серия обновлений (рейтинг, раунды) <img src="/predownloaded/21/a3/21a33b497ee8a34a678befc3f79745eb69a9cf07.png" style="float:right; margin: 0 1em 1em 1em;"/> Привет, Codeforces! Настало время новостей. Надеюсь, вам понравится! * Мы немного опускаем границу рейтинга для оранжевых участников. Таким образом, теперь оранжевый рейтинг (и звание _мастер_) будет начинаться от 2100 единиц рейтинга. * Нижняя граница рейтинга для _легендарных гроссмейстеров_ увеличена до 3000 единиц рейтинга. Таким образом, прямо сейчас в сообществе 14 участников соответствуют этому требованию. Настоящие легенды! * Для раундов серии «только для Div. 2» увеличена верхняя граница рейтинга для официального участия. Теперь все, чей рейтинг менее 2100 (то есть до _кандидатов в мастера_ включительно) смогут зарегистрироваться на такие раунды для участия в конкурсе, их рейтинг будет обновлён по результатам раунда. Мы не планируем повышать сложность Div. 2 раундов. Практика показывает, что задачи таких раундов и сейчас интересны и полезны ...

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

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

4.
Автор tourist, 5 лет назад, По-русски
VK Cup 2021 — Финал (Engine) и Codeforces Round #740 И снова привет! [contest:1563] начнётся совсем скоро: в [contest_time:1563]. В финале примут участие [32 лучших участника отборочного раунда](https://codeforces.me/contest/1544/standings), которые разыграют между собой солидные призы: - 1-е место — 300 000 рублей; - 2-е — 250 000; - 3-е — 150 000; - 4-е — 100 000; - 5-е — 80 000; - 6-е — 30 000; - и 7-е — 20 000. Следить за ходом соревнования и болеть за любимых участников можно будет [по этой ссылке](https://codeforces.me/spectator/ranklist/2488e608fc1223994a45bca34b4a2c51). Также смотрите прямую трансляцию [в сообществе Команды ВКонтакте](https://vk.com/tech) (нет, спойлеров к задачам финала не будет). Всех остальных, кроме финалистов VK Cup 2021, мы приглашаем на [contest:1558] и [contest:1561], которые начнутся на пару дней позже: во [contest_time:1558]. Раунды будут рейтинговыми для всех. Все задачи были придуманы и подготовлены мной. Большое спасибо всем, без кого этот раунд не смог бы состояться: [user:KAN...

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

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

5.
Автор Wind_Eagle, 5 лет назад, По-русски
Codeforces Round #741. Как развлекается автор контеста. Привет, Codeforces! Не так давно прошел мой второй раунд, Codeforces #741 (Div. 2). Перед его началом, я задумался: ведь наверняка на моем раунде, как и на любом другом, процветает читерство? И я решил сделать кое-что необычное. Как известно из [одного блога о читерах](https://codeforces.me/blog/entry/93893), искать telegram/youtube каналы с читерами не составляет никакого труда. И я решил найти парочку и вступить в них... Итак, первая telegram-группа, которую я нашел, это [ссылки пока нет]. В ней было не так много читеров, но все же они были, вот пример: <spoiler summary="Картинка"> <a href="https://imgbb.com/"><img src="https://i.ibb.co/kJqMzMS/pic1.png" alt="pic1" border="0"></a> </spoiler> Я вступил в эту telegram-группу, и состоялся содержательный диалог примерно такого плана: <spoiler summary="Картинка"> <a href="https://ibb.co/1mC2csG"><img src="https://i.ibb.co/VqFB6HY/pic2.png" alt="pic2" border="0"></a> </spoiler> Это может показаться невероятным, но ...

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

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

6.
Автор ATSTNG, история, 7 лет назад, перевод, По-русски
[Tutorial] Пересечение матроидов простыми словами **[This article is also available in [English](https://codeforces.me/blog/entry/69287?locale=en)]** Привет, CodeForces. Я думаю, что матроиды &mdash; это прекрасные и очень мощные структуры, однако, не настолько хорошо известные в спортивном программировании. Я познакомился с матроидами на Зимних Петрозаводских Сборах 2019. Там была задача, которая очевидно не решалась обычными способами, известными мне тогда. Разбор этой задачи состоял буквально из трех слов “just matroid intersection”. Тогда мне потребовалось больше двух дней дорешивания чтоб найти всю необходимую информацию и детали и написать решение, которое получает Accepted. И намного больше времени мне потребовалось чтобы понять почему это действительно работает и как именно это работает. (Я до сих пор сомневаюсь в некоторых деталях.) Конечно, совершенно не трудно нагуглить все необходимые определения и статьи, связанные с этой темой, но мне кажется, что все они больше сконцентрированы на математической теории, с...
**Расширенный матроид. Прямая сумма матроидов.** Мы можем рассматривать два отдельных матроида, как

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

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

7.
Автор Xellos, история, 11 лет назад, перевод, По-русски
CF Round #333 <center><img src="https://lh3.googleusercontent.com/--HN6DjhjZaM/VlNt6NQ6olI/AAAAAAAAAuQ/w6wSlj7rl0k/s250-Ic42/"></img><div>(<a href="http://i2.kym-cdn.com/photos/images/newsfeed/000/582/289/38f.gif">оригинальная версия</a>)</div></center> Привет всем! CF раунд #333 (обе дивизионы) состоится [сегодня](https://www.timeanddate.com/worldclock/fixedtime.html?day=24&month=11&year=2015&hour=19&min=35&sec=0&p1=166). Авторы раунда &mdash; я и [user:Baklazan,2015-11-18]. Просто случайно, мои задачи пронумерованы чётно и задачи Баклажана пронумерованы нечётно. И тепер можете раздумать, если они пронумерованы от 0 или от 1 :D. Как обычно, благодарим [user:GlebsHP,2015-11-19] за его помощь (в частности, за помощи упростить некоторые задачи), [user:MikeMirzayanov,2015-11-19] за CF и Polygon, [user:Delinur,2015-11-24] за перевод условий задач на русский язык и тестерам [user:misof,2015-11-24], [user:Mimino,2015-11-24], [user:AlexFetisov,2015-11-24] и [user:winger,2015-11-24]. Желаю хо...

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

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

8.
Автор MikeMirzayanov, 7 лет назад, По-русски
Testlib: Opts — парсинг параметров командной строки Привет! Мне кажется все последние годы я что-то писал прям в то время, пока все нормальные люди отмечают Новый год. Это прям традиция какая-то. Собственно, большая часть базовой функциональности Codeforces была написана в новогодние праздники 2010-го года: авторизация, блоги, базовая поддержка соревнований. Возможно, я хочу провести и следующий год с интересом что-то улучшая в инфраструктуре Codeforces (да-да, как Новый год встретишь &mdash; так его и проведёшь). А может просто в Новый год вроде работать не обязательно и делаешь не то, что вот прям сейчас надо, а то, что хорошо бы когда-нибудь сделать. В этот раз я выделил чуток времени, чтобы добавить в <a href="https://github.com/MikeMirzayanov/testlib">testlib</a> поддержку разбора параметров командной строки. Мне очень не нравится в генераторах писать такое `int n = atoi(argv[3]);`. Собственно по нескольким причинам: * небезопасно к тому, что 3-го параметра командной строки может и не быть; * небезопасно к тому, что 3-...

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

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

9.
Автор Um_nik, история, 6 лет назад, По-русски
Я написал квалификацию Yandex.Cup... Она все еще идет, но я буду постить непубличную информацию, потому что мне плевать. Если [user:Yandex,2020-10-19] захотят запретить мне участвовать в этом замечательном соревновании &mdash; да будет так. 1 Монитор выглядит так: <spoiler summary="Spoiler"> ![ ](https://i.imgur.com/N5qFbom.png) </spoiler> Notable problems: - Для меня от начала соревнования прошло 50 минут, но мне почему-то видны попытки других участников, которые совершены после этого времени. Интересно, что этой проблемы не было на пробном туре. - Получается, скриншотом этого монитора я даже не спойлерю вам ничего, ведь вы увидите такой монитор как только запустите виртуальное участие. - В мониторе написано, что задачу E сдали 27 человек из 31 попытавшегося. Вот только на этом же мониторе видно, что её сдали 3 человека, у всех кто ниже должно быть не больше 2 баллов в сумме, в то время как сдача задачи E приносит 4 балла. Вам придется поверить мне на слово, что в этой задаче не предусмотрено частичных...

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

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

10.
Автор geranazavr555, 7 лет назад, По-русски
Обновления Polygon (июнь-октябрь 2019) Hello, Codeforces! Я и [user:cannor147,2019-11-07], будучи студентами Университета ИТМО, в июне присоединились к разработке Codeforces. С июня по октябрь мы преимущественно занимались развитием платформы Polygon. В этом посте нам бы хотелось представить вам список того, что мы сделали за это время. В этот список не включены мелкие баг-фиксы или какие-то незаметные пользователям улучшения. #### Пин-коды для контестов и задач Иногда в Polygon разрабатываются особо важные контесты и задачи. В таком случае председатель жюри может быть обеспокоен возможностью утечки, например из-за слабого пароля другого члена жюри. Пин-код &mdash; дополнительный фактор подтверждения доступа к задаче или контесту, его может установить или изменить только владелец задачи или контеста. Предполагается, что пин-код будет передан каким-то отдельным надежным каналом связи. Теперь в интерфейсе контеста для владельцев появилась ссылка Create Pin: ![Create Pin в интерфейсе](https://i.ibb.co/bgcg8Cq/p...

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

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

11.
Автор gKseni, 9 лет назад, По-русски
ICPC Финал 2018 <img src="/predownloaded/de/f3/def309578bab3ca770ea7262a4135f8f1ea50545.jpg" style="margin: 0 0 0 1em; float: right;"> 19-го апреля 2018 г. в <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=ACM+ICPC+2018+World+Finals&iso=20180419T10&p1=33&ah=5">05:00 (московское время)</a> начнется главное событие года в мире спортивного программирования &mdash; финал командного студенческого чемпионата мира ACM-ICPC 2018! Позади открытие и пробные туры. 140 команд со всего мира собрались в Пекине (Китай), чтобы определить &mdash; кто из них станет чемпионом мира, кто получит медали чемпионата. Масштаб проведения чемпионата этого сезона поражает воображение. Всего во всех отборочных этапах чемпионата приняли участие 49935 студентов из 3098 университетов 111 стран мира 6 континентов! В этом году стран стало на 8 больше! В зависимости от региона команды прошли квалификации, четвертьфиналы, локальные отборы, региональные соревнования. Лучшие 140 команд приехали в Пекин для уча...

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

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

12.
Автор Denisson, история, 9 лет назад, По-русски
Codeforces Round #444 (Div. 2) Editorial Еще раз приносим извинения участникам за допущенные нами ошибки при подготовке раунда. ###[problem:887A] Автор: [user:ayoyia,2017-11-04]. Если в строке нет единиц, то ответ "NO", так как оставшееся число должно быть положительным. Иначе найдем самую левую единицу и проверим, что после нее есть хотя бы 6 нулей. [Решение.](https://pastebin.com/mKYmrrnm) ###[problem:887B] Автор: [user:ayoyia,2017-11-04]. Ответ никогда не превосходит величины 98. Переберем числа от 1 до 99 и найдем первое такое, что его нельзя собрать из кубиков. [Решение.](https://pastebin.com/W5MBrL5e) ###[problem:887C] Автор: [user:ayoyia,2017-11-04]. Возможных вариантов входных данных, на которые ответ "YES", не более 12, не учитывая перестановки цветов. Их все можно было записать в массив. Альтернативным решением является написание функции поворота заданной грани кубика и последующей проверкой на то, что кубик собран. [Решение.](https://pastebin.com/G8kAaSVz) [user:Denisson,201...
искомой окружности относительно прямой $AB$. Каждая изначально нарисованная окружность блокирует

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

Разбор задач Codeforces Round 444 (Div. 2)
  • Проголосовать: нравится
  • +491
  • Проголосовать: не нравится

13.
Автор adamant, 10 лет назад, По-русски
Общие идеи Всем привет! Любители ли вы задачи, которые расчитаны на Ad Hoc решение? Я &mdash; терпеть не могу! Поэтому я решил сделать подборку идей, которые могут быть применены к достаточно большому классу задач. Добавляйте ещё, если о чём-то забыл. :) [cut]<br> **1. Слияние множеств за $O(n\log{n})$ амортизированно.** Если у нас есть некоторые множества, которые нам потом нужно будет соединять, поддерживая промежуточные результаты, то можно делать это в лоб, всегда добавляя меньшее множество к большему. Таким образом, каждый элемент будет перенесён в какое-то другое множество не более, чем $O(\log{n})$ раз, так как новое множество для него каждый раз будет увеличиваться хотя бы в два раза. На этом, в частности, основана одна из версий общеизвестного _DSU_. Из применений &mdash; можно сливать множества внутри обхода дерева в глубину и таким образом можно для каждой вершины в какой-то момент времени подержать в руках множество всех элементов её поддерева. **2. Подвохи в задачах. Час...

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

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

14.
Автор YF_YUSUF, 7 месяцев назад, По-русски
Типичный "прямой эфир" codeforces Как часто читаете блоги на codeforces? --- ## Codeforces Round Announcement/Editorial Самое обычное напоминание что здесь можно не только читать блоги, но и решать/дорешивать задачи. --- ## Atcoder Contest Announcement Попробуй порешать задачи на другом vjudge. --- ## Пожалуйста забаньте этих читеров Стражи порядка, смотрят чужие коды и проверяют не LLM ли написала этот код. --- ## Изменение правил об использовании... Автор MikeMirzayanov Вы видели сколько там коментариев? --- ## Я только начал начал изучать спортивное программирование Новички которые только изучают код, рассказываюти как они решали задачи и просят советы как двигатся дальше. --- ## Я решил эту задачу с раунда другим способов Либо гении которые нашли более простое решение, либо те кто не понял авторское решение и написали его по своему. --- ## Челендж апнуть много рейтинга Поставил себе цель до которой хочет дойти, и ...
Типичный "прямой эфир" codeforces

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

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

15.
Автор Um_nik, история, 5 лет назад, По-русски
Текст для интервью в ТАСС В связи с финалом ICPC в Москве журналисты пытаются писать что-то про спортивное программирование. Меня (а также [user:manoprenko,2021-10-01] и [user:Farhod_Farmon,2021-10-01]) попросили ответить на несколько вопросов для целевой аудитории школьников, которые могут быть заинтересованы в олимпиадах по информатике и спортивном программировании, а также их родителей. Результат можно почитать [здесь](https://tass.ru/obschestvo/12552701), а я хочу выложить свой оригинальный текст, который я отправил журналистам. Обратите внимание, что и текст ТАСС, и мои ответы не предназначены для спортивных программистов, но могут быть интересны/полезны для той аудитории, которая была заявлена целевой. [cut] (я не понял, как сделать так, чтобы после `[cut]` нормально отобразился заголовок, поэтому здесь есть этот текст). Алсо спасибо [user:lperovskaya,2021-10-01] за помощь в редактуре. ### Как вы начинали изучать программирование? В каком возрасте? Что именно делали (собирали конструкторы и писал...
И, как я уже сказал, спортивное программирование — это далеко не самый прямой путь ни в вуз, ни в

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

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

16.
Автор Alexdat2000, 4 года назад, По-русски
Разбор Codeforces Round #862 (Div. 2) Спасибо за участие! Надеемся, что вам понравились задачи! [problem:1805A]<br> Идея и разработка: [user:Alexdat2000,2023-04-02] <div class="spoiler"> <b class="spoiler-title">Подсказка 1</b> <div class="spoiler-content" style="display: none;"> Вспомните основные свойства операции $\oplus$: $A \oplus 0 = A$, $A \oplus A = 0$, $A \oplus B = B \oplus A$. </div></div> <div class="spoiler"> <b class="spoiler-title">Подсказка 2</b> <div class="spoiler-content" style="display: none;"> Рассмотрите случаи чётной и нечётной длины массива. </div></div> <div class="spoiler"> <b class="spoiler-title">Разбор</b> <div class="spoiler-content" style="display: none;"> [tutorial:1805A]</div></div> <spoiler summary="Решение"> ``` for _ in range(int(input())): n = int(input()) a = list(map(int, input().split())) xor = 0 for x in a: xor ^= x if xor == 0: print(0) else: if n % 2 == 1: print(xor) else: ...
="display: none;"> Заметим, что расстояние между прямой и параболой тоже будет параболой. Тогда какое

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

Разбор задач Codeforces Round 862 (Div. 2)
  • Проголосовать: нравится
  • +186
  • Проголосовать: не нравится

17.
Автор viktork, 12 лет назад, По-русски
ZeptoLab Code Rush 2014 <img src="http://assets.codeforces.com/images/zepto2014/image06.png" style="width:190px;float:right;margin:0 1em 1em 1em;"/> Божественно кодить можно не только для разных поисковых систем, но и в индустрии видеоигр &mdash; и не где-нибудь, а прямо на родине. Если не верите, то компания ZeptoLab, создатель известной во всем мире игры Cut the Rope, дает вам возможность убедиться в этом лично. И да, мы находимся в Москве. Не секрет, что высот программирования достигают только те, кто много работает, в том числе &mdash; над собой и своим образованием. В ZeptoLab мы стараемся создать пространство, которое максимально к этому располагает. В частности, недавно у нас появилась корпоративная библиотека, где можно найти все необходимое для получения новых знаний, а также импровизированный читальный зал с диванами и креслами. <center> <img src="http://assets.codeforces.com/images/zepto2014/image08.jpg" style="width:400px;"/> </center> Также мы устраиваем чемпионаты по разработке вн...

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

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

18.
Автор awoo, история, 5 лет назад, По-русски
Educational Codeforces Round 111 [рейтинговый для Div. 2] Привет, Codeforces! В [contest_time:1550] состоится [contest:1550]. Продолжается серия образовательных раундов в рамках инициативы [Harbour.Space University](https://harbour.space/)! Подробности о сотрудничестве [Harbour.Space University](https://harbour.space/) и Codeforces можно прочитать <a href="http://codeforces.me/blog/entry/51208">в посте</a>. Этот раунд будет **рейтинговым для участников с рейтингом менее 2100**. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Вам будет предложено **6 или 7 задач на 2 часа**. Мы надеемся, что вам они покажутся интересными. Задачи вместе со мной придумывали и готовили Адилбек [...

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

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

19.
Автор rembocoder, 4 года назад, По-русски
Простые оптимизации ДП Нет, я не имею в виду Convex Hull-оптимизацию и оптимизацию Кнута. Я имею в виду более простые и распространённые методы. _Это продолжение моей серии постов о ДП, чтобы понимать обозначения, читайте [пролог](https://codeforces.me/blog/entry/102542)._ ### Переходы из отрезка Очень часто после построения графа динамики можно обнаружить, что переходы в то или иное состояние ведут не из случайного набора вершин, а из некоторого отрезка по одному из параметров. _Например, из состояний `dp[i][j]`, при некотором константном `i` и при `j`, лежащим в отрезке `[a, b]`._ **В таком случае можно не реализовывать каждый переход в отдельности, а реализовать все скопом.** Если под реализацией перехода понимается прибавление из `dp[A]` в `dp[B]`, то можно воспользоваться префиксной суммой. Если же нам нужно найти _наилучший_ переход в `dp[B]`, то можно воспользоваться деревом отрезков. #### Пример [AtCoder DP Contest: Задача M](https://atcoder.jp/contests/dp/tasks/dp_m) _Найти количе...
То есть состояния, из которых ведёт переход, **расположены на некоторой прямой в таблице `i - 1

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

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

20.
Автор Monyura, история, 11 лет назад, По-русски
Разбор задач Looksery Cup 2015 **UPD.** Появился разбор задачи Е. Мы просим прощения за задержку, он получился действительно трудоемким, и, чтобы как-то загладить свою вину, мы публикуем несколько интерпретаций решения. **A. Определение лиц** Автор: [user:Monyura,2015-06-06] Для решения этой задачи следует перебрать все квадраты 2х2 и проверить, что переставив буквы можно получить слово "face". Это можно удобно сделать, например, отсортировав буквы квадрата в алфавитном порядке и проверив, что отсортированное множество равно "acef"(Отсортированный порядок букв слова "face"). **B. Вечеринка в Looksery** Автор: [user:Igor_Kudryashov,2015-06-06] При любом раскладе существует такое множество людей, что, если они придут и разошлют сообщения своим контактам, то каждый сотрудник получит количество сообщений отличное от того, что указал Игорь. Покажем как построить это множество. Рассмотрим 2 случая. Ни одно из чисел, предложенных Игорем, не равно нулю. Тогда если никто не придет на вечеринку, то всем ...
задаёт некие ограничения на радиус окружности и на расположение центра окружности относительнопрямой, стороны и центром в $a_1$. Таким образом, нам нужно проверить, существует ли прямая, проходящая, $ также являются координатами точек $b_0$ и $b_1$. Заметим, что в этом случае прямая, проходящая, , что количество точек в выпуклой оболочке, в которой никакие три точки не лежат на однойпрямой, равно, . Все точки, не лежащие на прямой $pq$, ограничивают параметр $t$ сверху или снизу, точки напрямой

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

Разбор задач Looksery Cup 2015
  • Проголосовать: нравится
  • +246
  • Проголосовать: не нравится

21.
Автор Fefer_Ivan, 12 лет назад, перевод, По-русски
Zepto Code Rush 2014 — решения ## [problem:436A] Автор разбора: [user:Fefer_Ivan,2014-06-14] В задача А типы съеденных конфет должны все время менятся. Так что первая съеденная конфета определяет тип всех последующих конфет. Возможных типа всего два, так что переберем тип первой съеденной конфеты. Пусть в какой-то момент времени Ом Ном должен съесть конфету типа $t$ и может прыгать на высоту $h$. Очевидно, что наиболее выгодным решением будет съесть конфету с наибольшей массой среди всех конфет, которые Ом Ном может съесть на текущем этапе. Для решения задачи необходимо промоделировать процесс поедания конфет для начального $h = x$ и $t = [0, 1]$ и выбрать лучшее значение. ## [problem:436B] Автор разбора: [user:Fefer_Ivan,2014-06-14] Пронумеруем столбцы таблицы начиная с 0 слева направа, а строки начиная с 0 сверху вниз. Теперь заметим, что в момент времени $t > 0$ в клетке $(x, y)$ могут находиться только $4$ паука: * Паук, который движется влево и в начале был в клетке $(x, y + t)$. * ...
$, тогда, то что требуется найти — для каждой прямой $c = i$, такую прямую $p = j$, что

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

Разбор задач Zepto Code Rush 2014
  • Проголосовать: нравится
  • +117
  • Проголосовать: не нравится

22.
Автор adamant, 13 лет назад, По-русски
C++ STL: Policy based data structures Всем привет! После достаточно долгого затишья, я решил, что <s>мой вклад растёт слишком медленно</s> пришёл час порадовать вас ещё одной статьёй в блоге _:)_ 2 месяца назад пользователь [user:Perlik,2014-03-19] выложил [статью](/blog/entry/10355), в которой описал очень интересную реализованную в STL структуру, которая позволяла очень быстро производить различные операции с подстроками. Некоторое время после этого я тестировал её на различных задачах и, к сожалению, как правило, получал негативный результат &mdash; rope оказалась слишком уж медленной, особенно когда речь шла о работе с отдельно взятыми элементами. На некоторое время я позабыл о той статье. Однако всё чаще я сталкивался с задачами, в которых нужно было реализовать множество, да не простое, а <s>золотое</s> с возможностью узнавать порядковый номер элемента и, напротив, элемент по его порядковому номеру (т.е., порядковую статистику в множестве). Вопрос выполнения этих операций методами стандартной библиотеки достат...
(mlogn) необходим прямой доступ к вершинам дерева. Без него решение работает за O(mlogn*logn).

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

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

23.
Автор Edvard, история, 10 лет назад, По-русски
Разбор задач Educational Codeforces Round 13 ### [problem:678A] Задачу предложил Әбдірахман Исмаил [user:Ismail_A,2016-06-14]. Нам нужно найти минимальное $x$, что $x*k>n$. Легко видеть, что $x=\lfloor\frac nk\rfloor+1$. Для подробного знакомства с математическими функциями пола и потолка я рекомендую книгу авторов Грэхем, Кнут, Паташник "Конкретная математика". В этой книге есть отдельная глава, посвящённая этим функциям и их свойствам. <spoiler summary="Решение на С++"> ~~~~~ li n, k; bool read() { return !!(cin >> n >> k); } void solve() { cout << (n / k + 1) * k << endl; } ~~~~~ </spoiler> Сложность: $O(1)$. ### [problem:678B] Задачу предложил Артур Яворски [user:KingArthur,2016-06-14]. Два календаря совпадают если и только, если в них одинаковое количество дней и они начинаются с одного дня недели. Таким образом, достаточно было просто перебрать следующий год, поддерживая первый день недели в году. На самом деле день недели каждый год увеличивается на единицу. Исключением...
прямой найти самое верхнее её пересечение с какой-либо прямой.

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

Разбор задач Educational Codeforces Round 13
  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

24.
Автор Wild_Hamster, история, 11 лет назад, По-русски
Codeforces #308 (Div. 2) Editorial [problem:552A] В этой задаче проходило множество решений: 1) С каждым новым прямоугольником добавляется его площадь к результату, так что будем считать площадь каждого прямоугольника и прибавлять к ответу, т.е. для каждой строки $x_1,y_1,x_2,y_2$ прибавляем к ответу $(x_2-x_1+1)*(y_2-y_1+1)$ Асимптотика данного решения по времени $O(n)$. 2) Просто сделаем все, что описано в условии, создадим массив и с каждым запросом будем прибавлять прямоугольник к массиву, после чего просто сложим все элементы массива. Асимптотика по времени $O(n*x*y)$ [C++ code](http://ideone.com/uFAzzC) [user:Wild_Hamster,2015-06-19] [Java code](http://ideone.com/9FPeh9) [user:Wild_Hamster,2015-06-19] [Python code](http://ideone.com/kIXn7c) [user:Zlobober,2015-06-19] [problem:552B] Можно вывести формулу результата: для $n < 10$ ответом будет $n = n - 1 + 1 = 1*(n+1)-1$; для $n < 100$ ответом будет $2*(n-9) + 9 = 2*n - 9 = 2*n - 10 - 1 + 2 = 2*(n+1)-11$; для $n < 1000$ отве...
, после этого отсортировать его и искать количество точек на каждой прямой нахождением количества подряд, Переберем все возможные пары точек, проведем через каждую из пар прямую и запишем, что этойпрямой, прямой принадлежат эти 2 точки с помощью map. Если на прямой находится $x$ точек, то на самом деле мы

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

Разбор задач Codeforces Round 308 (Div. 2)
  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

25.
Автор danilka.pro, 12 лет назад, перевод, По-русски
Разбор Codeforces Round #284 ## [problem:499A] Задача решается жадным алгоритмом &mdash; если мы на текущем моменте времени можем пропустить $x$ минут, не пропустив при этом ни одного хорошего момента, то мы пропускаем $x$ минут, в противном случае &mdash; смотрим очередную минуту фильма. ## [problem:499B] В задаче требовалось для каждой строки из текста искать, в какой паре она находится, и из двух строк этой пары выводить меньшую по длине. ## [problem:498A] / [problem:499C] Несложно показать, что, если две исходные точки изначально находятся по разные стороны какой-то из прямых, эту прямую в любом случае придется пересечь. Поскольку все, что нам нужно &mdash; это пересечь все такие прямые, ответ на задачу &mdash; их количество. Чтобы проверить, лежат ли точки по разные стороны прямой, достаточно подставить их координаты в ее уравнение, и проверить, что получившиеся два значения имеют разные знаки. Итоговая сложность решения &mdash; $O(n)$. ## [problem:498B] / [problem:499D] Для удобств...
Чтобы проверить, лежат ли точки по разные стороны прямой, достаточно подставить их координаты в ее

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

Разбор задач Codeforces Round 284 (Div. 1)
  • Проголосовать: нравится
  • +63
  • Проголосовать: не нравится

26.
Автор purplesyringa, история, 5 лет назад, По-русски
Платформы по программированию в анекдотах ## AtCoder ### Условие Даны числа A и B. Выведите A + B. ### Разбор В задаче требуется вывести сумму двух чисел. Обратите внимание: в языках C и C++ необходимо использовать достаточно большие типы данных. Решение: ```python print(int(input()) + int(input())) ``` <!-- x --> [cut] <!-- x --> --- ## Algocode ### Условие Яна стоит на числовой прямой в координате 0. Так как у Яны день рождения, ей дарят яблоки мальчики Петя и Вася. Яна любит только зеленые яблоки, но не любит красные. У Пети есть N зеленых яблок, а у Васи M красных. Одно красное яблоко сдвигает ее из координаты i в координату i-1, одно зеленое яблоко сдвигает ее из координаты i в координату i+1. Напишите, при каких N и M координата на числовой прямой будет положительной; отрицательной; равна нулю. **Все утверждения строго доказывать!** ### Разбор --- ## Codeforces ### Условие Петя и Вася решили подарить Кате на день рождения яблоки, Петя подарил N яблок, а Вася &mdash; M. ...
Яна стоит на числовой прямой в координате 0. Так как у Яны день рождения, ей дарят яблоки мальчики

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

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

27.
Автор teraqqq, история, 7 лет назад, По-русски
Реализация встречного дерева Фенвика для RMQ или ДО для курильщиков Доброго времени суток! Началось все с того, что после прочтения [статьи](https://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D1%81%D1%82%D1%80%D0%B5%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B5%D0%BD%D0%B2%D0%B8%D0%BA%D0%B0) про встречное дерево Фенвика, я начал искать в интернете его реализацию, но (спойлер) так и не нашел. Безусловно, тема не нова, но, к сожалению, статью, описывающую эту структуру данных с приведенными примерами реализации, я так и не нашел. Перед прочтением данного поста советую ознакомиться с указанной статьей, т.к. на нее будут опираться все дальнейшие рассуждения. Встречное дерево Фенвика ================== Для начала, вспомним определение: Встречное дерево Фенвика (англ. counter tree Fenwick) — дерево Фенвика, в котором над каждым столбцом идет столбец такой же высоты, вычисляемый по формуле $f_{rev}[i]=\sum\limits_{j=i+1}^{i+2^{h(i)}}a[j]$. Сразу сделаю уточнение, что под прямым деревом Фенвика подразумевается массив, посчита...

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

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

28.
Автор dalex, 13 лет назад, По-русски
Разбор задач Codeforces Round #222 На всякий случай, [ссылка на анонс и обсуждение](/blog/entry/10138). А теперь разбор. #### A div 2: [problem:378A] Заведем три счетчика: для побед каждого из игроков и для ничьи. Переберем все варианты, как можно выбросить кубик &mdash; их всего 6 штук. Для каждого варианта определим, кто выиграет, или будет ли ничья, и прибавим единицу к соответствующему счетчику. #### B div 2: [problem:378B] Можно немного подумать и понять, что достаточно рассмотреть крайние случаи $k = 0$ и $k = \frac{n}{2}$. Все остальные случаи будут средними между этими двумя. В случае $k = 0$ мы должны выбрать $n$ максимальных элементов из двух посорченных списков, это можно сделать, например, двумя указателями. А в случае $k = \frac{n}{2}$ отметим первых $\frac{n}{2}$ спортсменов в каждом списке. #### A div 1 / C div 2: [problem:377A] Запустим поиск в ширину или в глубину из любой свободной клетки. Так как лабиринт связный, этот поиск обойдет все $s$ свободных клеток. Однако мы прервем э...
лежат в стеке после той, с которой было пересечение текущей добавляемой прямой ). Обработав все, К примеру, в начале это просто прямая $y = v_{1} x$, где $v_{1}$ — скорость строения, которое, Это уже совершенно стандартная задача, решающаяся с помощью сканирующей прямой по одной оси и

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

Разбор задач Codeforces Round 222 (Div. 1)
Разбор задач Codeforces Round 222 (Div. 2)
  • Проголосовать: нравится
  • +60
  • Проголосовать: не нравится

29.
Автор komendart, история, 11 лет назад, перевод, По-русски
Codeforces Round #340 (Div. 2) Editorial [problem:617A] Оптимально делать наибольший возможный шаг каждый раз. Поэтому слоник должен сделать сначала некоторое количество шагов на расстояние 5, а затем один или ноль шагов на меньшее расстояние. Следовательно, ответ равен $\lceil\frac{x}{5}\rceil$. Решение [submission:15550796] [problem:617B] Нам дан массив, состоящий только из нулей и единиц. Мы должны разделить его на части, в каждой из которых ровно одна единица. Особый случай: когда массив состоит только из нулей ответ равен нулю. Рассмотрим общий случай. Во-первых нули на префиксе относятся к первому куску, нули на суффиксе относятся ко второму куску. Во-вторых, между каждой парой соседних единиц должно быть одно и только одно разделение частей. Между соседними единицами с индексами $a < b$ всего $b - a$ вариантов разделения. Поэтому мы должны перемножить эти значения для всех пар соседних единиц. Бонус: каким является максимальный ответ при $n \leq 100$? Решение [submission:15550806] [problem:61...

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

Разбор задач Codeforces Round 340 (Div. 2)
  • Проголосовать: нравится
  • +60
  • Проголосовать: не нравится

30.
Автор tunyash, 14 лет назад, По-русски
Разбор Codeforces Round #122 Пожалуйста, задавайте возникающие у вас вопросы по задачам. Особенно это касается задачи D, так как она оказалась наиболее сложной. **Задача <<Экзамены>>** По условию $2n \le k \le 5n$. Если $k < 3n$ то некоторые экзамены мы сможем сдать только на $2$. Таких будет $3n-k$. Если же $3n \le k$, то мы все экзамены сдадим как минимум на три. **Задача <<Квадрат>>** Пусть карандаш идет по прямой и ставит крестики через каждые $(n+1)$ точку. Поставим в соответствие положению на прямой положение на квадрате. А именно, точке $x$ на прямой будет соответствовать точка, в которую придет карандаш, сдвинувшись по периметру квадрата на $x$. Тогда левому нижнему углу квадрата соответствуют все точки вида $4np$ для некоторого целого неотрицательного $p$. Поставленным крестиками будут соответствовать точки $k(n+1)$. Самая ближайшая точка совпадения двух семейств, за исключением начальной, будет в LCM($n+1$, $4n$) (LCM --- НОК). Тогда всего мы поставим $\frac{LCM(n+1,4n)}{n+1} + 1$ крестиков. *...
**Задача <<Квадрат>>** Пусть карандаш идет по прямой и ставит крестики через каждые $(n+1)$ точку

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

Разбор задач Codeforces Round 122 (Div. 1)
Разбор задач Codeforces Round 122 (Div. 2)
  • Проголосовать: нравится
  • +116
  • Проголосовать: не нравится

31.
Автор teraqqq, история, 7 месяцев назад, По-русски
Трассировка вектора В этом году проходил BSUIR Open XIV, мне было очень приятно съездить в Минск и на само соревнование. Но еще больше мне понравилась задачу, которую я туда предложил. В целом я не видел эту идею раньше, но она кажется достаточно простой, чтобы появиться раньше на каких-нибудь соревнованиях. Так что если вы знаете, где раньше встречалась это идея, то поделитесь, пожалуйста. **Задача.** (*BSUIR OPEN XIV*) Дано клеточное поле $100 \times 100$, в котором между некоторыми клетками проведены стены, также стены проведены по границе поля. Луч запускается из центра клетки $(r,c)$ в направлении $(x,y)$. Требуется определить, в какой клетке он окажется, пройдя расстояние $\sqrt{x^2+y^2}$, если луч отражается от стен. Решение задачки ------------------ Взглянем на вектор $(x,y)$ и посмотрим, в каком порядке он пересекает вертикальные и горизонтальные линии сетки. В точке $(0,0)$ пересечение с линиями сетки учитывать не будем, но будем учитывать пересечения в точке $(x,y)$, причем по формал...
пересечение с вертикальной прямой.

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

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

32.
Автор KADR, 15 лет назад, По-русски
Codeforces Beta Round #97: разбор <p>Представляю разбор задач Codeforces Beta Round #97. Если есть какие-то вопросы или пожелания --- пишите в комментариях.</p><h3>[[problem:136A]] (A Div 2)</h3><div><br /></div><div>В этой задаче нужно было просто считать перестановку и вывести обратную к ней. Для этого просто при считывании <i>i</i>-го по счету числа, которое равно <i>a</i> поместим <i>i</i> в ячейку массива с номером <i>a</i>. После этого выведем полученный массив.</div><div><br /></div><div>Сложность решения $O(N)$.</div><div>[cut]</div><div><h3>[[problem:136B]] (B Div 2)</h3></div><div><br /></div><div>Легко понять, что ответ всегда определяется однозначно. Для того чтобы его найти, можно ввести аналог операции вычитания без переноса разрядов. От каждого разряда числа <i>c</i>, записанного в троичной системе счисления отнимем соответствующий разряд числа <i>a </i>и результат вычитания в каждом разряде возьмем по модулю 3. Полученное число и будет искомым <i>b</i>, таким что <i>a tor b = c</i>.</div><div><br /></di...
, соединяющих последовательные точки, образуют прямой угол. Это можно сделать используя тот факт, что

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

Разбор задач Codeforces Beta Round 97 (Div. 1)
Разбор задач Codeforces Beta Round 97 (Div. 2)
  • Проголосовать: нравится
  • +87
  • Проголосовать: не нравится

33.
Автор Alex_KPR, 16 лет назад, По-русски
Разбор задач Codeforces Beta Round #69 <table border="0" cellpadding="5" cellspacing="0" width="100%"> <tbody><tr> <td bgcolor="#cccccc" width="2%" nowrap="nowrap"><div align="center"></div></td> <td bgcolor="#cccccc"><div align="center"> <p><strong>Предсказание Панорамикса (задача A, 2-ой дивизион). Автор задачи - </strong><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span class="Apple-style-span" style="border-collapse: collapse; font-family: verdana,arial,sans-serif; font-size: 13px; line-height: 20px;"><a class="rated-user user-orange" href="../../../profile/Alex_KPR" title="Майор Alex_KPR" style="font-family: arial; text-decoration: none; font-weight: bold; color: rgb(0, 0, 204);">Alex_KPR</a></span></s...
окружности в прямые либо окружности. Причем образом может быть прямая тогда и только тогда, когда исходная

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

Разбор задач Codeforces Beta Round 69 (Div. 1 Only)
Разбор задач Codeforces Beta Round 69 (Div. 2 Only)
  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

34.
Автор Endagorion, 15 лет назад, По-русски
Codeforces Beta Round #99: разбор <h3>[[problem:139A]]</h3>Вычтем из количества страниц книги количество страниц, которые Петя успеет прочесть в понедельник. Если результат неположительный, то в понедельник Петя закончит читать. Иначе перейдем ко вторнику и т.д. по циклу, после воскресенье опять рассматриваем понедельник. Заканчиваем, как только количество страниц должно стать неположительным.<br />Всего нужно пройтись по циклу не более N раз, поскольку на каждой неделе отнимается как минимум одна страница. Сложность - O(n)<br /><br /><h3>[[problem:139B]]</h3><p>Что подразумевалось в условии:</p><p>Каждый рулон можно резать только на полоски, длина которых совпадает с высотой комнаты (потому что нельзя делать горизонтальные стыки, и расположение должно быть строго вертикальным). В каждой комнате можно клеить только один тип обоев (в разных комнатах клеить одинаковые типы можно). Для каждой комнаты надо всего лишь определить оптимальный по цене тип обоев.</p><p>Ясно, что количество рулонов данного типа, нужных для обкле...
1) Сканирующая прямая. Будем идти слева направо и рассматривать события "отрезок начался

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

Разбор задач Codeforces Beta Round 99 (Div. 1)
Разбор задач Codeforces Beta Round 99 (Div. 2)
  • Проголосовать: нравится
  • +68
  • Проголосовать: не нравится

35.
Автор Zlobober, история, 11 лет назад, По-русски
Разбор VK Cup 2015 — Finals Всем спасибо за участие! Задачи следуют в порядке, в котором они шли на оригинальном соревновании. [problem:562A] -------------- (в трансляции: [problem:566C]) Формализуем задачу. Нам дано необычное определение расстояния по дереву: $\rho(a, b) = dist(a, b)^{1.5}$. У каждой вершины есть её вес $w_i$. Нужно как-то так выбрать место $x$ для проведения соревнования, чтобы минимизировать сумму взвешенных расстояний от всех вершин до неё: $f(x) = w_1 \rho(1, x) + w_2 \rho(x, 2) + \ldots + w_n \rho(x, n)$. Давайте изучим свойства функции $f(x)$. Мысленно разрешим себе ставить точку $x$ не только в вершины дерева, но и в любую точку на ребре, доопределив естественным образом расстояние от точки внутри ребра до всех остальных вершин (например, середина ребра длины $4$ находится на обычном расстоянии $2$ от концов ребра). **Утверждение 1**. На любом пути $x \in [a, b]$ в дереве функция $\rho(i, x)$ является выпуклой вниз. Действительно, функция $dist(i, x)$ на любом пути выгляд...
решить следующим образом. Отметим всех работников в ряд на прямой от $1$ до $n$. Заметим, что отделы, Добавляя запросы первого типа мы на самом деле разрешаем некоторым отрезкам на прямой относиться к

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

Разбор задач VK Cup 2015 - Finals
  • Проголосовать: нравится
  • +100
  • Проголосовать: не нравится

36.
Автор marat.snowbear, 12 лет назад, перевод, По-русски
Разбор Codeforces Round #269 [problem:471A] ------------------ Нам даны длины шести палочек и надо проверить, какое животное мы может из них собрать. Единственное условие, общее для обоих животных, &mdash; четыре палочки-лапы должны быть одной длины. Так как это условие общее, то в случае отсутствия хотя бы четырех палочек одинаковой длины ответ будет однозначно "Alien". Если же такие четыре палочки есть, то кого-нибудь мы точно соберем, надо только решить кого. В этом случае ответ будет зависеть от того, равны ли оставшиеся две палочки. Весь алгоритм получается такой: 1. Найти число, встречающееся не менее четырех раз. 2. Если такого числа нет, то ответ &mdash; "Alien" 3. Иначе надо удалить четыре вхождения этого числа из входного массива. 4. Если два оставшихся числа равны, то ответ &mdash; "Elephant", а иначе &mdash; "Bear". Вместо того, чтобы искать число встречающееся четыре или более раз, можно было просто отсортироваться входной массив, взять третье или четвертое число и проверить,...
быстро. В процессе работы заметающей прямой мы будем обрабатывать три типа событий (перечислены в, горизонтальных линий по ходу работы заметающей прямой. Итак мы добавляем вертикальную линии, которая, заметающей прямой. Таким образом мы будем рассматривать все пересечения слева направо, например.

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

Разбор задач Codeforces Round 269 (Div. 2)
  • Проголосовать: нравится
  • +186
  • Проголосовать: не нравится

37.
Автор peltorator, 5 лет назад, По-русски
Отбор в кружок олимпиадного программирования «Тинькофф» 2021-2022 Всем привет! Начинается новый учебный год, вместе с ним стартует и сезон олимпиад. Этот пост будет полезен школьникам, которые хотят заниматься олимпиадным программированием, но не знают где. Сейчас открыт отбор в кружок по олимпиадному программированию «Тинькофф Поколение». Один из классных плюсов кружка — он абсолютно бесплатный, но нужно написать вступительный контест, который открыт **до 12 сентября включительно**. Зарегистрироваться и начать решать можно здесь: [algocode.ru](https://algocode.ru). Ниже мы постараемся подробнее описать как все устроено в кружке. Если у вас останутся вопросы, задать их можно в комментариях к посту или в telegram (внизу есть наши контакты). Каждый год мы стараемся быть лучше и действительно полезными, так что в этом году кружок будет еще интереснее. ## Про формат занятий По результатам отборочного контеста мы разделим участников на учебные параллели. У каждой параллели есть своя группа преподавателей, которые будут читать лекции, п...

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

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

38.
Автор awoo, история, 4 года назад, По-русски
Educational Codeforces Round 147 [рейтинговый для Div. 2] Привет, Codeforces! В [contest_time:1821] состоится [contest:1821]. Продолжается серия образовательных раундов в рамках инициативы [Harbour.Space University](https://harbour.space/)! Подробности о сотрудничестве [Harbour.Space University](https://harbour.space/) и Codeforces можно прочитать <a href="http://mirror.codeforces.com/blog/entry/51208">в посте</a>. Этот раунд будет **рейтинговым для участников с рейтингом менее 2100**. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Вам будет предложено **6 или 7 задач на 2 часа**. Мы надеемся, что вам они покажутся интересными. Задачи вместе со мной придумывали и готовили Ад...

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

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

39.
Автор gen, 14 лет назад, По-русски
Разбор Codeforces Round #165 ### [problem:270A,Div II A — Завидный забор] #### Задача Нужно определить, существует ли правильный многоугольник, углы которого равны $a$. #### Решение Рассмотрим все смежные углы правильного $n$-многоугольника с углом $a$, они равны $180^\circ-a$. Их сумма равна $360^\circ$, так как многоугольник выпуклый. Тогда выполняется следующее равенство: $n\cdot(180-a) = 360$, которое означает, что ответ есть, когда $360\mod(180-a) \equiv 0$. ![ ](http://oi47.tinypic.com/qx1538.jpg) Время: $O(t)$. Память: $O(1)$. Реализация: [C++](http://ideone.com/xnq9Iu), [Java](http://ideone.com/D2hHEL) #### Комментарий Задача также решается поворачиванием вектора $(1,0)$ на угол величины $180^\circ-a$, пока он не вернётся на свою позицию (поворот делаем не более 360 раз), и проверяя, совершили ли мы ровно один полный оборот (пример реализации: [C++](http://ideone.com/e3kIXZ)). Это также одна из редких задач на Codeforces, у которой всего 1 пример, 1 претест и 1 полный тест. ### ...
#### Задача На прямой даны $n$ точек, каждая одного типа от $1$ до $m$. Мы можем раздеить прямую, #### Решение Для решения задачи используем метод сканирующей прямой. Эта горизонтальная

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

Разбор задач Codeforces Round 165 (Div. 1)
Разбор задач Codeforces Round 165 (Div. 2)
  • Проголосовать: нравится
  • +88
  • Проголосовать: не нравится

40.
Автор dmkozyrev, история, 3 года назад, По-русски
Реализовал триангуляцию многоугольника на C++ за O(n log(n)) Привет, codeforces! Сегодня, ориентируясь на статью **_Триангуляция полигонов_** с сайта neerc.ifmo.ru, я реализовал триангуляцию любых многоугольников без самопересечений (в том числе не являющихся выпуклыми) на C++. $\text{ }$ [cut] $\text{ }$ Зачем мне это понадобилось? На отбор на RuCode 7.0 в этом году дали задачу H. Территориальное размежевание. Задача ставится следующим образом: вам дана бесконечная плоскость, покрашенная зеброй (чёрная полоска высоты $1$, белая полоска высоты $1$, чёрная ..., белая ...). На плоскости дан многоугольник без самопересечений, состоящий из $n\text{ }\left(3\le n \le 100000\right)$ вершин с целочисленными координатами $x_i, y_i \left(-10^9 \le x_i, y_i \le 10^9\right)$. Вершины указаны в порядке какого-то обхода. Требуется посчитать чёрную площадь внутри многоугольника. Сначала я решил для случая, когда фигура &mdash; треугольник, а потом подумал, почему бы не триангулировать исходный многоугольник и не вызвать решение для тре...
внимательны с тем, что я вырезаю вершины, которые лежат на одной прямой с соседними вершинами, ибо они

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

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

41.
Автор Zlobober, 9 лет назад, По-русски
IOI 2017, первый тур <center><a style="font-size:20pt;" href="http://scoreboard.ioi2017.org/Ranking.html">Таблица результатов</a></center> <spoiler summary="Краткий обзор задач"> [Nowruz](http://jonathanirvin.gs/files/ioi2017/day1/nowruz-ISC.pdf) &mdash; это первая со времён канадского maze в 2010 году задача на IOI с открытыми тестами. Забавный факт состоит в том, что nowruz, как и maze, это задача про клетчатый лабиринт. Дано клетчатое поле, в котором некоторые клетки свободны, и нужно оставить от них связное подмножество клеток, образующее дерево (в том смысле, что от любой клетки до любой есть единственный путь). Требуется максимизировать количество листов в получившемся дереве. Оценка линейно зависит от количества листов, при этом в тесте дано, сколько умеет жюри, и результат жюри считается за полный балл на тесте. Говорят, оптимизационная задача, в которой есть много разных подходов, по ощущениям приятнее того же канадского maze. [Wiring](http://jonathanirvin.gs/files/ioi2017/day1/wiring-ISC.p...
несколько различных точек на прямой, часть из которых красная, а часть синяя. Можно соединять красные с

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

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

42.
Автор Zlobober, 12 лет назад, По-русски
Разбор VK Cup Round 1 Набор задач в онлайн-трансляции незначительно отличается от набора задач на основном раунде, задачи следуют в порядке, в котором они фигурируют в основном раунде. [problem:524A] ============== В задаче требовалось реализовать ровно то, что описано в условии. Фиксируем человека $x$, проходимся по всем остальным людям $y$, не дружащим с $x$, и считаем количество общих друзей $x$ и $y$. Тонкий момент №1: несмотря на то, пар друзей во вводе не более 100, самих людей может быть до 200, и можно ошибиться в выставлении размеров массивов. Тонкий момент №2: нужно аккуратно сравнивать вещественные числа. Если написать нечто вроде `common / degree >= k / 100.0`, то в силу специфики вычислений с вещественными числами, результат такой проверки может быть недетерминирован (если в какую-то из частей внесётся незначительная погрешность). Поэтому, надо либо сравнивать с точностью до некоторого `eps`, либо выполнять проверку в целых числах: `common * 100 >= degree * k`. [problem:524B] =...
прямой. Пусть мы идём слева направо и прошли через правую границу прямоугольника, расположенного в

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

Разбор задач VK Cup 2015 - Раунд 1
  • Проголосовать: нравится
  • +90
  • Проголосовать: не нравится

43.
Автор I_love_natalia, история, 11 лет назад, По-русски
Спортивное программирование и тоталитарные секты По материалам [одной статьи](http://www.aif.ru/dontknows/kak_raspoznat_sektu_10_priznakov_kotorye_dolzhny_nastorozhit) (текст полностью скопирован). Шутка, конечно, но повод задуматься. 1. Маркетинг. Сектанты стараются привлечь как можно больше адептов, поэтому участники секты обычно активно занимаются пропагандой своего учения. Должны насторожить назойливые звонки, письма и сообщения с предложениями бесплатно посетить <s>кружок по программированию в вузе</s> семинар по духовному росту или пробуждению. Благотворительные концерты, фестивали для детей, психологические тренинги тоже зачастую скрывают псевдорелигиозные течения.<br/> КСТАТИ Существует специальный психологический приём «бутерброд»: человека окружают особым вниманием и заботой, двое <s>тиммейтов</s> сектантов постоянно держат всестороннюю связь с вербуемым, чтобы не допустить его критических мыслей в отношении учения. 2. Иерархия и двойное учение. Обычно инициаторы секты маскируют своё учение под <s>программирование</...

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

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

44.
Автор netman, 12 лет назад, По-русски
Codeforces Round #260 — Разбор [problem:456A] Решение: [submission:7407613]; В этой задаче надо было проверить существования таких $i$ и $j$, что $i \neq j$, $a[i] < a[j]$, $b[i] > b[j]$. Если существуют такие $i$ и $j$, то Леша рад. Для этой задачи есть очень простое решение. Просто проверить, что для всех $i$ верно, что $a[i] = b[i]$. Если это так, то Леша не рад. Доказательство очень простое. Давайте отсортируем массивы $a$ и $b$, как пары чисел, по возрастанию. Можно увидеть что Лёша рад, если есть хотя бы одна инверсия в массиве $b$, то есть существуют такие $i$ и $j$, что $b[i] > b[j]$ и $i < j$ ($i < j \Leftrightarrow a[i] < a[j]$, так как числа в массиве $a$ идут в возрастающем порядке). То есть это значит, что массив $b$ не отсортирован, и это значит, что $a \neq b$. [problem:456B] Решения: [submission:7407625], [submission:7407631]; В этой задаче надо было вычислить то, что просили в условии. Правда в лоб это не легко сделать. Но если посмотреть на формулу, то можно сделать след...
}, B_{i})$ — $i$-ая прямая. $K_{i} = a[i]$, $B_{i} = a[i] \cdot i - sum[i]$., Можно заметить, что в скобках вышло что-то похожее на уравнение прямой — $K \cdot X + B$. В, Прямых у нас будет $n$. То есть для каждого элемента массива $a$ своя прямая. Теперь ответ на

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

Разбор задач Codeforces Round 260 (Div. 1)
Разбор задач Codeforces Round 260 (Div. 2)
  • Проголосовать: нравится
  • +45
  • Проголосовать: не нравится

45.
Автор HolkinPV, 14 лет назад, По-русски
Codeforces Round #158 (Div. 2) Разбор Задач [problem:260A] Сначала попробуем приписать справа любую цифру от $0$ до $9$, которая подойдет под условие задачи. Если это не получится, сразу выведем -1. В противном случае остальные $n – 1$ можно сделать $0$, так как делимость от этого не пропадет. [problem:260B] В этой задаче нужно было перебрать все даты от $2013$ до $2015$ года (високосных годов среди них нет), посчитать количество вхождений каждой даты в исходную строку и найти максимум. В году $365$ дней, следовательно это решение за $(3 \cdot 365 \cdot N)$. [problem:260C] Сначала опишем простой способ получения решения. Будем по одному шарику доставать из коробок, начиная с коробки $x$ справа налево (действие назад). В какой-то момент в текущей коробке окажется $0$ шариков. Это коробка является начальной для нашей исходной задачи, то есть та, откуда мы взяли все шарики и начали раскладывать. Тогда в эту коробку положим число шариков, равное количеству шариков, которое мы только что достали из всех коробок. То...
количество городов левее левой вертикальной прямой, правее правой вертикальной прямой, ниже нижней, , то есть некоторую решетку, легко посчитать количество городов левее левой вертикальнойпрямой, Для каждой из четырех зон (левее левой вертикальной прямой, правее правой вертикальнойпрямой, ниже

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

Разбор задач Codeforces Round 158 (Div. 2)
  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

46.
Автор ifsmirnov, история, 11 лет назад, По-русски
Разбор Codeforces Round #349 [problem:667A] Чтобы узнать, сколько воды вы потребляете за секунду, вы должны разделить выпитый в секунду объём $v$ на площадь дна, равную $\dfrac {\pi d^2} 4$. Далее следует сравнить эту величину с $e$. Если ваша скорость выше, то вы опустошите кружку через $\dfrac{h}{\tfrac{4v}{\pi d^2}-e}$ секунд. Иначе вы не сможете её опустошить. [problem:667B] Для того, чтобы из набора длин можно было сложить выпуклый многоугольник, должно выполняться обобщённое неравенство треугольника: длина наибольшей стороны должна быть меньше суммы длин оставшихся сторон. Раз из текущего набора длин сложить выпуклый многоугольник невозможно, есть сторона, длина которой не меньше суммы остальных. Пусть она больше этой суммы на $k$; тогда достаточно добавить стержень длины $k+1$. Кроме того, ясно, что никакой меньшей длиной обойтись нельзя. Таким образом, ответ на задачу &mdash; $\texttt{max}(l_1, \dots, l_n) - (l_1 + \dots + l_n - \texttt{max}(l_1, \dots, l_n)) + 1$. [problem:666A] / [problem...
)$. После этого четыре точки должны оказаться на одной прямой. Теперь задачу можно переформулировать так

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

Разбор задач Codeforces Round 349 (Div. 1)
Разбор задач Codeforces Round 349 (Div. 2)
  • Проголосовать: нравится
  • +68
  • Проголосовать: не нравится

47.
Автор adamant, 12 лет назад, По-русски
C++ STL: Policy based data structures. Часть 2 Всем привет! Некоторые из вас могут помнить мою [статью](/blog/entry/11080) про policy based data structures. Кроме обзорной статьи на эти структуры, я также хотел написать про возможность использования самописного `Node_Update` в структуре. Тогда мне так и не удалось выделить на это достаточно времени, однако теперь я могу и хочу наверстать упущенное и поделиться с вами новыми знаниями. <br> [cut] <br> Итак, начнём. Шаблон класса обновления вершин должен иметь следующий вид: ~~~~~ template<class Node_CItr, class Node_Itr, class Cmp_Fn, class _Alloc> struct my_node_update { typedef my_type metadata_type; void operator()(Node_Itr it, Node_CItr end_it) { ... } }; ~~~~~ Рассмотрим то, как работает этот класс подробнее. pb-дерево, использующее политику обновления вершин будет дополнительно хранить в вершине одну переменную типа my_type. Когда дерево перестраивается, часть метаданных портятся, поэтому к каждой вершине, у которо...
Это даст нам возможность получать прямой доступ к дереву. В частности, node_begin() будет указывать

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

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

48.
Автор zeliboba, 9 лет назад, По-русски
Почему на NEERC не дают использовать Team Notebook на контесте? Очень давно задаюсь этим вопросом и ни разу не получал ни от кого вразумительного ответа. При этом очевидно, что у этого решения, которое скорее всего является примером принципа "это плохо, но исторически сложилось, давайте не будем ничего менять", много минусов: 1) На финал могут не отобраться команды, которые выступили бы там лучше. 2) Для команд, которые имеют шансы пройти на финал, сильно усложняется подготовка к нему, потому что им нужно писать тренировки до декабря в режиме без Team Notebook. По сути эти команды существенно ухудшают свое качество подготовки к финалу в течение этих четырех месяцев. Особенно болезненны такие переключения для команд, которые ездили на финал в прошлом году, для меня в свое время это было довольно некомфортно. 3) Это приводит к тому, что некоторые сильные команды готовят свой Team Notebook некачественно или вообще его не готовят. Понятно, что это может сильно ухудшить их результаты на финале. 4) Чем дольше развивается acm icpc, тем больше ...

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

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

49.
Автор specia1, история, 6 месяцев назад, По-русски
Пошаговый разбор для новичков. Spectral::Cup 2026 Round 2 Всем Привет! ![ ](/predownloaded/92/d1/92d185b9a970affe38f3d3b1f1660b5a3a7e8055.png) Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать свой первый пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи. Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую пр...
A. Слаймы на прямой ===================

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

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

50.
Автор MrLolthe1st, 2 года назад, По-русски
Разбор Codeforces Round 990 (Div. 2 + Div. 1) ### Div2A Алёна счастлива, когда нет незавершенных слоев &mdash; то есть перед ней идеальный квадрат с нечетной длиной стороны. Поскольку порядок кусочков фиксирован, достаточно отслеживать общий текущий размер $s$ головоломки и после каждого дня проверять, является ли $s$ идеальным квадратом нечетного числа. Самый простой способ сделать это &mdash; создать дополнительный массив, содержащий $1^2, 3^2, 5^2, ..., 99^2$, и проверять после каждого дня, находится ли $s$ в этом массиве. <spoiler summary="Код"> ~~~~~ NT = int(input()) sqs = set() k = 1 while k * k <= 100 * 1000: sqs.add(k * k) k += 2 for T in range(NT): n = int(input()) a = list(map(int, input().split())) answer = 0 cursum = 0 for t in a: cursum += t if cursum in sqs: answer += 1 print(answer) ~~~~~ </spoiler> ### Div2B Найдите символ, который появляется наименьшее количество раз &mdash; если есть ничья, возьмите более ранний символ в алфавите. Найдите символ, которы...
Во время перебора вертикальной прямой мы будем поддерживать два дерева отрезков на сумму: одно для

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

Разбор задач Codeforces Round 990 (Div. 1)
Разбор задач Codeforces Round 990 (Div. 2)
  • Проголосовать: нравится
  • +114
  • Проголосовать: не нравится

51.
Автор GlebsHP, история, 9 лет назад, По-русски
Разбор задач разминочного раунда Яндекс.Алгоритма 2018 A. Время в зазеркалье --------------------- Рассмотрим движение "прямой" и "отражённой" стрелки. За то время, когда "прямая" стрелка повернётся на некоторый угол, "отражённая" повернётся на тот же угол, но в другую сторону, то есть суммарный угол поворота стрелок равен полному обороту. Для каждой стрелки независимо вычислим её позицию. Для часовой это 12 минус текущая позиция, а для минутной &mdash; 60 минус текущая позиция. В обоих случая надо не забыть заменить 12 или 60 на ноль. B. Фактор палинромности ----------------------- Пусть существует какая-то подстрока, являющаяся палиндромом. Если мы уберём первый и последний символ палиндрома, оставшаяся строка тоже будет палиндромом. Будем повторять процесс до тех пор, пока не останется строка из двух или трёх букв (в зависимости от чётности). Подстрок длины два или три всегда линейное количество, и суммарная их длина также линейна, поэтому среди таких строк ответ можно выбрать наивным алгоритмом. Если же ни одна из подстро...
одной прямой. Для удобства будем рассматривать удвоенные координаты центров, тогда для получения, определяемой этой парой прямой. Наиболее удобный способ проверить, что три точки $a$, $b$ и $c$ ($a, Для решения этой задачи нам потребуется простой геометрический факт, что прямая делит окружность на, Рассмотрим движение "прямой" и "отражённой" стрелки. За то время, когда "прямая " стрелка повернётся

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

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

52.
Автор polosatic, история, 4 года назад, По-русски
Мои попытки ускорить куб до O(1) Всем привет. Недавно мне в голову пришла следующая задача: Рассмотрим множество точек **_(x, y)_** с целыми координатами таких, что 0 <= x < a и 0 <= y < b. Требуется найти количество остроугольных треугольников с вершинами в этих точках. ### Попытки проинтерполировать Ясно, что можно написать функцию **_f(a, b)_**, которая будет искать ответ и работать при этом за `(ab) ^ 3`. Я предположил, что она ведет себя как многочлен от двух переменных степени не более 6. Я попытался её проинтерполировать, используя [эту теорему](https://ru.wikipedia.org/wiki/Комбинаторная_теорема_о_нулях). Но у меня ничего не получилось, так как при мономах степени больше 6 интерполяция давала ненулевой коэффициент. Не получилось также с тупоугольными и прямоугольными треугольниками. <spoiler summary="code (для прямоугольных треугольников)"> ~~~~~ int stupid(int a, int b) { int ans = 0; for (int x1=0;x1<a;x1++) for (int x2=0;x2<a;x2++) for (int x3=0;x3<a;x3++) ...
. Пусть угловой коэффициент прямой AB равен k, тогда у прямой BC он равен `-1/k`. Тогда разность, 1. треугольники, у которых нет вершин на прямой `x = a - 1`, 2. треугольники, у которых есть вершины на прямой `x = a - 1` и две стороны параллельны осям

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

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

53.
Автор Zlobober, 10 лет назад, По-русски
Разбор разминочного раунда Яндекс.Алгоритм 2017 Задачи раунда были подобраны Олегом [user:snarknews,2017-04-22] Христенко. ### [Задача A. Арифметическая задача](https://contest.yandex.ru/algorithm2017/contest/4449/problems/A) В данной задаче требовалось написать ровно то, что требуется в условии &mdash; начать перебирать целые числа, начиная с единицы, дойти до первого числа, которое не делит $n$, и вывести его. Несмотря на то, что само $n$ достаточно больше, это работает быстро, так как в ограничениях задачи ответ всегда не превосходит 22 (наименьшее общее кратное всех целых чисел от 1 до 23 это 5354228880, что уже превосходит максимально возможное значение $n$). Это была одна из самых простых задач контеста, в которой, тем не менее, многие участники по причине спешки на первых минутах контеста получали WA 4 из-за того, что машинально перебирали ответ не от $1$ до бесконечности, а от $1$ до $n$, что, конечно же, не работает при $n = 1$ и $n = 2$. Особенно, наверное, обидно допустить такой баг, отправив задачу втёмную :) <...
через границу прямой.

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

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

54.
Автор awoo, история, 2 года назад, По-русски
Educational Codeforces Round 171 [рейтинговый для Div. 2] <img alt="Neapolis University Pafos" src="/predownloaded/9a/33/9a332fadbb47050ba9405057df022a6e37eaf5c0.png" style="float:right;height: 150px; margin: 10px; max-width:40%;"/> Привет, Codeforces! Благодаря поддержке [Neapolis University Pafos](https://www.nup.ac.cy/bsc-in-computer-science-and-artificial-intelligence), продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со [стипендиями JetBrains](https://lp.jetbrains.com/academy/csai-program/). Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Любопытно? [Присоединяйтесь к прямой трансляции] (https://jb.gg/dpdwgc) во **вторник, 29 октября в 17:00 UTC**, чтобы узнать о программе CSAI, ее учебном плане, структуре курсов, стипендиях, стажировках для студентов и практическом подходе к обучению. Хотите получить больше опыта в программирован...
. Любопытно? [Присоединяйтесь к прямой трансляции] (https://jb.gg/dpdwgc) во **вторник, 29 октября в 17

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

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

55.
Автор Edvard, история, 11 лет назад, По-русски
Разбор задач Educational Codeforces Round 12 ### [problem:665A] Задачу предложил Сергей Эрлих [user:unprost,2016-04-20]. Рассмотрим интервал времени, когда Симион будет находиться на трассе строго между городами $(x_1, y_1)$, ($x_1=60h+m, y_1=x_1+t_a$). Переберём встречный автобус. Пусть $(x_2, y_2)$ &mdash; это интервал времени, когда встречный автобус будет находиться строго между городами. Если пересечение этих интервалов $(x=max(x_1, x_2), y=min(y_1, y_2))$ не пусто, то Симион посчитает этот автобус. <spoiler summary="Решение на С++"> ~~~~~ int a, ta; int b, tb; int h, m; bool read() { if (!(cin >> a >> ta)) return false; assert(cin >> b >> tb); assert(scanf("%d:%d", &h, &m) == 2); return true; } void solve() { int x1 = h * 60 + m; int y1 = x1 + ta; int ans = 0; for (int x2 = 5 * 60 + 0; x2 < 24 * 60; x2 += b) { int y2 = x2 + tb; int x = max(x1, x2), y = min(y1, y2); if (x < y) ans++; } cout << ans << endl; } ~~~~~ </spoiler> Сложность: $O(1)$. ### [problem...

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

Разбор задач Educational Codeforces Round 12
  • Проголосовать: нравится
  • +70
  • Проголосовать: не нравится

56.
Автор awoo, история, 2 года назад, По-русски
Educational Codeforces Round 170 [рейтинговый для Div. 2] <img alt="Neapolis University Pafos" src="/predownloaded/9a/33/9a332fadbb47050ba9405057df022a6e37eaf5c0.png" style="float:right;height: 150px; margin: 10px; max-width:40%;"/> Привет, Codeforces! Благодаря поддержке [Neapolis University Pafos](https://www.nup.ac.cy/bsc-in-computer-science-and-artificial-intelligence), продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со [стипендиями JetBrains](https://lp.jetbrains.com/academy/csai-program/). Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Любопытно? Ознакомьтесь с [учебной программой](https://drive.google.com/file/d/19I776O8NG07ie2Q14wwBspuh3De4kbHc/view) прямо сейчас. Доступно ограниченное количество стипендий. Не упустите свой шанс учиться в Европе бесплатно! Ищете способ улучшить свои навыки и увеличить шансы на получение стипенд...

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

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

57.
Автор dalex, 12 лет назад, По-русски
Разбор задач Codeforces Round #301 (Div. 2) [problem:540A] Для каждого символа посчитаем, в какую сторону выгоднее вращать диск. Это можно сделать либо формулой: $min(abs(a[i] - b[i]), 10 - abs(a[i] - b[i]))$, либо даже двумя циклами for: в прямом или обратном направлении. [problem:540B] Посчитаем количество оценок, меньших $y$. Если таких больше $\frac{n-1}{2}$ штук, то мы не сможем удовлетворить второму условию (про медиану), и ответ -1. Иначе получим ровно столько оценок $y$, чтобы количество оценок, больших или равных $y$, было как минимум $\frac{n+1}{2}$ штук (возможно, это уже выполняется). Это минимальное необходимое действие для удовлетворения второго условия. Теперь, чтобы не нарушить первое условие, сделаем оставшиеся неизвестные оценки как можно меньше &mdash; единицами, и проверим сумму. Если она больше $x$, то ответ снова -1, иначе требуемые оценки найдены. [problem:540C] Я выделил здесь три случая, хотя некоторые из них можно объединить. 1. Если начальная и конечная клетка совпадают, посмотрим ...

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

Разбор задач Codeforces Round 301 (Div. 2)
  • Проголосовать: нравится
  • +103
  • Проголосовать: не нравится

58.
Автор zeliboba, 11 лет назад, По-русски
AIM Tech Round 2 <img src="http://aimtech.com/bitrix/templates/aimfund/images/logo.png" style="width:120px; height:179px; float: right;margin: 0 1.0em 1.0em 1.0em;" /> Привет, Codeforces! <a href="http://www.timeanddate.com/worldclock/fixedtime.html?msg=AIM%20Tech%20Codeforces%20Round&iso=20160204T2005&p1=166&ah=2">4 февраля, в четверг, в 20:05 MSK</a> состоится AIM Tech Codeforces Round. Раунд подготовили для вас сотрудники компании AIM Tech: [user:Kostroma,2016-02-03], [user:AlexDmitriev,2016-02-03], [user:yarrr,2016-02-03], [user:ArtDitel,2016-02-03], [user:ValenKof,2016-02-03], [user:bobrdobr,2016-02-03], [user:Agul,2016-02-03], [user:gchebanov,2016-02-03] и [user:zeliboba,2016-02-03]. Раунд пройдет во время Петрозаводских сборов, спонсорами которых наша компания стала в этом году. В каждом из дивизионов участникам будет предложено пять задач и два часа на их решение. Разбалловка будет статическая. Мы постарались сделать задачи проще, чем в прошлый <a href="http://codeforces.me/cont...

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

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

59.
Автор MikeMirzayanov, 12 лет назад, По-русски
Codeforces: дайджест улучшений за два месяца от 5-летия (февраль-март 2015) Привет! **Остались всего сутки до окончания <a href="/5years">кампании по сбору средств по случаю 5-летия Codeforces</a>. Мы рады вашей поддержке и помощи. Очень стараемся оправдывать ваши и собственные ожидания.** Для тех кто долго запрягает, напоминаем, что у вас еще есть немного времени присоединиться к <a href="/5years/supporters">замечательному списку друзей Codeforces</a> &mdash; помочь нам и получить подарок от команды Codeforces! В момент подведения итогов, конечно, хочется не столько считать деньги, а оценивать прогресс и проделанную работу. Я просмотрел все наши коммиты в Codeforces и [Polygon](https://polygon.codeforces.com) и составил дайджест улучшений/нововведений. Я не стал включать в дайджест малозаметные вам изменения в глубинах бэкенда (хотя улучшения стабильности должны быть видны), инфраструктурные работы, орг. работу по чемпионатам &mdash; но, поверьте, и такой работы было не мало :-) А вот и список достижений за примерно два месяца от нашего юбилея. ...

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

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

60.
Автор Zlobober, 12 лет назад, По-русски
Разбор VK Cup Round 3 [problem:542A] -------------- Зафиксируем окно на телеканале и поймём, какой ролик имеет с ним наибольшее пересечение. Ролики бывают четырёх видов: вкладывающиеся в окно, накрывающие окно, частично пересекающие его слева и частично пересекающие справа. Научимся разбирать каждый вид. Определить наличие накрывающего ролика просто &mdash; достаточно отсортировать ролики в порядке возрастания левой границы, и, идя по ним слева направо, поддерживать минимальную правую границу, достигнутую к текущему моменту. Если, проходя через окно $j$, мы видим, что текущее значение максимума не меньше, чем $b_j$, то есть ролик, накрывающий наше окно, а значит ответ для данного окна можно установить равным $(r_i - l_i) \cdot c_i$. Среди всех вкладывающихся роликов надо найти тот, который имеет максимальную длину. Это можно сделать похожим образом, но чуть-чуть сложнее. Воспользуемся методом сканирующей прямой. Проходя через правую границу ролика $r_i$, будем присваивать в некоторой структуре дан...
сделать похожим образом, но чуть-чуть сложнее. Воспользуемся методом сканирующейпрямой. Проходя через

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

Разбор задач VK Cup 2015 - Раунд 3
  • Проголосовать: нравится
  • +97
  • Проголосовать: не нравится

61.
Автор gridnevvvit, 13 лет назад, По-русски
Разбор Codeforces Round #203 (Div. 2) ##[problem:350A] Пусть $v = min(a_{i}), p = max(a_{i}), c = min(b_{i})$. Тогда если $max(2*v, p) < c$, то ответ $max(2*v, p)$. Иначе ответ $-1$. Авторское решение: [submission:4632352] ##[problem:350B] В этой задаче достаточно было реализовать следующее. По сути там задан граф, в виде массива предков для каждой вершины. Поскольку у каждой вершины максимум один предок, то для каждой вершины, являющейся отелем запустим такой алгоритм: будем подниматься по предкам $prev[v]$ до тех пор, пока не встретим вершину со степенью исхода большей единицы. Степень исхода лучше посчитать заранее. После всего обновим ответ. Асимптотика решения $O(n)$ по времени и $O(n)$ по памяти. Авторское решение: [submission:4632399] ##[problem:350C] Главная идея, это отсортировать все точки в порядке возрастания величины $|x_i| + |y_i|$. Дальше будем обрабатывать каждую точку жадно, максимум за шесть ходов. А именно, пусть мы хотим дойти сейчас до точки $(x,y)$. Пусть $x \ne 0$. Тогда на...
нормализации прямой будем называть следующее: Пусть у нас есть прямая $Ax + By + C$. Пусть также $g, )$. Перпендикулярная ей прямая, проходящая через центр отрезка $[(x1, y1),(x2,y2)]$ будет иметь уравнение $A = 2, прямой, в множество точек (некоторые точки могут встречаться несколько раз). В первом отображении в

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

Разбор задач Codeforces Round 203 (Div. 2)
  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

62.
Автор Ripatti, 15 лет назад, По-русски
Разбор задач Codeforces Beta Round #74 <p><b>A div2</b>. В этой задаче можно было промоделировать весь процесс. А именно - рассматривать все минуты подряд и, в зависимости от того, какого цвета в данную минуту подошла кабинка, уменьшать соответствующую группу студентов $G$ на $min(|G|,2)$, где $|G|$ - размер группы. После этого нужно определить самую первую по счету минуту $t$, в которую все три группы опустеют. Тогда $t+30$ будет ответом. Это решение за $O(r+g+b)$.<br>[cut]<br>Также в этой задаче есть решение за $O(1)$. Оно выражается следующей формулой: $ans = max(3[(R+1)/2] + 27, 3[(G+1)/2] + 28, 3[(B+1)/2] + 29)$, где $[x]$ --- округление вниз до ближайшего целого.<br><br><b>B div2</b>. Задачу можно было решить реализовав ровно то, что написано в условии. А именно: для каждой буквы просмотреть все буквы в той же горизонтали и в той же вертикали, что и данная буква. Если найдется такая же - эту букву выводить не следует. Сканирование и вывод ответа можно было совместить, например, так:<br><br>FOR(a,1,n) FOR(b,1,m)<br>{<b...
луча с шаром, а не прямой).

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

Разбор задач Codeforces Beta Round 74 (Div. 1 Only)
  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

63.
Автор KADR, 14 лет назад, По-русски
Разбор задач Codeforces Round #153 Представляю полный разбор задач Codeforces Round #153. Если возникнут какие-то вопросы или пожелания -- пишите в комментариях, постараюсь ответить. ### [problem:252A] (A div 2) Переберем все отрезки чисел в массиве. Для каждого из них найдем $xor$ и выберем тот отрезок, у которого $xor$ максимальный. Осталось только вывести этот $xor$. ### [problem:252B] (B div 2) Если все числа в массиве равны между собой, то искомой пары позиций не существует. Теперь предположим, что в массиве есть хотя бы 2 различных числа. Будем перебирать все пары различных чисел и для каждой такой пары попробуем поменять местами числа на этих позициях, после чего проверим, является ли массив отсортированным и в случае необходимости, выведем ответ. Если этот алгоритм не нашел нужной пары позиций, то выведем -1. Кажется, что этот алгоритм работает за $O(N^3)$. На самом деле это не так и его время работы можно оценить как $O(N)$. Дело в том, что если есть хотя бы 3 пары позиций с различными числами, т...
предпоследней и применять к ней $(k - t) / 2$ раз связку "обратная перестановка +прямая перестановка". Это

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

Разбор задач Codeforces Round 153 (Div. 1)
Разбор задач Codeforces Round 153 (Div. 2)
  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

64.
Автор slycelote, 16 лет назад, перевод, По-русски
Codeforces Beta Round #26 — разбор задач <h3>A.&nbsp;<a href="http://codeforces.me/contest/26/problem/A">Почти простые числа </a><a href="../../../contest/26/problem/A"> </a></h3>Это задача на реализацию: для каждого числа от 1 до n разложим его на простые множители и посчитаем количество различных простых делителей.<br><br><h3>B.&nbsp;<a href="http://codeforces.me/contest/26/problem/B">Правильная скобочная подпоследовательность </a><a href="../../../contest/26/problem/B"> </a></h3>Будем читать строку слева направо и поддерживать на каждом шаге баланс скобок (т.е. разность между количеством выписанных открывающих и закрывающих скобок). Этот баланс должен быть всегда неотрицательным. Поэтому если он равен нулю и мы читаем закрывающую скобку, ее нужно пропустить и не выписывать. Ответ будет равен удвоенному количеству выписанных закрывающих скобок.<br><br><h3>C.&nbsp;<a href="http://codeforces.me/contest/26/problem/C">Паркет </a><a href="../../../contest/26/problem/C"> </a></h3>Докажем ...
, относительно прямой y=-1. Получится новый график, оканчивающийся в точке $(m+n, -2-n-k+m)$. Обратно, любой

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

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

65.
Автор Ripatti, 15 лет назад, По-русски
Разбор задач Codeforces Beta Round #82 (Div. 2) <p><b>A.</b> (<a href="http://codeforces.me/contest/106/problem/A">ссылка</a>) Решение этой задачи описано в четвертом абзаце условия. Его надо было внимательно прочитать и реализовать. Единственная сложность которая могла возникнуть - как опередить какое достоинство старше. Для этого можно было двумя проходами по массиву [ '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A' ] определить номера достоинств карт в массиве, а полученные числа сравнить.<br>[cut]<br><b>B.</b> (<a href="http://codeforces.me/contest/106/problem/B">ссылка</a>) Можно было использовать дополнительный массив, в котором true означает, что ноутбук устаревший, а false - что нет. Значение в каждой ячейке этого массива определяется проходом по всем ноутбукам и сравнения его параметров с параметрами текущего ноутбука. За еще один проход среди всех не устаревших ноутбуков нужно было выбрать самый дешевый.<br><br><b>C.</b> (<a href="http://codeforces.me/contest/106/problem/C">ссылка</a>) Создадим массив dp размера n на m. dp[i][...
минимумы f2 в плоскостях, перпендикулярных выбранной прямой. f3 тоже выпукла вниз - доказательство, Рассмотрим какую либо прямую. Функция расстояния от точек на этой прямой до какой либо точки будет, Теперь рассмотрим плоскость и выберем в ней прямую. Повесим на каждую точку этой прямой минимум из

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

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

66.
Автор ch_egor, 10 лет назад, По-русски
Codeforces Round #359 Editorial Если заметите неточности или ошибки, сообщите личным сообщением. <br> <br> [Div2A Раздача мороженого](http://codeforces.me/contest/686/problem/A) <br> Автор идеи: [user:cdkrot,2016-06-24] <br> Подготовил задачу: [user:ch_egor,2016-06-23] <br> В задаче требовалось просто реализовать то, что было сказано в условии. <br> Если у вас не получилось, то возможно вы забыли использовать 64-битные типы данных, или сделали какую-то ошибку. <br> Код правильного решения: <br> <br> <spoiler summary="C++ code"> ~~~~~ #include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cstring> #include <vector> #include <stack> #include <queue> #include <deque> #include <set> #include <map> #include <cassert> #include <algorithm> #include <iomanip> #include <ctime> #include <cmath> #include <bitset> #pragma comment(linker, "/STACK:256000000") using namespace std; typedef long long int int64; typedef long double double80; const int INF...
Будем решать данную задачу методом сканирующей прямой. Будем идти по вертикалям слева на право и

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

Разбор задач Codeforces Round 359 (Div. 1)
Разбор задач Codeforces Round 359 (Div. 2)
  • Проголосовать: нравится
  • +85
  • Проголосовать: не нравится

67.
Автор Hohol, 14 лет назад, По-русски
Разбор Codeforces Round #124 [problem:197A] Если первый игрок своим ходом не может поставить тарелку на стол (стол слишком маленький, и тарелка не помещается, т.е. $2r > min(a,b)$), выигрывает второй игрок. Иначе выигрывает первый игрок. Выигрышная стратегия такова: первый игрок ставит свою первую тарелку в центр стола, а затем симметрично отражает ходы соперника относительно центра стола стола. Легко видеть, что если в этом случае второму игроку удастся совершить ход, первому это также удастся. А если не удастся, первый игрок победит, что ему и было нужно. [problem:197B] Решение задачи --- разбор случаев. Легко понять, что важны лишь степени многочленов и их коэффициенты при старшем члене, остальные числа в инпуте --- для отвода глаз. 1. Если степень знаменателя больше, ответ равен "0/1". 2. Если степень числителя больше, ответ --- бесконечность. Чтобы понять, какая именно, надо посмотреть на знаки при старших коэффициентах. Если знаки одинаковые, то положительная, иначе --- отрицательная. 3. ...
Т.к. никакие три точки не лежат на одной прямой, решение всегда существует.

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

Разбор задач Codeforces Round 124 (Div. 1)
Разбор задач Codeforces Round 124 (Div. 2)
  • Проголосовать: нравится
  • +59
  • Проголосовать: не нравится

68.
Автор Ripatti, 14 лет назад, По-русски
Разбор задач Codeforces Round #150 **Adiv2.** Рассмотрим массив $A$ целых чисел от 1 до $nk$. Удалим из него все числа $a_i$, а все, что осталось, запишем в массив $B$. Массив $B$ будет состоять из $(n-1)k$ элементов. Теперь для $i$-го ребенка следует вывести числа $a_i$, $B[(n-1)*(i-1) + 1]$, $B[(n-1)*(i-1) + 2]$, ... $B[(n-1)*(i-1) + n - 1]$ (индексация $B$ начинается с 1). Автор --- [user:Gerald] [cut] . **Bvid2.** Решение 1. Напишем перебор по всем числам, состоящим из не более чем 9 цифр (число $10^9$ преверим отдельно). Схематично это будет выглядеть так: ~~~~~ dfs( int num ) // запускать как dfs(0) if (num > 0 && num <= n) ans++ if (num >= 10^8) return for a = 0..9 do if num*10+a>0 then if число num*10+a содержит не более 3х цифр then dfs( num*10+a ) ~~~~~ В ans теперь будет находиться ответ. Напишем, запустим &mdash; увидим, что работает быстро (это решение выполняется одинаковое время на всех тестах). Отошлем. Решение 2. Будем строить все безусловно счастл...

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

Разбор задач Codeforces Round 150 (Div. 1)
Разбор задач Codeforces Round 150 (Div. 2)
  • Проголосовать: нравится
  • +44
  • Проголосовать: не нравится

69.
Автор fcspartakm, 9 лет назад, По-русски
Улучшения Codeforces и Polygon (февраль — апрель 2018) Привет, Codeforces. В этом посте мы хотим рассказать о нововведениях в Codeforces и Polygon, реализованных в последнее время. #### Блоги (Codeforces) Раньше в Codeforces записи в блогах можно было либо публиковать вместе с переводом, либо скрывать в черновики обе версии. Теперь записи в блогах можно публиковать или скрывать в черновики отдельно от их переводов. В случае, если есть опубликованная запись в блоге, а ее перевод скрыт в черновиках, либо в случае обратной ситуации, при редактировании записи или ее перевода вы увидите соответствующее предупреждение об этом. Для корректной работы была полностью пересмотрена логика секции Прямого эфира и детального прямого эфира. ![ ](https://pp.userapi.com/c845017/v845017279/1e8c9/pXSRGuDEPTU.jpg) #### Переписки (Codeforces) Также добавлен новый функционал в разделе Переписки. Для некоторых пользователей было неудобно, что переписка с одним человеком могла становиться очень большой, и для того, чтобы найти переписку с другим, ну...

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

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

70.
Автор ivan.popelyshev, 17 лет назад, По-русски
Другой разбор задач Codeforces Beta Round #2 <div class="from-renderer"><div class="from-renderer"> <div class="from-renderer"> <div class="from-renderer"> <div class="from-renderer"> <div class="from-renderer"> <div class="from-renderer"> <div class="from-renderer"> <div class="from-renderer"> <div class="from-renderer"> <div class="from-renderer"> <div class="from-renderer">Начнём с конца.<br><br> <h2><a href="http://codeforces.me/contest/2/problem/C">Задача С. Commentator problem<br></a></h2> Пусть $R$ это расстояние из точки А до какой-то окружности с центром в О и радиусом $r$. Тогда из точки окружность видна под углом $2 \arcsin (r/R)$...
$ является либо прямой - серединным перпендикуляром AB

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

Разбор задач Codeforces Beta Round 2
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

71.
Автор yeputons, 15 лет назад, По-русски
Разбор командной олимпиады школьников Саратова 2011 Вопросы, предложение, более красивые решения можно и нужно предлагать в комментариях. <center><h3>Задача A. Лифт</h3></center> <br /> <p>Можно разобрать четыре случая, а можно заметить, что если обозначить front/back за 0/1 (b), а из a вычесть единицу, то a XOR b будет ответом (0/1). Время и пямять - $O(1)$.</p> <br /> <br /> <center><h3>Задача B. Что? Где? Когда?</h3></center> <br /> <p>Решается &quot;в лоб&quot; одним циклом: пока $k$-й вопрос сыгран, увеличить $k$ на один, и, если $k&gt;n$, то $k=1$. Время и пямять - $O(n)$.</p> <br /> <center><h3>Задача C. Винни-Пух и мёд</h3></center> <br /> <p>Одним из решений было написать ровно то, что просят в условии. Итераций Винни-Пуха будет не более $3n$ (к каждой банке он обращается не более 3-х раз), каждую итерацию можно выполнить за $O(n)$ (поиск максимума в массиве). Время - $O(n^2)\approx 10^4$ операций, память - $O(n)$. </p> <p>Но есть решение короче: давайте заметим, что порядок поедания мёда ни на что не влияет. Теперь посмотри...

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

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

72.
Автор Wandoka, история, 2 года назад, перевод, По-русски
Оптимален ли ваш сетап для спортивного программирования? Кликни и узнай! В этом блоге я сделал тест, который поможет вам определить, оптимален ли ваш сетап или нет. Ниже я напишу список критериев, по которым я буду его оценивать и разбаловку. И в конце вы сможете узнать, к какой "группе людей" вы относитесь, прямо как в тестиках на персонажа из аниме в Вконтакте. Я сюда включил практически всё, что мне пришло в голову, если я что-то забыл, предложите в комментариях. Но добавлять вещи как **У меня есть интернет** и **На моей клавиатуре есть большая часть клавиш** я не буду :) Это несерьёзный блог, но если вы новичок, вы, может быть, найдёте для себя что-то новое. Но это всё равно никак не поможет вам поднять рейтинг, для этого нужно решать задачи. ### Вы можете компилировать код перед посылкой - $0$ баллов: Я не знаю, как компилировать код самостоятельно, и просто отправляю его на проверку - $10$ баллов: Я умею запускать код до отправки Я видел много школьников, которые отправляют посылки никогда не запус...

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

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

73.
Автор Malinovsky239, 14 лет назад, По-русски
Разбор задач Codeforces Round #140 ### [A div2. Куда свернуть?](http://codeforces.me/contest/227/problem/A) Посмотрим на векторное произведение $\overrightarrow{AB}$ на $\overrightarrow{BC}$, численно равное $\overrightarrow{AB_x} \cdot \overrightarrow{BC_y} - \overrightarrow{AB_y} \cdot \overrightarrow{BC_x}$. Знак векторного произведения определяется знаком синуса ориентированного угла между векторами (т.к. векторное произведение также равно $|\overrightarrow{AB}| \cdot |\overrightarrow{BC}| \cdot sin(\overrightarrow{AB}, \overrightarrow{BC})$), а именно этот-то знак нам и нужно узнать. Если произведение равно нулю, то это в данной задаче означает, что $A, B$ и $C$ лежат на одной прямой, а значит ответ &mdash; <<TOWARDS>>. Если произведение больше нуля, то ответ &mdash; <<LEFT>>. И, наконец, если оно меньше нуля, то ответ &mdash; <<RIGHT>>. Также стоит обратить внимание, что вычисление векторного произведения требуется производить в 64-битном типе, чтобы избежать переполнения. [Решение](http://past...
прямой, а значит ответ — <>.

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

Разбор задач Codeforces Round 140 (Div. 1)
  • Проголосовать: нравится
  • +57
  • Проголосовать: не нравится

74.
Автор GlebsHP, история, 8 лет назад, По-русски
Разбор задач финального раунда Яндекс.Алгоритма 2018 Интеллектуальный вендинг ------------------ Автор идеи и разработчик: [user:glebshp,2018-05-29]. Заметим, что в любом случае Аркадий не может потратить больше денег, чем у него есть, поэтому количество купленных бутылок не превзойдёт $z = \lfloor \frac{b \cdot 10^{6} + c}{r} \rfloor$. Однако, может так получится, что Аркадию придётся купить меньше бутылок, если в какой-то момент у Аркадия не будет хватать мелочи на покупку без сдачи, а нужно количество сдачи в автомате не будет. Заметим, что суммарное количество мелочи в обороте не меняется и составляет $c + d$. При этом, если $c + d \geq 999\,999$, то либо у Аркадия всегда найдётся мелочь, чтобы купить очередную бутылку, либо автомат сможет дать сдачу, если платить только с помощью банкнот. В этом случае ответ равен $z$. Если же $c + d < 999\,999$, то может быть, что у Аркадия хватает мелочи для совершения покупки без сдачи, может быть, что в автомате достаточно сдачи для покупки банкнотами, но не может быть одновременно вы...
прямой с деревом отрезков.

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

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

75.
Автор HolkinPV, 14 лет назад, По-русски
Codeforces Round #123 (Div. 2) Разбор Задач [problem:195A] Полное видео скачается через $all = (c \cdot a + b - 1) / b$ секунд. В этой задаче можно было перебрать величину ответа $1<=t<=all$. Чтобы удовлетворить условию задачи, достаточно проверить, что в последний момент времени t0 = all выполняется условие, написанное в тексте задачи, а именно $t0 \cdot b >= (t0 - t) \cdot a$. [problem:195B] В этой задаче нужно было аккуратно реализовать описанный в условии процесс. Вначале заметим, что мяч с номером $i > m$ попадет в одну корзину с мячом под номером $i - m$. Поэтому достаточно распределить первые $m$ мячей. Это удобно сделать при помощи двух указателей $lf$, $rg$, начиная с середины. Поочередно кладем мяч сначала слева, затем справа и двигаем указатели. Единственный раз, когда нужно дважды подвинуть левый указателей, возникает в самый первый момент, если $m$ нечетно. [problem:195C] Данная задача носила реализационный характер. В своем решении я поступал следующим образом. Удалим из текста все пробелы, кроме...
заданных функций является прямая. Найдем уравнение этой прямой. Предположим, мы рассматриваем $i$-ую

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

Разбор задач Codeforces Round 123 (Div. 2)
  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

76.
Автор MikeMirzayanov, 11 лет назад, По-русски
Разбор задач Educational Codeforces Round 1 Задачи учебные &mdash; постараемся сделать разбор подробным. ### [problem:598A] Если бы в этой задаче не было бы "хитрости" и надо бы было просто найти сумму $1 + 2 + \dots + n$, то, воспользовавшись формулами суммирования арифметической прогрессии, можно было прийти к результату $s=n \cdot (n+1) / 2$ (числа такого вида называются треугольными). Однако каждое число, которое является степенью двойки, должно быть просуммировано не со знаком "плюс", а со знаком "минус". Давайте вычтем по два раза (так как первое вычитание просто изымет число из суммы, а второе &mdash; вычтет) каждую из степеней двойки, которые не превосходят $n$. Проще всего это сделать с помощью цикла вроде этого: ~~~~~ long long pow2 = 1; while (pow2 <= n) s -= pow2 * 2, pow2 *= 2; ~~~~~ Значение $s$ после такого цикла и будет ответом. Количество итераций этого цикла не превосходит двоичного логарифма числа $n$ (точнее &mdash; еще плюс единица), что является числом около 30 для максимального возмо...
Асимптотика: $O(m \dot n \log n)$ (для обработки одной прямой нужна сортировка всех точек

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

Разбор задач Educational Codeforces Round 1
  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

77.
Автор Eran, 10 лет назад, По-русски
Codeforces Round #365 (Div. 2) Editorial ####[703A &mdash; Мишка и игра](http://codeforces.me/contest/703/problem/A) Всё, что Вам требовалось сделать в этой задаче, &mdash; посчитать количество раундов, в которых победит Мишка, количество раундов, в которых победит Крис. Для этого следовало завести две переменные $countM$ и $countC$. Если в очередном раунде Мишка выкидывала на костях большее значение, чем Крис, то 1 следовало прибавлять к переменной $countM$. Если меньшее &mdash; к переменной $countC$. В конце нужно было сравнить полученные значения и вывести ответ. ####[703B &mdash; Мишка и путешествие](http://codeforces.me/contest/703/problem/B) Рассмотрим первую столицу. Заметим, что стоимость исходящих из неё дорог равна $c[id_1] \, \cdot \, (sum - c[id_1])$, где $sum$ &mdash; суммарная красота **всех** городов. Таким образом, переходя от одной столицы к другой, мы сможем посчитать суммарную стоимость дорог, исходящих из столиц. Однако не стоит забывать, что дороги между столицами в таком случае будут посчитаны...
$, при котором описанная прямая будет касаться многоугольника. Это может быть сделано при помощи, прямая не пересекает многоугольник (т.е. либо мы можем перейти дорогу перед автобусом, либо автобус

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

Разбор задач Codeforces Round 365 (Div. 2)
  • Проголосовать: нравится
  • +70
  • Проголосовать: не нравится

78.
Автор romanandreev, 11 лет назад, перевод, По-русски
Codeforces Round #345: editorial [problem:651A] ------------------ Автор идеи: [user:fcspartakm,2016-03-09], разработчик: [user:fcspartakm,2016-03-09]. Главной идеей решения является то, что в каждый момент времени нам нужно заряжать джойстик с самым низким уровнем заряда. По-этому мы можем просто проэмулировать процесс или вывести простую формулу за $O(1)$. [problem:651B] ------------------ Автор идеи: [user:fcspartakm,2016-03-09], разработчик: [user:fcspartakm,2016-03-09]. Давайте посмотрим на ответ, в нем будет несколько подряд идущих отрезков возрастания красоты, а между ними красота будет падать. Будем решать задачу жадно: давайте отсортируем массив значений и будем набирать возрастающие куски по очереди. Чтобы набрать очередной кусок мы идем слева-направо и среди каждого множества картин с одинаковым значением мы выберем только одно. Так будем продолжать пока картины не закончатся. Если аккуратно это реализовать, то получим решение за $O(n \log n)$. Но такое решение дает нам всю последователь...
выяснить, сколько точек лежат на каждой горизонтальной и на каждой вертикальной прямой. Это легко, Если у нас есть $k$ точек на одной горизонтальной или вертикальной прямой, то они добавят в ответ

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

Разбор задач Codeforces Round 345 (Div. 1)
  • Проголосовать: нравится
  • +116
  • Проголосовать: не нравится

79.
Автор DrunkMaster, 5 лет назад, По-русски
Как тренироваться: почему для школьных олимпиад не надо учить сложные темы и решать гробы Всем доброго времени суток! На этот пост меня вдохновил [user:Wind_Eagle,2022-04-05] своим [постом](https://codeforces.me/blog/entry/101549). Этот блог является заключительным в цикле [челлендж::поготовься к респе](https://codeforces.me/blog/entry/99856). Советую перед прочтением сначала прочитать его, а также вышеописанный блог, так как данный наследуется от них. Для начала подведу итоги челленджа. Он оказался скорее неуспешным, чем успешным. Единственное, что я получил от него &mdash; опыт, который будет полезен в будущем. Итак, итоги: - Взять диплом на республике. Не выполнил, остался без диплома. Нарешал очень плохо, наконец понял, что главная проблема не столько даже лежит в программировании, сколько в психологии. Заметил очень нехорошую особенность: пришёл как на первый, так и на второй тур, все 5 часов не мог сосредоточиться, чего-то боялся (сам не знаю, чего). Из-за этого я фактически не думал, а скорее просто выписывал на листочке что-то и пытался просто реализовать...
- методы решения задачи в оффлайн: алгоритм Мо, сканирующая прямая

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

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

80.
Автор Sereja, 13 лет назад, По-русски
Codeforces Round #243 tutorial ### [problem:426A] Посчитаем сумму всех элементов $Sum$ и значение максимального элемента $M$. Если $Sum-M \le S$ то ответ &mdash; да, иначе &mdash; нет. ### [problem:426B] Решим задачу с обратной стороны. Будем пытаться _свернуть_ нашу матрицу как можно больше число раз. _Свернуть_ означает операцию, обратную к описанной в условии. Для проверки, можно ли свернуть матрицу нужно, что бы выполнялись следующие условия: 1). $n~mod~2=0$ 2). $a_{i,j} = a_{n - i+1,j}$ for all $1 \le i \le n, 1 \le j \le m$. ### [problem:425A] Переберем интервал, на котором будет находится максимальная сумма. Для улучшения суммы, мы можем поменять не более $K$ минимальных элемента из интервала на не более $K$ максимальных элементов, не принадлежащих отрезку. Так как $n$ не большое мы можем делать это любым образом, например отсортировать все элементы на интервале по возрастанию и вне интервала по убыванию, а дальше будем менять максимальный элемент из вне интервала на минимальный в интерв...
Теперь нужно научится проверять: есть ли пара точек на некоторой прямой. Запишем все эти пары в, Удалим все просмотренные точки и отразим оставшиеся относительно прямой $x=y$. Мы получили ситуацию

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

Разбор задач Codeforces Round 243 (Div. 1)
Разбор задач Codeforces Round 243 (Div. 2)
  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

81.
Автор Fefer_Ivan, 13 лет назад, По-русски
Обновление функциональности групп <img style="margin: 0 1em 1em 1em; float: right" src="http://assets.codeforces.com/images/updates.jpg"/> Добрый день, Codeforces. Сегодня функциональность групп была обновлена и расширена. Вот краткий список изменений: - Появилась возможность прикреплять к группе записи из личного блога. - Появилась возможность создавать записи прямо в блоге группы. Эта запись не будет видна в прямом эфире и голоса за неё или за комментарии к ней не будут влиять на вклад. - Создавать или прикреплять к группе записи могут только менеджеры. Комментировать эти записи могут любые члены группы. - Появился новый вид участника группы: зритель. Зритель – это член группы, который не может зарегистрироваться на соревнование группы и не отображается в таблице результатов группы. Зритель может смотреть результаты и задачи, а так же читать и комментировать блог группы. Например, если вы хотите, чтобы кто-либо мог наблюдать за тренировками вашей группы, но не смог писать их, можно его пригл...

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

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

82.
Автор Nickolas, 15 лет назад, По-русски
Codeforces Round #105 (Div. 2): разбор задач Итак, разбор задач. Сразу уточню, что задачу [user:MikeMirzayanov,2012-02-02] не угадал никто (неплохо мы замаскировались, а?) --- это была задача C про переборчивую корыстолюбивую принцессу. Собственно, с этой задачи раунд и начался, все остальные я придумала уже для продолжения темы. [problem:148A] Общее количество драконов D может быть достаточно небольшим, поэтому задачу можно решать без затей, перебором драконов от 1 до D и проверкой каждого дракона отдельно. Сложность решения --- O(D). [cut] Существует более идейное решение со сложностью O(1), основанное на формуле включения-исключения. Для каждого из четырех критериев избиения драконов считаем количество драконов, которые под него подпадают, т.е. чей номер кратен соответствующему числу. Затем считаем количество драконов, которые подпадают под пары, тройки и четверки критериев, т.е. чей номер кратен наибольшему общему кратному соответствующих наборов чисел. Количество чисел от 1 до D, кратных T, равно D / T. Наконец...
прямой от пещеры до замка. В моем решении основной единицей были события "дракон в пещере и

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

Разбор задач Codeforces Round 105 (Div. 2)
  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

83.
Автор orz, история, 5 лет назад, По-русски
Быстрое умножение по модулю Рассмотрим такую задачу: даны три целых числа $x$, $y$ и $m$, $0 \leqslant x,y < m < 2^{32}$, найти $xy\bmod m$. По-хорошему хотелось бы просто перемножить эти два числа, а потом применить операцию остатка: ~~~~~ uint32_t prod(const uint32_t x, const uint32_t y, const uint32_t m) { return x * y % m; } ~~~~~ Как вы, возможно, догадываетесь, это решение неверное. Всё дело в том, что в такой процедуре возможно переполнение: операция `x * y` выполняется в типе `uint32_t`, и на самом деле промежуточным результатом выполнения этой операции будет не $xy$, а $xy\bmod2^{32}$. Если после этого взять результат по модулю $m$, он может отличаться от правильного: $$ \left(xy\bmod2^{32}\right)\bmod m\ne xy\bmod m. $$ Выход прост — перемножать необходимо в большем типе: ~~~~~ uint64_t prod_uint64(const uint64_t x, const uint64_t y, const uint64_t m) { return x * y % m; } ~~~~~ Если так делать, то, поскольку $xy<2^{64}$, это произведение точно не переполнится, и после взятия ре...

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

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

84.
Автор awoo, история, 2 года назад, По-русски
Educational Codeforces Round 169 [рейтинговый для Div. 2] <img alt="Neapolis University Pafos" src="/predownloaded/9a/33/9a332fadbb47050ba9405057df022a6e37eaf5c0.png" style="float:right;height: 150px; margin: 10px; max-width:40%;"/> Привет, Codeforces! Благодаря поддержке [Neapolis University Pafos](https://www.nup.ac.cy/bsc-in-computer-science-and-artificial-intelligence), продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со [стипендиями JetBrains](https://lp.jetbrains.com/academy/csai-program/). Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Любопытно? Ознакомьтесь с [учебной программой](https://drive.google.com/file/d/19I776O8NG07ie2Q14wwBspuh3De4kbHc/view) прямо сейчас. Доступно ограниченное количество стипендий. Не упустите свой шанс учиться в Европе бесплатно! В [contest_time:2004] состоится [contest:2004]. Этот раунд будет **ре...

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

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

85.
Автор Connector, 15 лет назад, По-русски
Разбор Codeforces Beta Round #75 <p><strong>Задачи A(div2), B(div2)</strong><br></p>В этих задачах требовалось реализовать ровно то, что описано в условии. В задаче <em>B</em> не рекомендовалось использовать BigInteger в Java из за скорости работы с ним.<br><p><strong>Задача C(div2), A(div1)</strong><br></p>В этой задаче буквы из строки $s1$ следовало набирать жадно: брать самую левую букву справа от последней использованной, если требуемой буквы не было справа от последней использованной, то следовало начать поиск с начала строки $s1$ и увеличить ответ на единицу. Однако реализация "в лоб" получала $TL$ и имела асимптотику $O(Ans*|s1|)$.&nbsp;<br><br>Это решение можно оптимизировать, например, следующим образом. Для каждой позиции в $s1$ предпосчитать позиции самых левых символов от текущего для всего алфавита. Это можно было реализовать идя справа налево в строке $s1$ храня позиции последнего вхождения символа каждого вида в строку. Такое решение имеет асимптотику $O(|s1|*K + |s2|)$, где $K$ --- размер алфавита.<br>...

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

Разбор задач Codeforces Beta Round 75 (Div. 1 Only)
Разбор задач Codeforces Beta Round 75 (Div. 2 Only)
  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится

86.
Автор fcspartakm, 10 лет назад, По-русски
Polygon: обновления (январь — апрель 2017) Всем привет! Пришла пора рассказать о нововведениях в [Polygon](https://polygon.codeforces.com/) &mdash; системе для подготовки задач по программированию. Именно в ней подготавливаются все задачи к раундам Codeforces и многим другим олимпиадам. Системой Polygon могут пользоваться все желающие в любой момент времени. #### Общее На странице со списком используемых в задаче файлов, а также на страницах чекера, интерактора и валидатора теперь отображаются специальные поля с соответствующими примерами. Это поможет новым пользователям быстрее разобраться в системе. ![ ](http://codeforces.me/predownloaded/98/10/9810d9c6ccbbab2e6a2f7ba59145647f77985dbe.png) [cut] <br/> Было добавлено несколько новых уведомлений на почту при изменениях в задачах и контестах. Теперь письма отправляются при добавлении, изменении и удалении прав на задачу/контест. Также во всех письмах теперь содержится прямая ссылка на измененный контест/задачу. Кроме этого добавлена возможность добавления спе...
теперь содержится прямая ссылка на измененный контест/задачу. Кроме этого добавлена возможность

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

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

87.
Автор pkhaustov, 14 лет назад, По-русски
Разбор задач Codeforces Round #152 **Задача A (div2) &mdash; Шкафы** Автор: [user:max777alex,2012-11-27] В этой задаче можно рассмотреть независимо все левые дверцы шкафов и, аналогично, все правые. Очевидно, чтобы привести все левые дверцы шкафов в одинаковое положение, нужно определить какое из двух состояний ("левая дверца открыта" или "левая дверца закрыта") встречается чаще. Все левые дверцы, которые находятся в другом состоянии требуется привести к этому. Аналогично надо поступить и с правыми дверцами. Если аккуратно посчитать в таком случае количество операций изменения состояния дверцы, то это оно и будет ответом. **Задача B (div2) &mdash; Котенок Гав** Авторы: [user:max777alex,2012-11-27], [user:KhaustovPavel,2012-11-27] В данной задаче требовалось найти минимальное положительное $N$-значное число, которое делится без остатка на $2$, $3$, $5$ и $7$. Очевидно, раз все эти четыре числа являются простыми, то число, которое делится на все эти четыре числа, должно делиться на их произведение $2 \cdot ...
координаты строго положительны), и имеется прямая $L_{0}$ под углом $\alpha_{2} - \alpha_{1

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

Разбор задач Codeforces Round 152 (Div. 2)
Разбор задач Codeforces Round 152 (Div. 1)
  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

88.
Автор machine_solution, 9 месяцев назад, По-русски
Как додуматься до... задачи "D. Бинарный не-поиск и запросы" из Codeforces Round 1082 (Div. 1) Сегодняшний пост посвящён [задаче D](https://codeforces.me/problemset/problem/2201/D) из прошедшего [Codeforces Round 1082 (Div. 1)](https://codeforces.me/contest/2201). Условие задачи не самое интуитивное, я не буду его повторять и просто попрошу прочитать оригинал В этой задаче просят считать две величины &mdash; $k_{max}(a)$ и $f(a)$, причём второе значение зависит от первого, поэтому давайте сначала попробуем разобраться, как считается $k_{max}(a)$ хотя бы для изначального массива. То есть, перефразируя часть условия, которое относится к интересующему нас значению, нам нужно посчитать **наибольшее** такое $k$, что в массиве существуют два подотрезка, для которых мультимножества значений совпадают **Вопрос 1:** как посчитать $k_{max}(a)$ для изначального массива? <spoiler summary="Подсказка 1.1"> Согласитесь, условие про совпадающие мультимножества значений не очень удобное. Давайте попробуем его немного упростить и найдём отрезки, которые ему удовлетворяют, но, с другой...
Мы на финишной прямой. Осталось только разобраться с тем фактом, что $k_{max}(a)$ может меняться

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

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

89.
Автор awoo, история, 21 месяц назад, По-русски
Educational Codeforces Round 175 [рейтинговый для Div. 2] <img alt="Neapolis University Pafos" src="/predownloaded/9a/33/9a332fadbb47050ba9405057df022a6e37eaf5c0.png" style="float:right;height: 150px; margin: 10px; max-width:40%;"/> Привет, Codeforces! Благодаря поддержке [Neapolis University Pafos](https://www.nup.ac.cy/bsc-in-computer-science-and-artificial-intelligence), продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со [стипендиями JetBrains](https://lp.jetbrains.com/academy/csai-program/). Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Любопытно? Ознакомьтесь с [учебной программой](https://drive.google.com/file/d/19I776O8NG07ie2Q14wwBspuh3De4kbHc/view) прямо сейчас. Доступно ограниченное количество стипендий. Не упустите свой шанс учиться в Европе бесплатно! В [contest_time:2070] состоится [contest:2070]. Этот раунд будет **ре...

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

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

90.
Автор RAD, 15 лет назад, По-русски
Codeforces Round #113 (Div. 2) Разбор задач Изначально мы хотели расположить задачи по сложности так: A-C-E-D-B. Насчет порядка последних двух мнения разделились. Посмотрим, что покажут результаты. [problem:166A] В этой задаче нужно сделать то, что написано в условии --- отсортировать команды по заданному компаратору: ($p_1 > p_2$) или ($p_1 = p_2$ и $t_1 < t_2$). После этого надо разбить команды на группы одинаковых, и найти размер группы, команды из которой делят $k$-ое место. Многие почему-то при равенстве числа задач сортировали команды по убыванию времени, а не по возрастанию. Такие решения случайно проходят претесты и получают WA #13. [problem:166B] Так как многоугольник A --- выпуклый, достаточно проверить, что все вершины многоугольника B лежат строго внутри многоугольника A. Идейно самое простое решение – построить выпуклую оболочку из точек обоих многоугольников, и проверить, что в нее входят точки только из первого многоугольника. Но в таком решении придется писать выпуклую оболочку, которая обязательно б...
прямой, а это на порядок сложнее других решений и содержит частный случай.

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

Разбор задач Codeforces Round 113 (Div. 2)
  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

91.
Автор darthrevenge, история, 2 года назад, По-русски
Числа Каталана, ну типа, и Educational 170 E [Submission](https://codeforces.me/contest/2025/submission/285935595) Хочется рассказать о логике, использованной при решении задачи Е (которую я не успел дописать за отведенное время и засабмитил на дорешивании). Для этого пригодится знание того, что такое числа Каталана, а также как умение выводить их формулу. Подробно про числа Каталана можно прочитать, например, на вики: [тык](https://en.wikipedia.org/wiki/Catalan_number), Можно по разному дать определение, мы определим число $C_n$ как количество правильных скобочных последовательностей длины $2n.$ Нас интересует следующий довольно известный и изящный метод найти это число. Рассмотрим координатную сетку, по которой нам нужно дойти из угла $(0,0)$ в угол $(n,n)$. Мы можем идти только вправо или вверх. Шаг вправо соответствует открывающейся скобке, шаг вверх &mdash; закрывающейся. Тогда существует взаимно однозначное соответствие между правильной скобочной последовательностью длины $2n$ и путем из $(0,0)$ в $(n,n)$, не перес...
общую точку с прямой $y=x+1.$ Возьмем первую (с наименьшим $x$) общую точку $(a, a+1)$ и отразим участок

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

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

92.
Автор awoo, история, 20 месяцев назад, По-русски
Educational Codeforces Round 176 [рейтинговый для Div. 2] <img alt="Neapolis University Pafos" src="/predownloaded/9a/33/9a332fadbb47050ba9405057df022a6e37eaf5c0.png" style="float:right;height: 150px; margin: 10px; max-width:40%;"/> Привет, Codeforces! Благодаря поддержке [Neapolis University Pafos](https://www.nup.ac.cy/bsc-in-computer-science-and-artificial-intelligence), продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со [стипендиями JetBrains](https://lp.jetbrains.com/academy/csai-program/). Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Любопытно? Ознакомьтесь с [учебной программой](https://drive.google.com/file/d/19I776O8NG07ie2Q14wwBspuh3De4kbHc/view) прямо сейчас. Доступно ограниченное количество стипендий. Не упустите свой шанс учиться в Европе бесплатно! В [contest_time:2075] состоится [contest:2075]. Этот раунд будет **ре...

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

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

93.
Автор Nickolas, 9 лет назад, По-русски
Codeforces Round #455 (Div. 2) Editorial #### [problem:909A] Самое простое решение &mdash; сгенерировать все возможные логины (перебрав все пары непустых префиксов имени и фамилии и скомбинировав их) и выбрать из них первый по алфавиту. Более быстрое решение основано на следующих свойствах логина. Во-первых, в первом по алфавиту логине префикс фамилии всегда состоит ровно из одной буквы (если префикс фамилии содержит две или более буквы, удаление последней буквы префикса позволяет получить логин, расположенный раньше в алфавитном порядке). Во-вторых, префикс имени не должен содержать букв, больших или равных первой букве фамилии (за исключением первой буквы имени), из аналогичных соображений. Эти свойства дают жадное решение: будем перебирать буквы имени, начиная со второй. [cut] Как только найдена буква, большая или равная первой букве фамилии, возвращаем префикс имени до этой буквы (не включая ее) плюс первую букву фамилии. Если таких букв нет, возвращаем все имя плюс первую букву фамилии. #### [problem:909B]...
Рассмотрим участок координатной прямой $[i,i+1]$. Очевидно, все отрезки, покрывающие этот участок

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

Разбор задач Codeforces Round 455 (Div. 2)
  • Проголосовать: нравится
  • +125
  • Проголосовать: не нравится

94.
Автор Kogut_Ivan, история, 8 месяцев назад, По-русски
Интенсив для 5-8 классов: готовимся к региону Келдыша и отбору в Сириус ![ ](/predownloaded/39/e2/39e203ec5f5a9109442525a77f78cc6bc7a0db37.jpeg) Контесты региона Келдыша и финального отбора на смену Информатика.Юниоры (ступень «Алгоритмы и структуры данных‑1») в Сириус **полностью совпадают по задачам и пройдут 18 апреля** **И по этому поводу мы проводим 4-недельный интенсив** – поможем отточить навыки и уверенно выступить на контесте! **Если совсем кратко о формате:** 30+ задач уровня и формата предстоящего контеста и их разбор с кодом на C++ и Python, запись всех полезных материалов и живое общение с преподавателем А теперь подробнее **Старт интенсива:** • Уже был &mdash; 16 марта • Присоединиться можно и сейчас – контесты и записи разборов будут доступны. Но в реальном времени интереснее!) **Формат – максимально приближен к реальной олимпиаде:** 1. 4 недели интенсивной подготовки 2. Каждый понедельник – новый полноценный контест уровня регионального этапа Келдыша на платформе codeforces: длительность 3 часа, решить можно в у...
3. В конце каждой недели – подробный разбор от преподавателя: прямой эфир с записью, коды задач на

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

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

95.
Автор Sammarize, 11 лет назад, По-русски
Codeforces Round 313 — Подробный разбор задач [problem:560A] В этой задаче главное &mdash; заметить, что если есть купюра номинала 1, то любую сумму денег можно выдать единичными купюрами. Если же такой купюры нет, то как раз сумму 1 представить нельзя. Поэтому, если нет купюры номинала 1, то ответ &mdash; 1, а если такая купюра есть &mdash; то -1. [problem:560B] Легко заметить, что можно прижать две картины друг в другу какими-то двумя краями, например, разместить одну картину прямо над другой. Тогда высота двух картин будет суммой высот картин, а ширина &mdash; максимум из ширин картин. Осталось перебрать все варианты, как повёрнуты картины и как при этом повёрнут стенд. Вот реализация. [problem:559A] & [problem:560C] Сперва заметим, что если правильный треугольник с целой стороной $k$ отрезками, параллельными сторонам, разделить на правильные треугольники со стороной 1 (тут появляется картинка), то площадь большого треугольника будет в $k^2$ раз больше площадей маленьких треугольничков и, следовательно, треугольн...

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

Разбор задач Codeforces Round 313 (Div. 1)
Разбор задач Codeforces Round 313 (Div. 2)
  • Проголосовать: нравится
  • +97
  • Проголосовать: не нравится

96.
Автор Dart-Xeyter, история, 5 лет назад, По-русски
Открытая олимпиада школьников по программированию (с разбором A, C, D, E, F, G, I). Кажется, подобного поста ещё не было, поэтому... Здесь вы можете обсуждать всё об Открытке 2021-2022 :) Также, вы можете прочитать мои решения некоторых задач (возможно, их число &mdash; разобранных &mdash; будет постепенно увеличиваться). [Условия задач.](https://olympiads.ru/zaoch/2021-22/zaoch/zaoch_long_20211231.pdf) [Таблица результатов.](https://olympiads.ru/zaoch/2021-22/standings.html) [Наконец-то добавленный официальный разбор.](https://olympiads.ru/zaoch/) <spoiler summary="Решение А."> Пишем алгоритм за квадрат. Очевидно, если $i$ зафиксировано &mdash; мы можем набирать нашу последовательность $b$ жадно. Теперь перейдём от $i$ к $i+1$. Если $i$ было нашим $b_1$, посмотрим на ближайшее число справа равное $b_1$. Если оно дальше, чем $b_2$, посмотрим на ближайшее от этого $b_1$ справа, равное $b_2$. И так далее, если сейчас $b_i$, проверяем, что $b_{i+1}$ левее $b_i$, и если да &mdash; ищем новое $b_{i+1}$ справа. Можно создать $map$ с позициями чисел в $a$ ...

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

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

97.
Автор MikeMirzayanov, 17 лет назад, По-русски
Воспоминания: ACM-ICPC World Finals 2009 <div> <img src="http://lh6.ggpht.com/_mSdPzSw5zAo/S2KKSsTdWyI/AAAAAAAADGE/vpMUDSuenS0/IMG_0494.JPG" style="float: left;margin: 1.0em;">Финал 33-го чемпионата мира по программированию среди студенческих команд ACM-ICPC был проведен в столице Швеции, Стокгольме. Третий раз Европа принимала у себя чемпионат: в 1999 году соревнования проходили в Эйнтховене (Нидерланды), а в 2004 в Праге (Чехия). Впервые ключевую роль в проведении чемпионата от принимающей стороны играл университет: соревнования проходили в библиотеке Королевского технологического института. В финале чемпионата приняли участие сто лучших команд мира, в то время как в отборочных этапах состязались 7109 команд из 1838 университетов и 88 стран. Для Саратовского государственного университета это было шестое участие в финале чемпионата мира.&nbsp;</div> <div> <br></div> <div>Участники соревнования проживали в двух гостиницах, расположенных в историческом центре Стокгольма, районе Гамла Ст...
Еще одной особенностью этого чемпионата была прямая многочасовая трансляция, которая

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

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

98.
Автор Sereja, 13 лет назад, По-русски
Разбор Codeforces Round #187 [problem:315A] Просто для каждой бутылки проверим, можно ли открыть ее другой. В данной задаче проходили абсолютно любые решения. [problem:315B] Будем поддерживать все элементы в массиве, но дополнительно заведем переменную add: сколько нужно добавить ко всем элементам. Тогда про добавлении ко всем элементам просто увеличим add. При выводе будем выводить элемент массива + величину add. При обновлении будем ставить элемент равным значению, которое нужно поставить минус текущая величина add. [problem:314A] Заметим, что если мы удалили некоторого участника, то мы никогда не удалим участников с меньшими номерами, так как их сумма будет только увеличиваться. Поэтому просто последовательно рассмотрим всех участников, и если участник не подходит, то удалим его. [problem:314B] Понятно, что можно жадно искать количество вхождений 2й строки в первой, но такое решение работает долго. Для ускорения процесса можно искать в первой строке строку, которая задает период вто...

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

Разбор задач Codeforces Round 187 (Div. 1)
Разбор задач Codeforces Round 187 (Div. 2)
  • Проголосовать: нравится
  • +76
  • Проголосовать: не нравится

99.
Автор FelixArg, 6 месяцев назад, перевод, По-русски
Educational Codeforces Round 191 [рейтинговый для Div. 2] <img alt="Neapolis University Pafos" src="/predownloaded/9a/33/9a332fadbb47050ba9405057df022a6e37eaf5c0.png" style="float:right;height: 150px; margin: 10px; max-width:40%;"/> Привет, Codeforces! Благодаря поддержке [Neapolis University Pafos](https://www.nup.ac.cy/bsc-in-computer-science-and-artificial-intelligence), продолжается серия образовательных раундов. Во [contest_time:2233] состоится [contest:2233]. Этот раунд будет **рейтинговым для участников с рейтингом менее 2100**. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Вам будет предложено **6 или 7 или 67 задач на 2 часа**. Мы надеемся, что вам они покажут...

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

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

100.
Автор MikeMirzayanov, 12 лет назад, По-русски
5 лет Codeforces Привет, друзья! Да-да, именно к друзьям Codeforces я хочу сейчас обратиться. Совсем недавно Codeforces исполнилось 5 лет, и по этому случаю мы открываем кампанию по сбору средств на работу и развитие Codeforces. Мы горим желанием развиваться, двигаться вперед и будем рады вашему участию в кампании. Приглашаем вас рассмотреть возможность поддержать Codeforces. Подробности кампании можно найти по ее [прямой ссылке](/5years). <iframe width="420" height="315" src="https://www.youtube.com/embed/PwQQK8pOzgk" frameborder="0" allowfullscreen></iframe> Михаил Мирзаянов **UPD: У нас <a href="/blog/entry/16658">отличные новости!</a>**
ее [прямой ссылке](/5years).

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

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