Разбор Codeforces Round 860 (Div. 2) Всем спасибо за участие, надеюсь вам понравились задачи! Вы можете оценить задачи раунда в соответствующих спойлерах под разбором. [problem:1798A]<br> <div class="spoiler"> <b class="spoiler-title">Подсказка 1</b> <div class="spoiler-content" style="display: none;"> Для каждого индекса $i$ нет смысла проводить операцию $\ge 2$ раз, так как применение операции с одним индексом дважды ничего не меняет. </div></div> <div class="spoiler"> <b class="spoiler-title">Подсказка 2</b> <div class="spoiler-content" style="display: none;"> Условие $a_n = \max(a_1, a_2, \ldots, a_n)$ равносильно тому, что $a_i \leq a_n$ для всех $i$. Значит на каждый индекс $i$ наложено всего 2 условия: $a_i \leq a_n$ и $b_i \leq b_n$. </div></div> <div class="spoiler"> <b class="spoiler-title">Разбор</b> <div class="spoiler-content" style="display: none;"> [tutorial:1798A]</div></div> <spoiler summary="Решение"> ``` for _ in range(int(input())): n = int(input()) a = list(map(int, in...

Full text and comments »

Разбор задач тестового раунда Яндекс.Алгоритм Тестовый раунд и его разбор были подготовлены [user:snarknews,2013-07-07] и [user:Gassa,2013-07-07]. Задачи тестового раунда уже использовались ранее в других соревнованиях. Все последующие раунды будут состоять из новых оригинальных задач, и вы все еще можете [зарегистрироваться](http://algorithm.contest.yandex.ru/register/) и поучаствовать в [квалификационном раунде](http://algorithm.contest.yandex.ru/contest/307/enter/). По ходу раунда многие участники пытались сдавать задачи &laquo;втёмную&raquo;, время от времени даже выходя на первые строчки таблицы &mdash; правда, как оказалось после системных тестов, с одной фактически решённой задачей. На момент окончания раунда первое место занимал [user:tourist,2013-07-07], сдавший все задачи, кроме B, &laquo;втёмную&raquo;. Второе место занимал [user:vepifanov,2013-07-07], сдавший A, C и D &laquo;втёмную&raquo;, а B и F &mdash; &laquo;в светлую&raquo; (причём каждую из них &mdash; с одной штрафной попыткой), третье &mdash; [user:Ant...

Full text and comments »

Как додуматься до... задачи "F. Изучение бинарного поиска" из Codeforces Round 1088, Div. 1 + Div. 2 Всем привет! Сегодняшний пост посвящён [задаче F](https://mirror.codeforces.com/contest/2211/problem/F) с недавнего [Div 1 + Div 2 раунда](https://mirror.codeforces.com/contest/2211). Она стала локальной знаменитостью, потому что является более решаемой задачей, чем [задача Е](https://mirror.codeforces.com/contest/2211/problem/E) того же раунда. А сегодня мы разберёмся, почему же эта задача такая простая Итак, переходим к задаче. В ней для каждого отсортированного массива $a$ с элементами от $1$ до $m$ нужно посчитать суммарное количество итераций, за которое стандартный бинпоиск находит в массиве каждый элемент от $1$ до $m$. В задаче эта сумма описана как $f(a,1,1,n)+f(a,2,1,n)+\ldots+f(a,m,1,n)$. Ограничение: $n, m \leq 10^6$ Давайте попробуем что-то понять про количество итераций бинпоиска в зависимости от искомого числа $k$. Интуиция подсказывает, что на всех массивах бинпоиск будет вести себя регулярным образом, нужно это лишь формализовать. Для того, чтобы быстрее нащупать идею, давайте нем...

Full text and comments »

Russian Code Cup 2017 Warmup — Разбор задач (и полетов) <p> Всем привет и спасибо тем, кто принял участие в разогревочном раунде. </p> <p> Во-первых, хотелось бы извиниться перед участниками за очереди тестирования в середине-конце первого часа. Для разогревочного раунда мы решили использовать задачи ИОИП &mdash; команда авторов задач RCC и ИОИП в целом совпадает &mdash; тур подготовили Виктория Ерохина ([user:viktoria,2017-03-19]), Илья Збань ([user:izban,2017-03-19]), Станислав Наумов ([user:josdas,2017-03-19]), Михаил Путилин ([user:SpyCheese,2017-03-19]), Андрей Станкевич ([user:andrewzta,2017-03-19]), Дмитрий Филиппов ([user:DimaPhil,2017-03-19]), Григорий Шовкопляс ([user:GShark,2017-03-19]). Мы хотели дать возможность всем желающим познакомиться с довольно интересным, на наш взгляд, набором задач. </p> <p> К сожалению, мы не учли один аспект. Можно заметить, что в RCC мы стараемся делать мультитест в задачах, ведь самая затратная операция &mdash; запустить решение участника на тесте. Поскольку ИОИП расчитывалась на меньшую наг...

Full text and comments »

Многопоточность на контестах Всем привет! Многим известны соревнования Google Code Jam, Facebook Hackercup, IPSC, ch24, deadline24 и т.п. Их объединяет то, что в задаче даётся инпут с мультитестом внутри, на который нужно посчитать ответ у себя локально. Мне стало интересно, пользуетесь ли вы распараллеливанием? Современные машины позволяют дать ощутимый прирост, например, чтобы избежать [таких](/blog/entry/3875) ситуаций. А прошедший deadline24 мы писали так  _([само описание событий](http://k-mihey.livejournal.com/39098.html))_ Я решил написать свой вариант шаблона, и вот что у меня получилось: [code](http://pastebin.com/tCYfCw8V). Вот ещё другой подход от [user:Kormyshov,2015-03-14]: [code](http://paste.org.ru/?nku223). Кто может предложить другие варианты, желательно на с++? А может на других языках это делается проще? А может у кого-то есть инструменты, позволяющие параллелить инпут на несколько машин (кроме рук и фле...

Full text and comments »

ABBYY Cup 3.0 — Finals. Разборы Всем привет! Вчера состоялся финал ABBYY Cup 3.0! Хочется сказать большое спасибо всем-всем: кто решал контест, кто помогал его готовить, авторам задач и еще много кому! О том, как прошел День открытых дверей ABBYY, мы расскажем позже, а пока разборы: #### Задача A Утверждение: если прогулка начинается с дерева $i$ и заканчивается в дереве $j$, то нужно выпилить все деревья до $i$, все деревья после $j$ и все деревья с отрицательной эстетической привлекательностью между $i$ и $j$. Для решения подзадачи A1 достаточно для каждой пары деревьев с одинаковой эстетической привлекательностью воспользоваться утверждением и выбрать максимум; ограничения позволяли сделать это хоть за $O(n^2)$, хоть за $O(n^3)$. Для решения подзадачи A2 требуется такое утверждение: сколько бы ни было деревьев с одинаковой эстетической привлекательностью, нам всегда выгодно рассматривать только пару из самого левого и самого правого таких деревьев. Тогда количество различных рассматриваемых пар сократ...

Full text and comments »

Краткие правила Google Code Jam - еще не поздно принять участие! <p><a href="http://code.google.com/codejam/">Google Code Jam </a>- очередное всемирное соревнование по спортивному программированию (<b>язык</b> - только английский). Для участния нужно иметь Google-аккаунт, зарегистрироваться и принять участие в квалификационном раунде, который продлится <b>до трёх часов ночи</b> (по Москве) сегодняшнего дня.<br><br>Итак, правила:<br></p><ol><li>Есть несколько задач, тесты открытые (с мультитестом) - Вам нужно прислать в систему <b>ответ</b> и программу, если жюри усомнится в том, что Вы играли честно. Допустимые языки - любые. В каждой задаче есть две подзадачи: Small input и Large input. Каждая из них оценивается по своей системе и может быть либо решена полностью (тогда Вы получаете некоторое количество баллов), либо не решена вообще (получаете ноль). Участники ранжируются по количеству баллов (больше - лучше) и штрафному времени, именно в таком порядке.</li><li><b>Small input.</b> Ограничения небольшие. Для того, чтобы попробовать сдать подзадачу,...

Full text and comments »

Facebook Hacker Cup 2012 в Тренировках! Добрый вечер! Я [подумал](http://mirror.codeforces.com/blog/entry/6341#comment-119892), что было бы неплохо собрать задачи прошлых лет в одном месте, чтобы можно было удобно их решать для подготовки к предстоящим раундам Facebook Hacker Cup 2013. Поэтому я создал [тренировку](http://mirror.codeforces.com/gym/100159), где Вы можете решить 9 задач из 1-3 раундов Facebook Hacker Cup 2012. Может быть, это первый и последний контест, где Вы увидите задачу с ограничением по времени 100 секунд, но не волнуйтесь &mdash; это случилось потому, что в задаче мультитест, поэтому на самом деле на каждый кейс приходится не больше 5 секунд. Желаю Вам приятного времяпрепровождения! Удачи!

Full text and comments »

Мультитест(Как читать в MS С++) Всем привет! Буду очень благодарен за помощь в данном вопросе. На самом деле я понятия не имею, как его считывать, возможно написал полнейший бред, но это работало в запуске на кф. Пробовал вот так: ~~~~~ #include<iostream> #include<cstdio> #include<stdio.h> using namespace std; ... int main(){ FILE * pFile = stdin; // FILE * pFile = fopen("a.in","r"); - так тоже пробовал. freopen("a.in","r",stdin); freopen("a.out","w",stdout); m=1; while(true){ fscanf(pFile,"%d",&a); if(feof(pFile)) break; } return 0; } ~~~~~

Full text and comments »

Пара слов о том, как правильно готовить условия задач <div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-color: transparent; "><h3 id="internal-source-marker_0.28558810288086534"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-color: transparent; "><h3 id="internal-source-marker_0.28558810288086534"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-color: transparent; "><h3 id="internal-source-marker_0.28558810288086534"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-color: transparent; "><h3 id="internal-source-marker_0.28558810288086534" style="font-weight: normal; text-align: justify; "><font class="Apple-style-span" face="Arial"><span class="Apple-style-span" style="font-size: 15px; white-space: pre-wrap;"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-color: transparent; font-family: 'Times New R...

Full text and comments »

Мультитесты Кто-нибудь может объяснить мне, зачем в задачах делают мультитесты?

Full text and comments »