Очень скоро начнется личная олимпиада ИТМО. Клик.
Это будет последний шанс попрактиковаться на задачах от ИТМО перед финалом ИОИП для российских школьников и Всеукраинской олимпиадой по программированию для украинских.
Очень жаль, что эти 2 события совпадают (ИОИП 18 марта и UOI 17 марта) :(Предлагаю здесь обсудить задачи.
UPD: Контест окончен, можно обсуждать задачи. Приветствуются доказательства решений, а не посты типа "Я расписал пару тесткейсов в Bшке и заметил, что можно отсортировать массив и по-очереди искал среднее арифметическое между двумя соседними, записывая результат в правый элемент". Особенно интересует решение Cшки на 100.
если по последней отправке не просмотрен результат, то возьмется максимум из нее и всех просмотреных?
Там где scored, тот и возьмется.
Вообще-то нет. Эта фича не работает.
Feedback уже последние 2 контеста как работает. Конечно не полностью, только по отдельным группам тестов, но баллы на них уже можно посмотреть.
feedback — да, а scored — нет. у меня знакомая в прошлый раз последний сабмит сделала неудачный(на 0 баллов) и, чтобы не переотправлять, нажала scored на другом(где было > 0 баллов). Зачлось ей 0.
ну вы же лучше знаете, лол.
зачем вы ее минусуете у меня была такая же проблема.
Уже завершилось. Как решать последние 4 задачи? Верно ли, что в А ответ будет N-K, где K — наидлиннейшая неубывающая, заканчивающаяся в N-ом элементе? Почему в B проходит брать на каждом шаге 2 минимальных?
По А могу сказать, что верно. Вот даже накидал корявое доказательство: Мы имеем право менять все элементы последовательности на следующий, при этом не имея право менять последний. Значит нам нужно найти наименьшее количество "мешающих" элементов, чтобы образовать неубывающую последовательность. Очевидно, что наименьшее количество мешающих равно n-k, где k наибольшая неубывающая последовательность. Поскольку нам не на что менять n-ый элемент, то мы должны искать длину такой последовательности, которая включает в себя n.
Меня самого интересует док-во Bшки, т.к. на контесте запихнул решение по расписанным на бумажке тесткейсам.
Как уже сказал автор темы, ИОИП и его трансляция пересекается с Всеукраинской олимпиадой. Для меня, как и для многих других 11-классников, это был последний контест на neerc.imfo.ru/school. Это один из немногих IOI-стайл контестов, которые проводятся регулярно, поэтому на протяжении нескольких лет пытался почаще в них участвовать. Вообще, с нирком связано много приятных моментов...
Хочется сказать спасибо людям, которые все это время готовили контесты. Ваша работа сыграла большую роль в моей, и далеко не только моей, подготовке.
Непосредственно сегодня, контест был очень интересным. Если бы четвертую заменить на последнюю с прошлого контеста, то был бы, наверное, лучший проблемсет в этом сезоне. Несмотря на это, я благополучно завалил >.<
Еще раз спасибо!
Задача D отлично подходит для школьного контеста!
Даже слегка недотягивает, эллипс неплохо бы смотрелся и внутри многоугольного футляра :D :D
мне кажется, или Б была проще, чем А?
в С надо было поддерживать декартовы деревья эйлеровых обходов? или как ее нормально решать?
Во время контеста не довела, но решение вроде правильное, хоть и небыстрое:
Будем держать необычное дерево отрезков. Для каждого отрезка из дерева (пусть он соответствует отрезку [L, R]) и числа k (от 0 до 10) посмотрим на решение исходной задачи на суффиксе, начинающемся с (L + k)-того символа. От этого нас интересуют две вещи — сколько (возможно, последняя влезет не полностью) подстрок будет выбрано до R включительно, и где закончится последняя (возможно, вылезающая за границу) подстрока. Эти два числа мы и будем хранить в каждой вершине дерева отрезков.
Обновление предка через детей делается очевидно за ~10 операций, при запросе нам придётся обновить не более 10 листьев. Возможно, это решение можно как-нибудь ускорить
P.S. а ещё сначала неправильно прочитала условие, и 1.5 часа думала, что надо решить задачу, когда сумма подстроки <= x, может, это тоже вполне разрешимая задача?
да, клево, что-то подобное придумал, но до ума не довел
кажется, авторское такое же
Интересно, я почему-то думала, что авторское будет быстрее моего, но вроде они даже обновляют также
Там просто корневая. Будем насчитывать next[i] — куда мы попадем, когда проскочим число, начинающееся с i. При изменении символа изменится не более 10 некстов.
Теперь поделим на кусочки и будем насчитывать finish[i] — куда мы попадем, когда пропрыгаем до конца кусочка из i и ans[i] — за сколько попадем. Теперь мы умеем обновлять за размер кусочка + 10*10 и искать ответ за кол-во кусочков. Ура.
Авторское было такое, как описала iroro, но такое решение тоже хорошее.
не совсем понятно, мы храним целое количество чисел в блоке? вот мы что-то изменили, finish[i] изменился, теперь у нас блок заканчивается в другом месте и следующий начинается тоже в другом, как это изменять.
или у нас каждое i — это начало какого-то блока длины sqrt(N)? и изменение это изменение всех блоков, которые включают наш символ?
Блоки состоят из символов. finish[i] — это самый правый символ в который мы припрыгаем внутри блока. Т.е. еще один прыжок и мы уже выпрыгнули из блока.
Это позволяет считать ответ следующим образом:
При изменении мы пересчитваем все finish внутри блока. Они никак не зависят от чисел в других блоках.
код
Добавте пожалуйста в тренировки.
пожалуйста, обьясните как решали задачу B?
Отсортировать массив а потом всегда добавлять среднее арифметические первых 2 чисел, а потом удалить эти 2 числа и добавить среднее арифметическое в массив. Делать так пока в массиве не останется 1 число. Это и есть ответ.
Только сейчас увидел, что там N<=200000. А я еще думал, что авторы сделали на первые две группы слабые тесты, что неправильное решение их проходило, а дело то в массиве :(
Контест в тренировках — 2012-2013 Цикл интернет-олимпиад. Седьмая личная олимпиада (2 марта 2013 года)