Does anyone know when the results of APIO 2012 will appear? Results of open contest were published several days ago, test data is available for two days already, but results are still ‘TBA’.
Довольно странно, что никто не создал пост для обсуждения. Сейчас заканчивается мартовский раунд USACO 2012. Желающие еще могут начать участие в течениие целых 18.5 часов. Предлагаю после окончания обсуждать тут задачи.
Всем привет.
Меня достало прокручивать страницу блога в поисках новых комментариев, а заходить в "прямой эфир" не всегда удобно, поэтому написал userscript, который добавляет справа страницы кнопки перемотки по новым комментариям.
Работает в Firefox (надо поставить плагин GreaseMonkey), Chrome. Скорее всего, работает в Opera и чем-нибудь еще - никакого специфичного API нет.
Установить можно по ссылке. Если выдаётся исходник - значит, Ваш браузер не поддерживает userscripts.
О багах и предложениях можно отписываться тут.
UPD: теперь стало возможным просматривать родительский комментарий при наведении мышки на "^". Клик по-прежнему работает.
UPD2: создал репозиторий на GitHub.
На Росолимпе появились тесты к прошлогоднему региону. Заодно выложил заочный этап заочки того же года.
Всё там же, где обычно: http://yeputons.net/tsweb/. Если кому-нибудь еще надо, то регистрируемся и сдаём. Можно переключаться между контестами ("List of all contests"). Система следующая: вы получаете результат выполнения программы на тестах из примера (и на online-группе, если такая есть), и, если хотите, можете открыть полные детальные результаты (как на IOI в этом году, кнопка "Use token"). Если программа не прошла примеры - она не тестируется вообще.
Вопросы, предложение, более красивые решения можно и нужно предлагать в комментариях.
Задача A. Лифт
Можно разобрать четыре случая, а можно заметить, что если обозначить front/back за 0/1 (b), а из a вычесть единицу, то a XOR b будет ответом (0/1). Время и пямять - O(1).
Задача B. Что? Где? Когда?
Решается "в лоб" одним циклом: пока k-й вопрос сыгран, увеличить k на один, и, если k > n, то k = 1. Время и пямять - O(n).
Задача C. Винни-Пух и мёд
Одним из решений было написать ровно то, что просят в условии. Итераций Винни-Пуха будет не более 3n (к каждой банке он обращается не более 3-х раз), каждую итерацию можно выполнить за O(n) (поиск максимума в массиве). Время - O(n2) ≈ 104 операций, память - O(n).
Но есть решение короче: давайте заметим, что порядок поедания мёда ни на что не влияет. Теперь посмотрим на то, сколько мёда из каждой банки съест Винни-Пух, а сколько оставит Пятачку. Нетрудно понять, что если ai > = 3k, то Винни-Пух оставит Пятачку ai - 3k килограмм, а если ai < 3k, то 
. Теперь решение задачи - один цикл. Время и память - O(n).
Сегодня, в четверг, 13 октября 2011 года в 15:02 по Москве состоится 521-й TopCoder Single Round Match (время в других городах).
Так как остальные задачи я не то что не пытался решить, а даже не читал, публикую те решения, которые узнал
Задача A. Домино
Для начала поймём, что на квадраты 2x2 всё поле разбивается однозначно и это можно сделать жадным алгоритмом. Теперь у нас есть 14 квадратов. Далее можно сделать необязательное преобразование, от которого лично мне стало жить проще: построим граф на 14 вершинах, ребро между вершинами будет тогда и только тогда, когда у соответствующих квадратов есть общая доминошка. В принципе, это даже какой-то оптимайз по времени, но не суть важно.
Теперь задача такова: есть граф на 14 вершинах, надо раскрасить их в цвета от 0 до 6 так, чтобы все рёбра были разными (два ребра одинаковы, если цвета концов совпадают). Утверждается, что решение - перебор. Перебираем цвет первой, второй, третьей, ..., 14й вершины, на каждом шаге проверяем, что у нас не появилось ребро той же расцветки, что уже было (естесственно, делаем это массивом bool'ов). После чего останется вывести ответ и какую-нибудь раскраску.
Однако это решение может не зайти по времени. Остался один мощный оптимайз. Заметим, что, по сути, разницы между цветами нет. Значит, цвета в раскраске можно переставлять как угодно. Теперь научимся считать количество ответов с точностью до перестановок цветов, а в конце домножим его на 7!=5040. Это просто: достаточно ввести условие, что цвет очередной вершины либо встречался раньше, либо идет сразу после максимального использованного цвета. Например, после цветов 0 1 2 1 0 2 могут идти только цвета 0..3.
Чтобы уверовать в то, что это решение зайдёт, можно грубо оценить количество ответов. Каждая вершина раскрашена в один из семи цветов, каждый цвет встречается ровно два раза, плюс мы не учитываем различные перестановки. Итого получается
, что, очевидно даже при отсечении на последнем шаге рекурсии, влезает в TL.
Теперь задача такова: есть граф на 14 вершинах, надо раскрасить их в цвета от 0 до 6 так, чтобы все рёбра были разными (два ребра одинаковы, если цвета концов совпадают). Утверждается, что решение - перебор. Перебираем цвет первой, второй, третьей, ..., 14й вершины, на каждом шаге проверяем, что у нас не появилось ребро той же расцветки, что уже было (естесственно, делаем это массивом bool'ов). После чего останется вывести ответ и какую-нибудь раскраску.
Однако это решение может не зайти по времени. Остался один мощный оптимайз. Заметим, что, по сути, разницы между цветами нет. Значит, цвета в раскраске можно переставлять как угодно. Теперь научимся считать количество ответов с точностью до перестановок цветов, а в конце домножим его на 7!=5040. Это просто: достаточно ввести условие, что цвет очередной вершины либо встречался раньше, либо идет сразу после максимального использованного цвета. Например, после цветов 0 1 2 1 0 2 могут идти только цвета 0..3.
Чтобы уверовать в то, что это решение зайдёт, можно грубо оценить количество ответов. Каждая вершина раскрашена в один из семи цветов, каждый цвет встречается ровно два раза, плюс мы не учитываем различные перестановки. Итого получается
, что, очевидно даже при отсечении на последнем шаге рекурсии, влезает в TL.Задача B. Надмножество
Задача была немножко (или множко?) идейной. Одним из возможных решений является разделить множество точек пополам веритикальной прямой (если не получается ровно, та так, чтобы разница была минимальна), решить задачу рекурсивно для двух половин, и добавить на разделяющую прямую точки со всеми встречающимися в ответах для половин y'ами.
Докажем корректность. Если точки лежат в одной половине, всё мы верим, что верно решили подзадачу. Если же они лежат в разных половинах, то их bounding box пересекает нашу прямую, и в точках пересечения выделенные точки есть (посльку их y'и встречались слева и справа).
Прошу сообщество рассказать остальные задачи в комментариях
Докажем корректность. Если точки лежат в одной половине, всё мы верим, что верно решили подзадачу. Если же они лежат в разных половинах, то их bounding box пересекает нашу прямую, и в точках пересечения выделенные точки есть (посльку их y'и встречались слева и справа).
Прошу сообщество рассказать остальные задачи в комментариях
Добрый всем день.
Недавно меня заинтересовал вопрос, и хочу с ним обратиться к тем, кто имеет доступ к логам проверки решений - на скольки процентов тестов обычно хоть кто-то валится? На каждом тесте, на половине, на каких-то трёх?
Недавно меня заинтересовал вопрос, и хочу с ним обратиться к тем, кто имеет доступ к логам проверки решений - на скольки процентов тестов обычно хоть кто-то валится? На каждом тесте, на половине, на каких-то трёх?
Google Code Jam - очередное всемирное соревнование по спортивному программированию (язык - только английский). Для участния нужно иметь Google-аккаунт, зарегистрироваться и принять участие в квалификационном раунде, который продлится до трёх часов ночи (по Москве) сегодняшнего дня.
Итак, правила:
- Есть несколько задач, тесты открытые (с мультитестом) - Вам нужно прислать в систему ответ и программу, если жюри усомнится в том, что Вы играли честно. Допустимые языки - любые. В каждой задаче есть две подзадачи: Small input и Large input. Каждая из них оценивается по своей системе и может быть либо решена полностью (тогда Вы получаете некоторое количество баллов), либо не решена вообще (получаете ноль). Участники ранжируются по количеству баллов (больше - лучше) и штрафному времени, именно в таком порядке.
- Small input. Ограничения небольшие. Для того, чтобы попробовать сдать подзадачу, надо нажать соответствующую кнопку. Вам выскочит окно с запросом на скачивание файла - это тесты. После нажатия на кнопку есть 4 минуты для того, чтобы запустить программу и загрузить в систему ответ и код. Главное, на самом деле - ответ. После загрузки есть три вердикта:
- Rejected. Вы послали какую-то хрень. Ближайший аналог - PE. Например, не совпадает количество тестов. Эта посылка везде игнорируется. До окончания 4х минут Вы можете попробовать еще раз.
- Incorrect. На каком-то из тестов ответ неправильный. Таймер сбрасывается и, чтобы попробовать еще раз, надо брать еще одну попытку.
- Correct. На всех тестах ответ верный - Вы точно получили свои баллы за подзадачу. Всё, больше её посылать нельзя вообще - кнопка исчезает.
- Если вы не успели за 4 минуты получить свой Correct, считается, что Вы получили Incorrect. А если Вы получили за попытку Incorrect, то можно попробовать еще раз - 4 минуты пойдут заново, но Вам выдадут другой тест.
- Large input. Подзадачу можно посылать только после получения Correсt на Small input. Тут всё почти аналогично, но у вас есть только одна, и только одна 8-минутная попытка сдачи. При приёме в систему вы можете получить только Rejected (аналогичный предыдущему), либо Submitted - что означает, что претензий нет. Правильный ответ, или нет - Вы узнаете только по окончании тура. За эти 8 минут можно перепослать сколько угодно раз - засчитывается последняя посылка с вердиктом Submitted.
- Штрафное время. Считается как время последней посылки (по всем задачам), которая принесла Вам баллы (Correct на Small input или Submitted на Large input) плюс 4 минуты за каждый Incorrect в Small input (опять же, по всем задачам).
- Вопросы. Во время раунда можно задавать вопросы при помощи кнопки Ask a question под списком задач. Также можно, если Вы послали не тот код на Large input, попросить жюри перепослать (перепослать ответ невозможно, даже если попросить). Впрочем, подчеркивается, что не стоит злоупотреблять этой возможностью.
- FAQ.
- Квалификационный тур. В нём обязательно надо принять участие - задачки довольно простые. Собственно, без этого Вас не пустят дальше. Для прохода в Online Round 1 требуется набрать хотя бы 25 баллов (см. список заданных вопросов в контесте), что меньше, чем суммарный балл по всем Small Input. То есть Вы практически сразу знаете, прошли Вы, или нет.
Добрый вечер.
Пару дней назад опубликовал статью на Хабре про БПФ. Постарался объяснить и доказать всё без матриц (как на e-maxx), потому что не умею с ними еще работать на интуитивном уровне. Там точно также есть код и оптимизации (кстати, одной очень важной - прекалк корней, на e-maxx нет).
Если кому-нибудь помогло разобраться - буду рад.
Добрый вечер.
В связи с тем, что через некоторое время начинается квалификационный раунд Google CodeJam, хотелось бы прояснить несколько непоняток относительно правил.
Как я понял, каждая задача состоит из двух подзадача: Small Input и Large Input. Вторую можно решать только после первой. Каждая даёт сколько-то очков.
Для решения Small Input качаем тест (с этого момента пошёл 4-х минутный таймер), запускаем на нём наш код, отсылаем в систему сначала ответ (получаем сразу либо Rejected - ботву послали, либо Correct - всё ок, либо Incorrect - вывел неправильный ответ), потом код, который этот ответ сгенерировал. Если не получили Correct за 4 минуты, считается как Incorrect. После этого можно попробовать еще раз, но уже с другим тестом. Попыток много. Вопрос: сбрасывается ли после получения Incorrect таймер (т.е., можно ли исправить баг и послать другой ответ на тот же тест за эти 4 минуты)?.
Далее. Large Input. Тут у нас одна 8-и минутная попытка (опять качаем тест), решения получают Correct/Incorrect в конце контеста, Rejected - сразу. Считается последняя попытка, которая не-Rejected.
Участники ранжируются по сумме набранных баллов, при равенстве - по штрафному времени, которое равно "время последней Correct-посылки/не-Rejected посылки по Large input" плюс количество Incorrect попыток * 4.
И, да, в течение раунда можно попробовать обратиться к жюри, если послал не тот код на Large input. Ответ перепосылать нельзя. Также можно спрашивать по условиям при помощи "Ask question".
Вопрос два: всё ли я правильно понял?
В связи с тем, что через некоторое время начинается квалификационный раунд Google CodeJam, хотелось бы прояснить несколько непоняток относительно правил.
Как я понял, каждая задача состоит из двух подзадача: Small Input и Large Input. Вторую можно решать только после первой. Каждая даёт сколько-то очков.
Для решения Small Input качаем тест (с этого момента пошёл 4-х минутный таймер), запускаем на нём наш код, отсылаем в систему сначала ответ (получаем сразу либо Rejected - ботву послали, либо Correct - всё ок, либо Incorrect - вывел неправильный ответ), потом код, который этот ответ сгенерировал. Если не получили Correct за 4 минуты, считается как Incorrect. После этого можно попробовать еще раз, но уже с другим тестом. Попыток много. Вопрос: сбрасывается ли после получения Incorrect таймер (т.е., можно ли исправить баг и послать другой ответ на тот же тест за эти 4 минуты)?.
Далее. Large Input. Тут у нас одна 8-и минутная попытка (опять качаем тест), решения получают Correct/Incorrect в конце контеста, Rejected - сразу. Считается последняя попытка, которая не-Rejected.
Участники ранжируются по сумме набранных баллов, при равенстве - по штрафному времени, которое равно "время последней Correct-посылки/не-Rejected посылки по Large input" плюс количество Incorrect попыток * 4.
И, да, в течение раунда можно попробовать обратиться к жюри, если послал не тот код на Large input. Ответ перепосылать нельзя. Также можно спрашивать по условиям при помощи "Ask question".
Вопрос два: всё ли я правильно понял?
Вопрос: что есть сабж?
Откуда взял: книжка, которую наказали купить и составить по ней план теорподготовки к IOI.
Задача A. Игра в автобусе (автор - rng_58)
В этой задаче прекрасно работает симуляция "в лоб" - нам прямым текстом сказано, как ходят игроки. Лиса Кейл играет по следующей стратегии: если есть хотя бы две монеты по 100 йен и две монеты по 10 йен, она берёт их. Иначе, если есть хотя бы одна монета по 100 йен и 12 монет по 10 - она забирает их. В противном случае она берет 22 монеты по 10 йен. Если ей это не удаётся - выигрывает Ханако. Кролик поступает точно также, но в обратном порядке. Сложность решения - O(x+y).Задача B. Разноцветное поле (автор - ir5)
Решение, использующее массив NxM получает TL/ML, и, разумеется, мы не можем решать задачу "в лоб". Так как и запросов, и безжизненных клеток не более 1000, нам достаточно научиться отвечать на каждый запрос за время O(K).Пусть (a, b) - клетка из очередного запроса. Является ли она безжизненной, или нет - решит один цикл for по входным данным.
Итак, мы знаем, что на этой клетке что-то растёт. Пусть I - суммарное число клеток перед (a, b), а J - количество безжизненных клеток перед (a, b). Тогда ответ определяется значением (I-J) mod 3 (где 0 => "Carrots", 1 => "Kiwis", 2 => "Grapes"). Путем несложной математики можно понять, что I=(a-1)M+(b-1) (первое слагаемое - это количество клеток в предыдущих строках, а второе - количество предыдущих клеток в текущей строке), а величину J можно опять же подсчитать циклом for за O(K).
Получаем решение за O(TK), где T - количество запросов.
Задача C. Скучные строки (автор - ir5)
Мы можем представить каждую подстроку в s, совпадающую с какой-либо скучной строкой, как "запрещённый отрезок". Таких кандидатов в плохие отрезки для каждой из bi порядка O(n), поэтому мы можем подсчитать их все за O(|s|· n· |bi|) (да, тут не требуется никаких специальных алгоритмов, например, КМП).Теперь мы можем переписать задачу по-другому: дано не более 106 запрещенных отрезков, найти отрезок, который не содержит полностью ни один из запрещённых.
Давайте подсчитаем величину right[i] - минимальная правая граница среди запрещенных интервалов с левой границей в i. Если таких интервалов нет, положим right[i]=|s|.
Теперь давайте переберём начало ответа, начиная с |s| и до 0. Вначале ответ - пустая строка. Пусть ответ для предыдщего начала - подстрока с i+1 до j. Тогда, если right[i]>j, то мы можем спокойно приписать один символ слева и ответ увеличивается на 1 - подстрока с i до j. Если же right[i]<=j, то ответ не может быть дальше, чем до right[i]-1, в противном случае мы полностью покроем "плохой отрезок". Таким образом, мы пробежимся по всем возможным началам ответов за O(|s|).
Итого время работы - O(|s|· n· |bi|).
Задача D. Кодовый замок (автор - rng_58)
Давайте слегка переформулируем состояние замка: определим массив bi следующим образом: bi = 0, если панели i и i + 1 находятся в одинаковом состоянии и bi = 1 в противном случае. Положим, что панели 0 и n + 1 выключены (OFF). Если Кейл изменяет состояние панелей на отрезке с x до x+a-1 (включительно), то в массиве b изменяются значения bx и bx + a:
Задача D'.
У Вас есть массив bi. Не более 20 (=2k) элементов - единички. За каждый ход Вы можете изменить значения в bx и bx + a, где a - элемент ai и 0 ≤ x ≤ n - a. Определите минимальное количество ходов, требуемое для обнуления массива (мы просто "перевернули" порядок действий).
Понятно, что порядок ходов не важен. Также понятно, что если массив еще не обнулён, то есть такой индекс x, что bx = 1, и нам придётся походить, задев этот индекс, хотя бы один раз. Давайте следаем этот ход первым. Далее применим аналогичное рассуждение и получим, что на каждом ходу хотя бы одно из двух чисел bx и bx + a - единица.
Задача D''.
Теперь давайте построим граф с вершинами от 0 до n+1. Ребро между двумя вершинами v1 и v2 будет в том, и только том случае, если |v1 - v2| - элемент массива ai (то есть, мы можем сделать ход bv1 и bv2. Также изначально есть не более 20 фишек (стоят в позициях изначальных единиц в массиве bi). За один ход мы можем подвинуть фишку по какому-либо ребру. Если две фишки оказываются в одной вершине, они исчезают. Определить минимальное количество ходов, необходимое для избавления от всех фишек.
Для начала предподсчитаем попарные расстояния между всеми фишками. Это можно сделать, 20 раз запустив BFS. А далее имеем динамику по подмножествам: d[S] (где S - подмножество фишек) - минимальное количество шагов, чтобы убрать все фишки из S. Если S пусто, d[S=0]=0. Если S = {s0, s1, ..., sm - 1} непусто, то мы выбирае фишки, которая исчезнет вместе с нулевой, и делаем переход: d[S] = min(d[S\{s0, si}] + dist(s0, si)), где 1 ≤ i ≤ m - 1.
Итоговая сложность решения - O(knl + k· 22k).
Задача D'.
У Вас есть массив bi. Не более 20 (=2k) элементов - единички. За каждый ход Вы можете изменить значения в bx и bx + a, где a - элемент ai и 0 ≤ x ≤ n - a. Определите минимальное количество ходов, требуемое для обнуления массива (мы просто "перевернули" порядок действий).
Понятно, что порядок ходов не важен. Также понятно, что если массив еще не обнулён, то есть такой индекс x, что bx = 1, и нам придётся походить, задев этот индекс, хотя бы один раз. Давайте следаем этот ход первым. Далее применим аналогичное рассуждение и получим, что на каждом ходу хотя бы одно из двух чисел bx и bx + a - единица.
Задача D''.
Теперь давайте построим граф с вершинами от 0 до n+1. Ребро между двумя вершинами v1 и v2 будет в том, и только том случае, если |v1 - v2| - элемент массива ai (то есть, мы можем сделать ход bv1 и bv2. Также изначально есть не более 20 фишек (стоят в позициях изначальных единиц в массиве bi). За один ход мы можем подвинуть фишку по какому-либо ребру. Если две фишки оказываются в одной вершине, они исчезают. Определить минимальное количество ходов, необходимое для избавления от всех фишек.
Для начала предподсчитаем попарные расстояния между всеми фишками. Это можно сделать, 20 раз запустив BFS. А далее имеем динамику по подмножествам: d[S] (где S - подмножество фишек) - минимальное количество шагов, чтобы убрать все фишки из S. Если S пусто, d[S=0]=0. Если S = {s0, s1, ..., sm - 1} непусто, то мы выбирае фишки, которая исчезнет вместе с нулевой, и делаем переход: d[S] = min(d[S\{s0, si}] + dist(s0, si)), где 1 ≤ i ≤ m - 1.
Итоговая сложность решения - O(knl + k· 22k).
Добрый всем вечер, утро.
В ЛКШ в этом году появилось необычайно интересная мне параллель P - промышленное программирование. Как я понял по описанию на сайте в ней будет производиться "симуляция" работы команды в крупной компании со всеми вытекающими: svn, читабельный код, ООП, юнит-тесты и пр. плюшки. Собственно, мне бы очень хотелось туда поехать, потому как мне нравится писать код, который кому-то нужен дольше пяти часов.
Но вот проблема: эта параллель существует только в июльской смене (10-30 июля), а с 22-го по 29-е в Таиланде (соответственно, надо прибавить время на перелёт и акклиматизацию) происходит IOI.
Собственно, вопрос: знает ли кто-нибудь аналогичные по полезности мероприятия, куда теоретически могут взять школьника? Я слышал что-то про летнюю школу Яндекса, но ни гугление, ни яндексация, ни привели меня на какой-нибудь большой сайт.
Про Google Summer of Code слышал, но там ограничение по возрасту - 18+. В этом году уже участвовал в Google Code-in - похожее мероприятие, но для школьников (13+).
На Codeforces теперь используется новый WYSIWYG-редактор с поддержкой хоткеев. Поздравляю всех с этим знаменательным событием!
Спасибо, Штаб!
Спасибо, Штаб!
Задача A. Чат
Задача решается жадным алгоритмом. Сначала найдём в строке первую букву ('h"). Далее - найдём следующую после неё букву 'e'. Если мы таким образом нашли все буквы, то ответ, очевидно, YES. Теперь давайте докажем, что если ответ был, то он обязательно найдётся. В самом деле, пусть был какой-то ответ. Посмотрим на позицию буквы 'h'. Если мы её сдвинем до самой первой влево (той, которую найдёт жадник), то ничего не изменится. Аналогично поступим со второй и следующими буквами.
Получили жадный алгоритм, работающий за O(n), где n - длина входа.
Получили жадный алгоритм, работающий за O(n), где n - длина входа.
Задача B. Монеты
В этой задаче правильным решением опять же является жадный алгоритм. Выглядит он так: перебираем все числа от 2 и далее, пока стоимость последней добавленной монеты делится на него, делим, добавляем в ответ.
Доказать корректность можно, если посмотреть на стоимости монет в разложении на простые множители. В каждой следующей стоимости все простые входят в меньшей либо равной степени, нежели в текущей (это равносильно тому, что одно делится на другое). Также очевидно, что если суммарная степень уменьшилась хотя бы на два (например, было число a = x· y· z (где y, z > 1, а стало b = x, то можно добавить еще одну промежуточную стоимость a > c = x· y > b. Таким образом, в правильном ответе сумма степеней вхождений при переходе от стоимости к следующей и меньшей уменьшается каждый раз на один. Наш жадный алгоритм именно так и поступает.
Доказать корректность можно, если посмотреть на стоимости монет в разложении на простые множители. В каждой следующей стоимости все простые входят в меньшей либо равной степени, нежели в текущей (это равносильно тому, что одно делится на другое). Также очевидно, что если суммарная степень уменьшилась хотя бы на два (например, было число a = x· y· z (где y, z > 1, а стало b = x, то можно добавить еще одну промежуточную стоимость a > c = x· y > b. Таким образом, в правильном ответе сумма степеней вхождений при переходе от стоимости к следующей и меньшей уменьшается каждый раз на один. Наш жадный алгоритм именно так и поступает.
Задача C. Деревья
Первая мысль - красивая последовательность полностью задаётся любым своим членом. Следующая мысль: хотя бы одно дерево мы трогать не будем. Доказательство: скажем, что мы не трогаем первое дерево, а высоты остальных подгоним. Они, очевидно, все будут положительны.
Решение за квадрат: перебираем, какое дерево мы не трогаем, узнаём первый член последовательности, смотрим, сколько деревьев не совпало.
Это оптимизируется до решения за линию: если мы не трогаем какое-то дерево, то у нас фиксирован первый член последовательности. Давайте подсчитаем для каждого возможного первого члена, скольки деревьям он подходит. Это делается линейным проходом по всем деревьям и операцией "инкремент" на массиве. После чего осталось найти значение первого члена, которому удовлетворяет наибольшее количетсво деревьев, и вывести n - x, где x - это значение.
Решение за квадрат: перебираем, какое дерево мы не трогаем, узнаём первый член последовательности, смотрим, сколько деревьев не совпало.
Это оптимизируется до решения за линию: если мы не трогаем какое-то дерево, то у нас фиксирован первый член последовательности. Давайте подсчитаем для каждого возможного первого члена, скольки деревьям он подходит. Это делается линейным проходом по всем деревьям и операцией "инкремент" на массиве. После чего осталось найти значение первого члена, которому удовлетворяет наибольшее количетсво деревьев, и вывести n - x, где x - это значение.
Задача D. Календарь
Для начала заметим, что так как все строки календаря должны иметь одинаковую длину, то мы легко может эту длину найти. Это просто 
, где suml - суммарная длина всех строк. Теперь посмотрим на строку, которую поставим самой первой. Очевидно, выгодно брать строку, чтобы s + d было минимально (где s - наша строка, а d - дописываемый символ). Понятно, что такая найдётся однозначно, иначе получается, что две строки совпадают (так как символ d нигде не встречается). Разумеется, нельзя забывать, что зафиксировав первую строку, мы зафиксируем длину второй - надо, чтобы хотя бы одна была. Отлично, с первой строкой мы определились. Теперь мы знаем длину второй строки. Здесь нам надо взять просто минимальную строку соответствующей длины (одна префиксом другой быть не может - длины равны). Таким образом, заполняем календарь по линиям.
, где suml - суммарная длина всех строк. Теперь посмотрим на строку, которую поставим самой первой. Очевидно, выгодно брать строку, чтобы s + d было минимально (где s - наша строка, а d - дописываемый символ). Понятно, что такая найдётся однозначно, иначе получается, что две строки совпадают (так как символ d нигде не встречается). Разумеется, нельзя забывать, что зафиксировав первую строку, мы зафиксируем длину второй - надо, чтобы хотя бы одна была. Отлично, с первой строкой мы определились. Теперь мы знаем длину второй строки. Здесь нам надо взять просто минимальную строку соответствующей длины (одна префиксом другой быть не может - длины равны). Таким образом, заполняем календарь по линиям.Задача E. Выражение
Under construction. Основная идея - кубическая динамика с переходом за 102.
Прошёл пробный (да и первый тоже) туры XXXIII Всероссийской олимпиады школьников по информатике.
Результаты доступны на Google Spreadsheets. Добавьте свои! Внимательно читаем предупреждения сверху. Просьба не портить результаты и устраивать чат на других листах (либо в специализированном окошке от гугла - кто найдет, тот молодец).
Результаты доступны на Google Spreadsheets. Добавьте свои! Внимательно читаем предупреждения сверху. Просьба не портить результаты и устраивать чат на других листах (либо в специализированном окошке от гугла - кто найдет, тот молодец).
Добрый день.
Предположим, у нас есть такая задача: есть поле WxH, в некоторых клетах стоят стенки. Есть минимальный путь из верхнего левого угла в правый нижний и нужно что-то посчитать от этого пути.
Можно построить тест, на котором этот путь имеет длину порядка половины площади и идёт "змейкой".
Однако я слышал, что также можно построить тест, где этот путь будет иметь длину порядку 2/3 площади и этим люди челленжили какую-то задачу на TopCoder.
Кто-нибудь знает этот тест?
Предположим, у нас есть такая задача: есть поле WxH, в некоторых клетах стоят стенки. Есть минимальный путь из верхнего левого угла в правый нижний и нужно что-то посчитать от этого пути.
Можно построить тест, на котором этот путь имеет длину порядка половины площади и идёт "змейкой".
Однако я слышал, что также можно построить тест, где этот путь будет иметь длину порядку 2/3 площади и этим люди челленжили какую-то задачу на TopCoder.
Кто-нибудь знает этот тест?
Доброе утро.
Кто-нибудь знает алгоритм деления длинных чисел быстрее, чем за квадрат? Слышал, что это можно сделать при помощи преобразования Фурье (умножать им уже умею)
Кто-нибудь знает алгоритм деления длинных чисел быстрее, чем за квадрат? Слышал, что это можно сделать при помощи преобразования Фурье (умножать им уже умею)
Навеяно вот этим комментарием. У меня давно была такая идея: если разделяют рейтинг на Algorithm/Development/etc, почему бы не разделить вклад на Разборы+Идеи+Помощь/Шутки юмора?Просто мне самому кажется неправильным получать такие же кучи плюсов за шутки, как и за хорошие идеи.
Ваше мнение?
Ваше мнение?
Добрый вечер.
Смотрю разные проверяющие системы и наткнулся на dudge. Собственно, есть вопросы к тем, кто с ней работал:
Смотрю разные проверяющие системы и наткнулся на dudge. Собственно, есть вопросы к тем, кто с ней работал:
Так как ждать официальных резов всем, я думаю, лень, то можно заполнять свои результаты тут:
http://yeputons.net/wiki/COCI_2011_R4
Заодно можно и почитать коллективный разбор задач.
http://yeputons.net/wiki/COCI_2011_R4
Заодно можно и почитать коллективный разбор задач.
А когда нет - могу посмотреть, если введу codeforces.ru без www.
UPD. Fixed
После публикации моего предыдущего поста на эту тему я решил обобщить информацию, которую узнал.
Итак, на главной странице системы багрепортов GCC висит отличное сообщение: "Проблемы с числами с плавающей точкой - самый популярный небаг". Т.е. к этому надо быть готовым и исправлять это они не собираются.
Небаг заключается в некорректном преобразовании оптимизатором плавающих чисел. Точнее, не так, как это делает соппроцессор (иногда, впрочем, угадывает). Как от double к int, так и в обратную сторону.
В частности, код из предыдущего поста (компилировать с -O2) на некоторых версиях и машинах может вывести, что 20971519 == 20971520. Однако, если сделать EPS = 10-8, то лично у меня всё работает.
Ощущение, что оптимизатор что-то где-то всё-таки криво считает (например, во float).
Но всё же это надо учитывать. Я лично изменил свой любимый EPS. Жаль.
Итак, на главной странице системы багрепортов GCC висит отличное сообщение: "Проблемы с числами с плавающей точкой - самый популярный небаг". Т.е. к этому надо быть готовым и исправлять это они не собираются.
Небаг заключается в некорректном преобразовании оптимизатором плавающих чисел. Точнее, не так, как это делает соппроцессор (иногда, впрочем, угадывает). Как от double к int, так и в обратную сторону.
В частности, код из предыдущего поста (компилировать с -O2) на некоторых версиях и машинах может вывести, что 20971519 == 20971520. Однако, если сделать EPS = 10-8, то лично у меня всё работает.
Ощущение, что оптимизатор что-то где-то всё-таки криво считает (например, во float).
Но всё же это надо учитывать. Я лично изменил свой любимый EPS. Жаль.
Так как в последнее время я много пишу на Codeforces и контестов, и постов с комментариями, у меня появились некоторые предложения по улучшению WYSIWYG редактора.
Расставил в порядке уменьшения приоритета:
Расставил в порядке уменьшения приоритета:
- Хоткеи. Когда я пишу в Word/TinyMCE, я привык не пользоваться мышкой. Вообще. Я просто выделяю текст стрелочками и нажимаю Ctrl+B/Ctrl+I/Ctrl+U/Ctrl+S/... Получается гораздо быстрее. Тут пока таких хоткеев не замечено. (Firefox 3.6.13)
- Заголовки. В какой-то момент я случайно обнаружил, что иногда редактор заменяет текст "по центру" на красивый синий заголовок. Причём обнаруживается это только при предпросмотре или сохранении - в окне редактирования не видно. Также он делает когда хочет, а не когда нужно. Приходится лезть в HTML-код и самостоятельно добавлять class="header". А потом нажимать предпросмотр и убеждаться что всё хорошо.
- Редактирование HTML-кода. Когда я поступаю так, как написал выше, иногда забываю "свернуть" HTML обратно. В результате чего теряю изменения. Хорошо было бы не добавлять окошко с кодом рядом, а заменять им WYSIWYG. Или просто при нажатии на одну из кнопок "Отправить" показывать предупреждение, что остались несохранённые изменения HTML-кода.
- Списки выглядят по-разному. Ну, тут всё понятно. Ненумерованный список показывается с большими отступами в редакторе и без них - в предпросмотре.
- Подсветка синтаксиса. Когда требуется вставить большой кусок кода, я пользуюсь Pastebin. Но когда надо показать буквально 5-10 строк, это кажется излишним. Поэтому есть предложение сделать подсветку синтаксиса. Можно даже не в редакторе - это ИМХО трудно. Например, сделать еше один тег [code] впридачу к