24 декабря Архивач восстановлен после серьёзной аварии. К сожалению, значительная часть сохранённых изображений и видео была потеряна. Подробности случившегося. Мы призываем всех неравнодушных помочь нам с восстановлением утраченного контента!
Основные ресурсы с задачками: codeforces.com - Клевый проект, чуть ли не еженедельные контесты. Система писькомерства рейтинга уровня ELO с Короткевичем 4к+. Задачки своеобразные, пилятся комьюнити, мало общего с задачками стандартного ACM, что продиктовано форматом соревнований. Так же codeforces выбирают площадкой для множества престижных соревнований уровня VK Cup, в тренировки заливаются все крупные контесты оффлайн. acm.timus.ru - великолепный архив. Решишь 500 задач на тимусе - будешь гарантированно красным на кфе informatics.mccme.ru - хорош для новичков Дальше идут ресурсы, которые оп не юзал особенно по своему скудоумию: acmp.ru - ничего сказать пока не могу TopCoder.com - пендосский codeforces, регулярные контесты, открытые турниры и тому подобное e-olymp.com - не знаю
FAQ Что почитать? Грэхэм, Кнут, Паташник "Конкретная математика" Кормен "Алгоритмы. Построение и анализ"
Как вкатиться? Читай книжки сверху, и решай как можно больше ____________________
>>792140 [code lang="python3"]sum(sum(map(int, (c for c in str(x)))) == sum(map(int, (c for c in str(y)))) for x in range(100, 1000) for y in range(0, 1000))[/code]
>>792739 да вижу тут есть запускалка, потыкался, я так понял он в sdin пихает, а не в стартовые ключи - как я думал. хотя вроде логично, ведъ программа после ввода должна умереть?
>>792745 В стартовые ключи это как. Там есть задачи с мегабайтами инпута, ключами не обойдёшься. Твоя задача вывести правильный output и вернуть EXIT_SUCCESS. >>792801 Для интереса, это в основном хобби. Есть побочные профиты типа "в яндексе любят олимпиадников". Для школьников также помогает попасть на всякие бюджеты, ещё проводятся соревнования с неплохими призами, но это надо сильно угореть по теме.
>>792818 >Там есть задачи с мегабайтами инпута, ключами не обойдёшься. ну наверно тоже верно, но можно было файлами заделать - а то ведь скорость будет сильно зависеть от того как реализован инпут в языке - а оно очень разнородно.
>>792818 >хобби Таки да, если не дрочиться по 2-3 5-часовый тренировки в неделю чтобы стать чемпионом мира. Школьнику однозначно имеет смысл угореть, я сам жалею, что не хватало мотивации/не всегда мог себя заставить ботать в школьном возрасте, победителя всероса а не призера взял бы с легкостью. Все равно это лучше чем проебывать время на каэску какую-нибудь. Поступление в любой топовый универ халявное, опять же.
Студентам активно задрачивать смысла нет, если не целиться на финал АСМ. Но таки полезные эффекты в виде "быстро решать задачки на собеседовании в Yandex/Google" возникают. Ну еще, если не совсем донный, да и универ не совсем парашный, можно нахаляву за счет универа то есть ездить по всяким соревнованиям как и в пределах рашки, так и заграницу.
>>792838 Раньше делали с файлами, но постепенно от этой практики отказались, может быть чтобы полностью избавиться от еботни с правами доступа. Кроме того, тебе же удобнее, сколько WA было получено на неверном названии файла… Причём в некоторых случаях это оказывалось решающим фактором.
>>792879 А сейчас люди получают WA на том, что ОЙ А ТУТ ФАЙЛЫ НУЖНЫ. Или ОЙ Я ФАЙЛЫ НЕ ЗАКОММЕНТИЛ (хотя нормальные пацаны юзают препроцессор для этого). Хотя без файлов таки удобнее, да, жаль, что не везде так сейчас
>>792922 но вооще, где-нибудь в лине можно было бы перехватывать пару функций в libc и на любое имя файла давать один путь. наверняка и в винде такое можно провернуть.
сап, вопрос такой вот на соревах стоят ограничения по памяти но в jvm языках же сама jvm автоматом отжирает до пизды памяти получается jvm-блядки априори сразу сосут?
>>793026 Да. Алсо, ты ещё забыл про инициализацию машины, тоже время отжирает. Выбор языка в любом случае за тобой + ситуации, когда задача решается на С и не решается джавой, крайне редки.
>>793033 Это в случае, если ТЛ для Джавы стоит раза в 2 больше, что некоторые Online Judges делают по дефолту. А вообще зависит еще и от автора. Если он напишет какое-то заоптимизированное решение на плюсах и поставит жесткие ТЛи чтобы отсечь другое решение с чуть большей асимптотикой, то Джавакодеры соснут
>>793038 Иди сразу на кодфорсы, читай параллельно емакс, дорешивай задачи и читай разборы. Для начала сойдёт, когда дело дойдёт до уровня суфавтоматов, уже сам разберёшься, что делать.
Зачем нужно олимпиадное программирование, если все держится на библиотеках и фреймворках? Оно же абсолютно не нужно в реальном мире. Лучше потратить время не на подготовку и дрочку алгоритмов, а на прикладную разработку и на свой гитхаб.
>>792098 (OP) В спортзал и к стилистам всех четверых. Футболки блядь на халка, пошить соразмерные. Крайнему слева в жопе похудеть, перестать жрать говно, перейти на салатики и мясо. Бородачу как минимум выровнять бороду.
>>793047 друг, где читать разборы? я заходил на рашен кап чето там, но там объяснение мне показалось уже для чуваков которые прорешали пару десятков контестов
>>793056 На кодфорсах почти к каждому контесту пилят разбор авторы. Кроме этого, не стесняйся в случае чего спрашивать в комментах: пост вынесет на первое место в секции комменты, его увидят и ответят с вероятностью 99%.
>>793052 >абсолютно Радикально. В многих областях алгоритмы необходимы, пусть и не всем разработчикам.
>>793053 Котёнка лучше не трогать, где ещё такое встретишь, при том что он относительно молод.
>>793052 Писали же кучу раз Школьникам есть однозначные профиты которые не очень сложно получить, да и олимпиадки на таком уровне таки сильно влияют на прогерские навыки Студентам - хобби, помощь на собеседованиях. Да и полезно таки некоторые алгоритмы писать самому, чтобы понять как работает что-то. Опять же, навыки писать оптимальный код на плюсах
>>793060 Я не говорю про алгоритмы, они то очень нужны, я говорю про олимпиадную дрочку, которая вырабатывает плохой стиль кода (попробуй попиши читаемый код на время) и бесполезна в реальном мире.
Могу поспорить по следующим пунктам: 1. В целом развитие понимания, как всё работает, неасимптотическая оптимизация как, например, std::ios::sync_with_stdio 2. Навык дебага сложных конструкций. 3. Умение писать код быстро и правильно, то есть держать в голове много деталей
Отдельно скажу, что после многих лет олимпиад в проектах всё пишу максимально красиво, по другому уже и не хочется, но тут уже у всех своё. По крайней мере можно сказать, что само понимание красивого кода приходит после взаимодействия, а лучше написания некрасивого.
>>793658 Ну ты же наверняка понимаешь почему так, или есть хотя бы предположения. Просто не нравится? Вполне вероятно, что ты просто мало промышленно кодил, тогда это нормально. В олимпиадках ты ж тоже не сразу начал норм участвовать наприер
>>795402 Блять, ты тролль или ты серьезно? Пиздец просто, >на пушбэк поп Техника имени Семена, блять. Это как про любую задачу сказать "это задача на инт мейн", поеботень полная
>>795406 Тебе надо знать, что такое массивы, как считывать-выводить вещественные числа, и как извлекать корень. Первое - это лучше погугли и почитай в нормальном месте туториалы по языку, если таких основ не знаешь Второе - считывать так: double a; scanf("%lf", &a); и писать printf("%f", a) На самом деле, это верно для 11+ стандартов, в старых стандартах и читать и выводить с помощью %lf вроде Третье это #include <math.h> ... a = sqrt(23.9);
>>796352 Что такое бинарное дерево? Я не понимаю зачем обсираться в присядку, одновременно обмазываясь говном и дрочить на коколимпидаки и нахуй не нужные алгоритмы
>>796903 А нет его в памяти. Даже размер не известен. но в long long влазит. Выглядит как на той картинке. Наверно просто максимальный надо делить на 2 пока они не сравняются.
>>796352 1. В любом дереве маршрут всегда единственный, иначе бы там были циклы. 2. Задача сводится к нахождению наименьшего общего предка двух вершин, которую можно решить например алгоритмом Тарьяна.
>>796208 То, что все лошади одной масти, можно доказать индукцией по числу лошадей в определенном табуне. Вот так: „Если существует только одна лошадь, то она своей масти, так что база индукции тривиальна. Для индуктивного пере- перехода предположим, что существует п лошадей (с номерами от 1 до п). По индуктивному предположению лошади с номера- номерами от 1 до п — 1 одинаковой масти, и, аналогично, лошади с номерами от 2 до п имеют одинаковую масть. Но лошади по- посредине с номерами от 2 до п — 1 не могут изменять масть в зависимости от того, как они сгруппированы,—это лошади, а не хамелеоны. Поэтому в силу транзитивности лошади с номе- номерами от 1 до п также должны быть одинаковой масти. Таким образом, все п лошадей одинаковой масти. чтД* Есть ли ошибка в приведенном рассуждении и какая имен- именно?
>>795392 просто это математика, мне сложно, нужно по другому мыслить, немного перестроить голову.
>>797948 Граф ориентированный или нет? У тебя в коде он ориентированный, а в задаче как? Видимо, в ней он неориентированный, тогда надо делать adj_list[begin].push_back (make_pair(end, weigth)); adj_list[end].push_back (make_pair(begin, weigth)); У тебя нет второй строчки
>>797964 Неориентированный, и еще допустимы мультирёбра, но в тестовых данных для примера мультирёбер нет. Какие изменения в алгоритме надо сделать, чтобы обрабатывать мультиграфы?
>>797980 Нет, не надо. Лишние ребра тебе ничего плохого не делают: ты все равно в итоге выберешь из всех мультиребер ребро с наименьшим весом. В принципе, если их совсем много, то можно когда строишь граф, просто среди всех ребер, соединяющих одинаковые пары вершин, оставить только ребро с минимальным весом, но алгоритм будет работать корректно и без этого
>>797984 Ну например это может быть важно в случае, если человек юзает матрицу смежности вместо списка смежности хотя тогда бы по TL бы не прошло скорее всего. И, как правило, в задачах по умолчанию граф простой, поэтому выделение того, что есть кратные ребра, является некоторым правилом хорошего тона, можно сказать.
Посоны, смотрите. На двумерной плоскости имеем набор многоугольников с float координатами. Как определить, находится ли точка внутри какого-либо многоугольника?
>>798398 Да, вспоминаю про трассировку луча. Но тогда ведь нужно проверять каждую грань каждого многоугольника? Хотя можно применить небольшую оптимизацию и проверять только те многоугольники, с проекциями которых есть пересечения. Или еще лучше, с проекциями сторон которых есть пересечения. В общем, спасибо, навел на мысли.
>>798398 Проще, но на этот способ любят делать контртесты. Надёжнее пускать в рандомном направлении. >>798379 Я всегда использовал сумму полярных углов. Тема такая, для каждой грани ты считаешь, под каким ориентированным углом она видна из точки. Дальше считаешь сумму, если получилось 0, то ты снаружи, если 360 градусов – внутри. Случай на грани рассматривается отдельно. >>800440 Бывает, что ломают решения, которые не валятся на тестах. >>800574 Разбор появляется от сразу до нескольких дней, пали комменты к посту о контесте, там обычно спрашивают такие вещи.
>>797533 мне сложно, а вот если есть задача - я могу её решить, как там написано, и так же индукцией доказать - не проблема. но когда меня спрашивают, например докажите что в задаче на столбы, используются все возможные комбинации - вообще не ебу как. да, для меня очевидно, что вот число и его бит может иметь 3 значения, тогда число с n бит имеет 3^n-1 возможных комбинации - даже не представляю как это доказывают.
>>800960 > Почему 3, а не 2? потому что это из усложненной задачи 2. но я не проверял в ответахзаебало чувствовать себя говном
> Откуда -1? потому что ноль не учитываем - там задача сформулирована так, вродъ.
> А ты попробуй индукцией как? замкнутая форму уже есть, я её вывел из рекуррентной, опять же, из прошлой задачи. дальше то что?
> 2 Найдите кратчайшую последовательность перекладываний, перемещающих башню из n дисков с левого колышка А на правый колышек В, если прямой обмен дисками между А и В запрещен. (Каждое перекладывание должно производиться через средний колышек. Как обычно, больший диск нельзя класть на меньший.) > 3 Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения нам встретятся все допустимые варианты размещения n дисков на трех колышках.
>>800963 >как? замкнутая форму уже есть, я её вывел из рекуррентной, опять же, из прошлой задачи. дальше то что? в смысле, я человек тупой, не математик, и не имею этот склад ума, я так понял, что индукция способ доказать что замкнутая форма формулы верна - путём поставления её в рекуррентную.
>>792098 (OP) >Грэхэм, Кнут, Паташник "Конкретная математика" Этой книги достаточно, чтобы понимать анализ алгоритмов, всякие асимптоты и прочее из следующей книжки? Или придется до кучи ещё математики наверстать? Мой уровень если что на уровне девятиклассника, лол.
>>801308 Угу. А асимптотика там обсуждается аж в последней главе. Как я и думал, все эти алгоритмы и интеллектуальные игры с ними для элиты, которую с рождения обучают не тому, что дают в обычной быдло-школе. Пойду дальше в дотку катать.
>>801315 Просто начни с книжек попроще. "программирование: теоремы и задачи" Шеня, а потом вот это http://codeforces.com/blog/entry/12314 Ну и перед этим учебник школьный по математике, если совсем неуч.
>>800887 >Бывает, что ломают решения, которые не валятся на тестах. Ну вот. Ты меня запутал. Чётно обфусцирую решение на следующем контесте, а нечётно нет.
Есть ли простой алгоритм быстро возвести матрицу в квадрат? Вот две произвольные матрицы либо за эн в кубе умножать, либо хитрый алгоритм. А тут может попроще?
>>805626 Я понимаю, вот и говорю, что я, по крайней мере, никогда о таком частном случае ничего особенного не слышал. Пиши Штрассена или гугли научные статьи на эту тему.
>>792098 (OP) Рассказываю, почему я бросил олимпиадное программирование. Когда я начинал, то думал, что там задачи чисто на смекалку, для решения которых не требуется никаких предварительных знаний. Но это оказалось не так. Есть определенное количество узкоспециализированных тем, например, динамическое программирование или древовидные структуры данных, в которых надо быть хорошо прошаренным, чтобы решать олимпиадные задачи. Если кто не понял, что я сказал, приведу такой пример: если вы попытаетесь доказать хотя бы теорему Пифагора, ничего о геометрии не зная вообще, то у вас ничего не выйдет. Так вот я задумался однажды, стоит ли задрачиваться в темах, которые котируются на олимпиадном программировании, если они мне скорее всего не пригодятся в работе. Лучше уж потрачу это время на изучение чего-нибудь более практичного.
>>810133 Ты прав, в принципе, если не считать, что в некоторых местах типа яндекса и вк олимпиадников очень любят. Да и в целом на базовом уровне почти везде спрашивают, но базовый CS и так все должны знать просто по роду профессии.
>>810715 Тут замкнутый круг. В "базовый CS" входит комбинаторика, теория чисел, графы, динамическое программирование. Это активно используется на олимпиадах и во всяких гуглах. Но никак не изучается глубоко в вузах (кроме парфеновской кафедры и еще схожих) и не применяется в рф-it. Кроме сам знаешь где. Тоесть олимпиадное программирование, или тот же Скиена, это единственный способ рф-студенту окунуться в то "а что же там пишут в гуглах, что у нас нет". Да и без олимпиадной подготовки ты будешь о-о-чень долго вникать во всякие crack the coding interview и elements of programming interview.
>>813017 Вроде это не совсем то. Все точки должны быть задействованы. Я написал примитивный алгоритм: проходим по точкам, отсортированным убывающе по y, и соединяем ближайшие по x, но иногда он фейлится.
>>813104 Берёшь самую нижнюю-правую точку, ставишь её как начало координат. Считаешь полярные координаты остальных точек относительно центра. Сортируешь по углу, обходишь в этом порядке. Дядя Сэджвик с Курсэры так учил
>>813134 Я походу проще вариант нашел: пространство делится на 2 части по x (можно взять тупо width/2), слева и справа строятся ломаные кривые и потом соединяются.
>>813255 Все нормас, быстрейшее из всех, O(n). Проблема была только в разделении. Надо делить линией, которая проходит через самую верхнюю грань и через самую нижнюю. Теперь все без ошибок.
>>813300 Я думал о корректности. Из любого набора разных точек можно сделать ломанную линию с непересекающимися кусками, соединяя точки одна за другой в одном направлении. Пересечений гарантированно не будет, если между точками в этом направлении нет других точек. Мы получаем две ломанных линии, не пересекающиеся между собой. Вопрос только в том, можем ли мы безопасно соединить их концы. Ответ: да, т.к между концами больше нет других точек, т.к. мы заведомо взяли 2 верхние и 2 нижние точки и от каждой начали строить линию. И все же это не n, а nlogn, т.к. надо сначала отсортировать точки в одном направлении.
>>813319 Занятно, я всегда пользовался сортировкой по полярному углу. Сложность такая же, но алгоритм ка будто чуть попроще, нет двух частей, тупо сортировкой сразу достигаешь нужный порядок с другой стороны, может быть критична скорость работы с float
>>816923 А интегрирование аналитическое, без погрешностей. Хотя если оценить вид первообразной и по пределам оборвать, то можно свести все к вычислению 1109369452791600/20078358300
>>817083 Нет, все верно у меня. Главное не ошибиться с выбором лево-право у крайних отрезков. Я сначала выбирал тупо - если p1.x < p2.x, то p1 уходит влево, но это не всегда так. Пример на второй пикче.
>>815449 Понял твое решение, скорее всего, оно лучше. Хотел придумать корнер-кейс, но сам же на него ответил. При равенстве угла, если он [0; 90], то сортируем по Y возрастающе, если же больше, то убывающе.
>>818434 Допустим, мы проходим против часовой стрелки от нижней точки. Если мы сначала возьмем по убывающей, то получатся вершины 1-3-2, что уже ошибка, я это имел в виду.
Есть правильная скобочная последовательность и внутри неё есть мусорные данные. Для удобства есть ассоциативный массив в котором каждой зная координату одной скобки можно найти координату соответствующей ей скобки. Иногда нужно удалять мусорные данные. И когда это происходит, то размер строки и координаты некоторых скобок меняются, а ассоциативный массив нет. Как максимально быстро вернуть корректные значения в ассоциативный массив? Пример s="aa(bbcccb)" В массиве m лежат 2:7 и 9:-7. Это значит что скобке s[2] соответствует скобка s[2+7], а скобке s[9] скобка s[9-7]. Теперь если удалить все c, то получим s="aa(bbb)" И массив надо будет 2:4 и 6:-4. Скобок может быть больше поэтому на некоторые это удаление влияет, а на некоторые нет. Формат записи в ассоциативном массиве менять нельзя. т.к. это не совсем ассоциативный массив и в нём ещё хранится инфа по мусорным данным которые не совсем мусорные Нужно делать это максимально быстро. Память не жалко т.к. размер строки около 10к символов. А вот время нужно экономить т.к. важна каждая миллисекунда. Как решить?
>>822144 Что за "ассоциативный массив", он совсем медленный, или можно к нему обращаться лишний раз в процессе апдейта? Пока вижу так: держим массив с координатами всех скобок. Когда надо делать апдейт находим бинарным поиском первую скобку правее места удаления, и начиная с неё до конца массива фиксим каждую скобку. То есть: 1. Уменьшаем адрес каждой скобки на размер удалённого куска. Скорее всего это подразумевает удаление записи из ассоциативного массива, и добавление новой с другим ключом. 2. Если это закрывающая скобка, а соотв. открывающая левее точки удаления, то обновляем сдвиг в открывающей. 3. Уменьшаем адрес скобки в нашем вспомогательном массиве на размер удалённого куска.
>>822569 >он совсем медленный Совсем быстрый. За константу обращение. >бинарным поиском И как им искать скобки в не отсортированной строке? И работает это долго и не правильно. Вот тест ((abc)()) После удаления любой буквы скобки выделенные жирным трогать не надо. Пока думаю делать вспомогательный массив где отсортированы координаты всех закрывающихся скобок. Вот например тест "((a)b(c)d)" и удаляем b. В вспомогательном массиве будет 3 7 9. С помощью ассоциативного узнаём координату закрывающейся скобки и проверяем есть ли между ними удалёный элемент. Так должно быть быстрее, но после каждого удаления заново по массиву проходить не хочу, а как после всех удалений применить этот метод не знаю т.к. удалять можно несколько элементов подряд и их потом ещё запоминать придётся.
>>822144 Всё зависит от требований: много запросов – меняй за линию, это как угодно можно делать, быстрее за раз всё обновить нельзя, будешь на запросы за 1 отвечать. Много удалений, мало запросов – делай вспомогательный массив "текущей версии" для каждого индекса, и вспомогательное дерево типа дерева отрезков для "обновления" индексов за логарифм и взятия за логарифм (с дальнейшей записью в оригинальный массив и обновлением номера версии, чтобы между вырезаниями только один раз каждый индекс заново считать).
>>822710 А как сделать чтобы пока поступают запросы просто заменяешь символы на пробел, а потом за раз всё удаляешь и скобки корректируешь? Это быстрее всего должно работать. Запросы обычно не большие. Несколько байт. Но может много запросов на небольшой участок строки быть.
>>822616 >И как им искать скобки в не отсортированной строке? Для "((abc)())" массив индексов скобок будет [0, 1, 5, 6, 7, 8] как видишь он отсортирован.
>И работает это долго Удаление символа в середине строки это уже медленно.
>и не правильно >После удаления любой буквы скобки выделенные жирным трогать не надо. В ассоциативном массиве были записи 6:1 и 7:-1, а должны стать 5:1 и 6:-1, само по себе оно не обновится.
Анончики, может у кого есть нормально отформатированная Конкретная математика в mobi/epub или прочем ebook формате? Я искал, форматировал и все тщетно. А пдф читать на 6 дюймовом киндле не шибко удобно и приятно. Заранее спасибо за ответ.
Вчера писал свой первый раунд на Codeforces, почувствовал себя дауном. Первая задача простая, ну действительно, чего ее решать, давайте посмотрим остальные. Вторая про графы, чет как-то слишком длинное условие, сложна. Третья про пифагоровы тройки. И тут я засел. Родил какое-то стремное решение через числа Фибоначчи (спасибо Википедии за это), а оно зависает на всех нечетных, а на четных выдает не всегда верные ответы. В итоге два часа просидел над этой задачей, ничего не решил, а когда открыл разбор - охуел от простоты и изящества. Это лечится или мне навеки оставаться тупым?
>>824692 А у меня в С неправильное решение принялось. Должен быть TL, а оно принялось. Там я рассматриваю 2 случая: 1) a - катет. Тогда a^2 = (c - b)(c + b). Перебираем все делители числа a^2 (факторизуем a и умножаем все степени на 2; всего делителей будет не больше нескольких тысяч). Для каждого делителя d решаем в натуральных числах систему { c + b = d c - b = a^2/d } 2) Если a - гипотенуза, то я перебираю b от 1 и до тех пор пока b^2 < a^2, то есть там в цикле может быть 10^9 итераций. Почему у меня нет TL, я не понимаю.
>>824692 >>825960 > а когда открыл разбор - охуел от простоты и изящества. Какое изящество, тут просто надо знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает, это знают только всякие дрочилы, которые нарешивают олимпиады по математике для школьников.
>>826006 Не трать на это время, это полная хуйня. На cf есть нормальные задачи на какие-то определенные темы, решение которых помогает в понимании этих тем. То есть это задачи на какие-то алгоритмы или структуры данных, а не на знание того, что нечетное число можно представить в виде разности квадратов. Просто нужно уметь отличать хуету от нормальных задач.
>>826006 скиена "олимпиадные задачи по программированию"
>>824692 Я как-то хантился в майкрософт, к Дену Расковалову. https://www.linkedin.com/in/raskovalov/ru Он говорит, что только масштабы и время. Тоесть кодфорсес к собеседованиям мало отношения имеет. Так что чтобы решать олимпиады нужно быть задротом и дрочить много именно задачки. Там может быть ад на теорию чисел и комбинаторику. Как в прожект ейлера. После 300 задачек начнешь уже решать без задней мысли. А это полгода дрочильни где-то.
ХОДИШЬ ТАКОЙ НА ОЛИМПИАДЫ, БЕРЕШЬ ПРИЗОВЫЕ МЕСТА @ ПРИГЛАШАЮТ РАБОТАТЬ В ЯНДЕКС @ ПОСЛЕ НАПИСАННОГО ТОБОЙ ОБНОВЛЕНИЯ У ВИНДОВС ПОЛЬЗОВАТЕЛЕЙ СЛЕТАЕТ ВИНДОВС СО ВСЕМ СОДЕРЖИМЫМ ДИСКА Ц @ С ПОЗОРОМ УВОЛЬНЯЮТ @ КАРЬЕРА В ИТ ДЛЯ ТЕБЯ ЗАКОНЧЕНА, ПИЗДУЕШЬ РАБОТАТЬ ДВОРНИКОМ
>>827819 @ НЕ ОСТАЕТСЯ НИЧЕГО ДРУГОГО, КАК СТАТЬ НАЕМНЫМ УБИЙЦЕЙ ЗА ДОЗУ ГЕРОИНА @ ЦЕЛЬ ИЗЛЕЧИВАЕТСЯ ОТ БОЛЕЗНЕЙ ПОД ТВОИМИ УДАРАМИ @ ВЫГОНЯЮТ БЕЗ ПЕНСИИ
На джаве кто-нибудь пишет? Поможете сопитимизировать? У меня TL. http://codeforces.com/contest/709/problem/E http://pastebin.com/pW573vzV Время работы там O(n), в этом точно косяка нет. Я заменил рекурсию на while + stack, потому что до этого был stack overflow. То что инпут с помощью Scanner - это норм, потому что если бы инпут не успевал, у меня бы не доходило до stack overflow в первой версии. От лямбд я уже пробовал избавляться, тоже TL.
>>829616 Помог, где-то на полторы секунды быстрее стало, но этого было недостаточно. > Какая выгода от BufferedOutputStream? В этой задаче аутпут 400000 и выводится по 1 символу, а это очень долго. А buffered сначала ниче не выводит, а когда делаешь flush, выводит все сразу.
>>825975 >знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает Если ты не знаешь, что комбинаторный интеграл от 2n+1 равен n(n-1)+n, что ты вообще делаешь в этом треде?
Это шутка была (про то, что все знают, что такое комбинаторный интеграл). Но то, что (n+1)^2 = n^2 + (2n+1) знают все, а если человек так давно раскрывал такие скобки, то хули он делает в олимпиадном программировании.
А комбинаторный интеграл это понятие тесно связанное с комбинаторной производной. Комбинаторная производная определяется так: d(F(n)) = F(n+1) - F(n) Видим, например, что к.п. от 2^n равна 2^(n+1)-2^n = 2^n, то есть 2^n выступает здесь в роли e^x. Похожие правила работают и для полиномов. d(n^2) = (n+1)^2 - n^2 = 2n+1, не очень приятное выражение получается. Но если вместо обычных полиномов использовать полиномы вида n^(k_) = n(n-1)(n-2)(n-3)...(n - k + 1) то к.п. берётся проще: d(n^(k_)) = k n^((k-1)_) Например: d(n(n-1)) = (n+1)n - n(n-1) = 2n Тут есть ещё много разных вариаций, которые можно вывести, например, d(f(n) g(n)) = f(n) d(g(n)) +d(f(n)) g(n + 1) = f(n+1) d(g(n)) + d(f(n)) g(n) выглядит почти как правило умножения для производных.
Польза от такой производной в том, что можно взять от неё комбинаторный интеграл. То есть по функции f(n) найти функцию F(n), такую, что F(n+1) - F(n) = f(n) Зачем нужна эта штука? Допустим, мы хотим найти сумму f(1) + f(2) + ... + f(k), для этого можно переписать эту сумму как (F(2) - F(1)) + (F(3) - F(2) + ... + (F(k + 1) - F(k)) = F(k+1) - F(1) Магия - мы научились сворачивать ряды в closed-form формулу. Пример: найти сумму 1 + 2 + 3 + ... + n К.и. от n равняется n(n-1) / 2, значит ответ - (n+1)*n / 2 - 0 = (n+1)n/2 Пример 2: найти сумму 1^2 + 2^2 + 3^2 + ... + n^2 Чтобы проинтегрировать n^2 нужно сначала представить его в базисе n^(k_), а именно: n^2 = n^2_ + n, легко проверить: n^2 = n(n-1) + n = n^2 Берём интеграл от n^2_ + n, он равен n^3_ / 3 + n^2_ / 2 Раскрываем скобки: n(n-1)( (n - 2) / 3 + 1/2 ) = n(n-1)(2n - 1)/6 Подставляем границы, ответ равен (n+1)n(2n+1)/6 - 0 Подставляя n=2 и n=3 убеждаемся, что мы нигде не ошиблись.
Если интересно, можете таким способом найти сумму k 2^k для k=1...n Подсказка: интегрирование по частям.
Циановый даун с кодефорсеса цвета морской волны ищет боевого товарища, чтобы в соревновательно-помогательном режиме ботать прогу. По заявкам оставляю фейко-контакты
Самолет взлетает в X (целое, 0<=X<=23) часов по местному времени в часовом поясе номер M (целое, 0<=M<=23). После полета в течение K (целое, 1<=K<=12) часов он приземляется в часовом поясе номер N (целое, 0<=N<=23). Определите местное время в пункте приземления. Считать, что часовые пояса нумеруются с запада на восток.
Тупая задачка. Почему нельзя просто прибавить ко времени старта врем полета, а потом прибавить разность номеров часовых поясов?
>>834027 А кто тебе сказал, что нельзя? Летал самолет или нет, значения не имеет, от этого разница во времени между часовыми поясами не изменится. Здесь просто спрашивается, какое время будет в другом часовом поясе через n-цать часов. И какое все это имеет отношение к погромированию?
Эй, умники. Есть задачка. У нас имеется n целых неотрицательных чисел, чья сумма не превосходит 10^5. Еще есть некое m до 10^4. Все эти n чисел мы хотим представить в виде целых долей этого числа m, причем нецелые доли мы вольны округлять в любую сторону по желанию левой пятки. Я тут набросал тупой жадник, который, конечно же, доказывать не умею, и он отхватывает wa2. Жадник настолько тупой, что он все округляет вверх, а потом, переокругляет вниз пока не получим нужную сумму, равную m http://ideone.com/3x53a2
>>835570 Дай ссылку на исходную задачу, потому что ты во-первых написал условие как мудак (блядь, неужели нельзя скриншот запостить хотя бы, и пару примером входа выхода), а во-вторых лучше засабмитить, чем какому-то петуху объяснять.
>>836283 Хотя тут даже динамика не нужна, жадный алгоритм должен работать. У тебя, наверное, просто не проверяется, что если число нацело делится, то его двигать нельзя уже.
Ну динамика, если интересно, такая: f(arr[i:], amount) - можно ли набрать amount сумму, округляя как-нибудь числа начиная с i-й позиции, как в рюкзаке, и по времени проходит - 50е6. Только, повторяюсь, она тут не нужна.
Олимпач, я тебе задачу подвез. Пока из идей посортить стержни по максимальному расстоянию от конца до точки d, а потом как-то хитро посчитать. Хитро что-то не выдумывается
>>843105 Допустим все числа нечетные, тогда просто расположим их так, чтобы их середины находились на оси x и будем зажигать от самого длинного к самому короткому. Допустим, нечетные, тогда то же самое. Допустим есть четные и нечетные числа. Например, 2 стержня 4 и 5. Тогда придётся все числа той же четности, что и максимальное, зажечь с одного конца, чтобы сделать всех одной четности, а потом применить алгоритм из первого параграфа.
Короче зажигаешь самый длинный стержень с двух сторон, а дальше изъебывайся как хочешь, но чтоб все в один момент лопнули. Это можно сделать. В первую секунду зажигаешь самый длинный стержень с двух сторон, а стержни длины на 1 меньше - с одной стороны, во вторую секунду все стержни которые горят с одной стороны поджигаешь со второй, а все стержни на 1 меньше - с одной стороны. И так далее.
Я умею искать гамильтонов путь в неорграфе динамикой по подмножествам, где вершин не больше 20. А вот теперь мне надо проверить наличие гамильтонова пути в ацикличном орграфе с количеством вершин вплоть до 10^5. Вроде простая задача должна быть. Думаю пока в сторону топсорта какого-то
>>846398 >>846526 Честно говоря не понимаю зачем пишут топсорт делать. Наверное чтобы достичь O(N) вместо O(N*log(n)). По идее достаточно для каждой вершины предрасчитать списки входящих соседей (если вершин с пустым списком >1, то гамильтонова пути сразу нет), а потом пока есть нерассмотренные вершины берёшь рандомную считаешь расстояние от истока до этой вершины как максимум среди её входящих соседей+1. Применяешь алгоритм рекурсивно, не забывая про мемоизацию. Короче как поиск кратчайшего, только длиннейшего.
>>846526 Да, спасибо. Я пытался делать дфс, который брейкается, когда глубина рекурсии становится равна количеству вершин. Но как-то это получало ва5. >>846535 Ты же понимаешь, что твои идеи на порядок сложнее и для осознания, и для написания. Топсорт - это одна строчка в дфсе
Окей. Как быстро проверять достижимость каждой вершины из каждой по матрице достижимости? Вершин всего тысяча, но флойд не вариант, потому что там сверху еще будет логн от бинпоиска висеть. Граф плотный, поэтому бфс меня тоже смущает. Или нормально?
Нужны две функции. Одна принимает английский неправильный глагол, а возвращает его первую форму, а вторая получает рандомное слово и составляет кучу других слов из таких-же букв. Какие есть способы это сделать быстро?
Что, как поживаете? Я вот тут недавно школьную командную олимпиадку писал. Суть в том, что я-то алгоритмов довольно много знаю, могу написать. Префикс, з функции, декартачи, до, всякие графы, хэши. Но, сука, проблема в том, что в команде я ничего не придумывал. Мне говорили: "пиши топсорт, потом проверяй наличие соседних ребер". Или: "Склей строчки, посчитай префикс функцию, пока суффикс совпадает с префиксом, удаляй их. Я, бля, даже условия оригинального не знаю. Это все круто, но на личной олимпиаде не проканает. Неумение быстро выдумывать решения - это приговор? Или еще есть шанс до феврали задрочить задачки из первой полутысячи тимуса?
Есть программа с кучей функций. У каждой функции есть название. Известно количество обращений к каждой функции за последнее время. Надо назначить функциям однобуквенные хоткеи так, чтобы сумма чисел обращений к функциям, которым назначены хоткеи, была максимальна. Хоткеем функции можно назначить только букву, входяшую в её название. Знаю про венгерский алгоритм, но у меня вес дуги из функции в каждую из допустимых клавиш одинаков. Есть ли что-то быстрее для такого случая?
>>864307 не все такие умные и не все так рано начинали, мне вот 30 лет и на тимусе у меня 50 задач, в школе был далек от программистов, даже не знал об этом, но как сейчас выяснилось тогда по матеше я обходил парней ныне уже участников финала мира acm icpc
Пишу алгоритм для игры. В ней нужно набрать максимум очков. Их количество не может уменьшаться. Есть фактор случайности. игра похожа на монополию и количество возможных исходов одного хода меньше чем у шахмат При этом игра может закончиться совсем неожиданно если неколько ходов подряд кубик будет плохо падать. Значит обычный minmax не подойдёт т.к. при большой глубине поиска лучший из худших всегда будет проигрыш. И что делать с линией горизонта? Ведь здесь нельзя форсировать поиск при шахе как в махматах. Реквестирую литературу про программирование ии для игр с влиянием рандома.
>>865189 >обычный minmax не подойдёт т.к. при большой глубине поиска лучший из худших всегда будет проигрыш Не понял проблему. Оцениваешь все исходы броска кубика, и считаешь матожидание оценок. Или не просто матожидание, а матожидание от некоторой функции, учитывающей твоё отношение к риску. Например если надо срочно догонять противника имеет смысл оценивать нулём исходы, которые не дают тебе достаточно очков.
>похожа на монополию Пиши эвристический алгоритм. Если хочешь можно ещё сделать обход дерева ограниченной глубины, а по достижении дна считать оценку. Эвристикой опять же. Альтернативно можно использовать метод Монте-Карло. Берёшь начальное положение и много-много раз отыгрываешь его до конца каким-то простым алгоритмом за обоих игроков, а потом по результатам отыгрышей даёшь оценку положению. Но мне кажется эвристика будет точнее.
>>865292 > обход дерева ограниченной глубины, а по достижении дна считать оценку Так и хочу. Но уже на небольшой глубине можно получить большую оценку, но это будет проигрыш и конец игры. Если в одну и ту же сторону идти, то скоро проиграешь. А в алгоритме перебираются все возможные направления и все возможные броски кубика. Потом смотриться на конкретную глубину и выбираеться тот ход минималиный профит от которого самый большой. Что делать с этими проигрышными тупиками? И исходники читать не интересно. Хоть статьи скинь.
>>865330 >получить большую оценку, но это будет проигрыш и конец игры Оценка не обязательно равна количеству очков. Это может быть и разность очков у тебя и противника, и сложная функция, учитывающая ещё и ситуацию на доске. Никто не запрещает тебе назначать проигрышам оценку 0.
>>865348 Так может быть так что все ходы проигрышные. Надо что-то выбрать из тех нулей. Может их в 2 очереди проверять? А с горизонтом что делать? Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный. А алгоритм только на 5 вглубь смотрит и войдёт в проинрышную ветку из которой не выйти.
>>865385 >Так может быть так что все ходы проигрышные. Надо что-то выбрать из тех нулей. Если у всех стратегий одинаковая оценка, то выбираешь рандомно.
>А с горизонтом что делать? Ну блин, делай как в шахматах делают. По достижении дна оценивай положение на доске эвристикой. В шахматах фигурам назначают цену, цены имеющихся фигур складывают, и ещё как-то расположение учитывают, хз как. Так получают примерную оценку для позиций на дне. Тебе тоже надо придумать эвристику для оценки позиции. Как это сделать я подсказать не могу, тут надо пробовать варианты и проявлять изобретательность. Попробуй решить https://projecteuler.net/problem=84 может придумаешь как прикрутить себе сети Маркова.
>Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный. В настолке с кубиком такое нереально. Там слишком много рандома. По этой же причине нет смысла делать сложный алгоритм - разница в уровне игры по сравнению с тривиальным "покупай всё что можешь" будет практически незаметна человеку.
>>867885 Мне это напомнило задачу с прошлогоднего полуфинала или даже финала. Копни в эту сторону Насколько я помню, там отчасти рандомизированный алгоритм. Сперва что-то поспрашивать, а потом решать.
Стандартная задачка егэ: Из ряда натуральных чисел выбрать произвольное количество чисел так, чтобы их сумма не делилась на 6. При этом сумму надо максимизировать. На выход количество выбранных чисел и их сумму. Я не совсем ньюфаг в олимпиадном программировании, но тут встал в тупик. А егэ сдавать надо
>>875369 Я понял задачу так, что обязательно использовать ровно r+1 запрос. В таком случае возникает проблема, что на каком-то шаге мы можем обнаружить расхождение, но мы обязаны сделать остальные шаги, и непонятно как передать на эти шаги информацию о том, что различия уже найдены.
Может тут есть кто-нибудь, кто тоже участвует во всероссийской олимпиаде для 11 классов? Сейчас пробный тур проходит как раз. И еще может кто-нибуд в технокубке участвовал? Какого уровня там задачи? Там вообще ебанутые какие-то правила с этими взломами, не знаю осилю ли я там хороший результат показать.
>>875793 Ну, участвовал в твоем технокубке. Из-за того, что не в том порядке стал решать задачи, занял не 70-какое-то, а 150 с хуем место. Не понравилось
>>877675 >среди работ с дедлайном >= i. А если таких нет, то ничего не назначать, а потом делать дополнительный проход, заполняя дни без назначений? И как находить такие дни - поддерживать отсортированную по штрафу коллекцию, и в неё докидывать работы из заранее подготовленного списка работ, сгруппированных по дедлайну?
Мне кажется проще назначать день работе с наибольшим штрафом. Если есть свободные дни до дедлайна, то забираем последний. Иначе забираем последний из дней после дедлайна.
Какую теорию погуглить для олимпиадного программирования? Я просто совсем неадвно вкатился и пока что просто на логике всё делаю. Жадные алгоритмы, динамическое алгоритмы, что ещё?
>>877910 Способы представления графов в памяти, DFS/BFS, алгоритм Дейкстры, комбинаторика на уровне итерации по всем перестановкам и сочетаниям, бинарный поиск, алгоритм Эвклида, решето Эратосфена, генерация пифагоровых троек, метод ветвей и границ. На самом деле сам поймёшь что нужно когда будешь натыкатьсся на трудные задачи.
Как научиьься реализовывать алгоритмы? Смотрю в интернете всякие видео уроки по популярным алгоритмам, типа quicksort, но реализовать на языке который изучаю не могу. Сто делать?
>>877991 Как научиьься выступать в суде защитником в деле об ебле козы бабы Нюры? Смотрю в интернете всякие видео уроки по выступлениям-заседаниям, типа quicksort, но выступить в суде в котором выступаю не могу. Сто делать?
>>877991 Находишь в интернете реализацию ксорта на твоем языке. Понимаешь. Потом переписываешь, можно подглядывать. Как переписал, закрываешь. На следующий день без подглядывания пиши.
>>877675 > Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i. И какая у этого алгоритмическая сложность? По-моему, не меньше O(N^2). Многовато.
Есть таблица связей в бд (postgres): юзер id - группа id. Нужно выделить несколько секций юзеров (нужно, чтобы было максимум N юзеров в каждой такой секции), которые входят в группы "эксклюзивно". Другими словами. Допустим N=1000. В секции #1 будет 10 групп, в которые входят только юзеры из этой секции, всего 980 юзеров в секции #1. В секции #2 будет 14 групп, в которые входят только юзеры из секции #2, всего 900 юзеров в этой секции. Всех остальных относим в последнюю секцию. Нужно найти такие вот секции, приблизительно.
Какой тут алгоритм применять? Главное чтобы быстрее работало, какая-то точность разбития на секции (типа, чтобы максимально скомпоновать юзеров по N=1000 в секции) не нужна. Пока вижу просто тупо ходить в цикле по группам (в порядке возрастания популярности групп, навеhное), собирать юзеров, пока не наберется 1000, после чего собирать следующую.
>>881503 >не зная как распределены пользователи по группам Как угодно, считай, это группы в вк. >"приблизительно" Я имел, ввиду, что не хочу найти лучшее решение из возможных (где секции максимально укомплектованы - по 999, 998 юзеров, например, в каждой), а более быстрое (то есть, пусть там в каждой секции будет по 900-1000 юзеров, это ок). >"эксклюзивно" Это я просто так назвал, не знаю как правильно. Смысл - в каждой секции должны быть группы, в которые входят только юзеры из этой секции, не пересекаясь с другими секциями.
Как я уже написал, группы - это как группы в вк. То есть, например, соберу секцию #1, где будет группа любителей хентая 500чел + группа любителей гуро 400чел (из них 100, например, входят в группу хентая) + группа любителей golang 10чел. В других секциях любителей хентая, гуро и golang быть не должно. И т.д. Большие группы, типа мдк, где >1000чел, не входят в секции. Но их подписчики могут быть любителями хентая, гуро, golang.
Сап. Я школьник, 10 класс. Алгоритмы знаю на уровне "quick sort, binary search, bfs, dfs, dijkstra". Такой вопрос - можно ли за год вкатиться в олимпиады так, чтобы получить хоть какие-то бонусы для поступления? И на что следует обратить внимание? Готов сидеть у книжек часами каждый день. Если что, пишу на плюсах.
>>792098 (OP) >codeforces.com >acm.timus.ru >informatics.mccme.ru >acmp.ru >TopCoder.com >etc Скажите, а есть возможность на каком-нибудь из этих ресурсах сдавать задания на питоне?
>>881518 > Как я уже написал, группы - это как группы в вк. То есть, например, соберу секцию #1, где будет группа любителей хентая 500чел + группа любителей гуро 400чел (из них 100, например, входят в группу хентая) + группа любителей golang 10чел. В других секциях любителей хентая, гуро и golang быть не должно. > И т.д. Большие группы, типа мдк, где >1000чел, не входят в секции. Но их подписчики могут быть любителями хентая, гуро, golang.
Ну что же вы, бэтманы? Я думал, в треде есть бородатые гики, что пояснят по хардкору, какой мне алгоритм нужен.
>>882755 Сколько групп всего? Если не больше нескольких тысяч, то можно представить их в виде графа, в котором две вершины соединены если в соотв. группах нет общих членов. Перебираешь в нём клики Броном-Кербошем, и когда находишь подходящую удаляешь её из графа. В принципе может и не обязательно хранить граф в явном виде, в конце концов проверить наличие дуги между группами можно глянув на пользователей.
Но лучше делай как я уже написал >>881503 >Выбирай очередную группу рандомом пока не наберёшь достаточно, делай несколько подходов, выбирай лучший результат. Можешь ещё отранжировать группы по аутичности, то есть отношению количества пользователей группы к количеству других групп в которых они состоят (или суммарному количеству пользователей в которых они состоят). Начинать наполнение секции лучше с аутистов.
Вангую что результаты тебя огорчат из-за того что есть боты, вступающие в дохуярд групп.
>>881549 Я вот вообще не пробовал олимпиадное программирование раньше, но опыта в пограммировании каких-то практических вещей и всякой хуйни у меня куча. И вот в этом году я неплохо так начал в него вкатываться. 11-класс
Анончики, не нашел ваш тред на нулевой и поднимаю этот, вроде бы актуальный. Интересует решение задания "743D - Хлоя и приятные подарки" на codefoces Разбор здесь http://codeforces.com/blog/entry/49049 , но я в упор не понимаю, как его реализовать. Кому не лень и кто шарит, можете разжевать идиоту.
>>895409 >я в упор не понимаю, как его реализовать Там же решение на С++. Да и рекурсивное решение тупое как с перестановками: Вывести все перестановки N чисел. Перестановка N чисел - это перестановка первого числа и последовательности N-1. И так повторять пока N не будет равно 2, а два элемента переставить может даже школьник.
>>895494 >решение тупое >Вывести все перестановки N чисел. На минуточку N до 2*10^5. Вот если ты вообще не в теме, но нахуя лезть в каждую бочку затычкой?
>>895517 На минуточку ты долбаеб, а первоначальная задача легко решается рекуррентно за n операций. Я же привел задачу намного сложнее, которая тоже легко решается похожим образом. Толку в этих задачах все равно 0, а автора кода надо бить палкой по голове за такой код
>>897953 Тогда у тебя дохуя мотивации. От халявного поступления в вуз и повышенной стипухи, до чемпионата мира в пендосии. Открыл книгу и начал читать, нахуй
>>898360 ну тут сразу понятно что вершины надо не удалять, а добавлять в обратном порядке. дальше очевидный флойд уоршел получается 500^3, норм тебе? только смотри не объебись - в двух внутренних циклах надо итерироваться по всем вершинам, а не только по добавленным.
>>898775 >получается 500^3, норм тебе? >только смотри не объебись - в двух внутренних циклах надо итерироваться по всем вершинам, а не только по добавленным. >>898775 Спасибо большое.
>>903807 Буду краток. знаешь, буквально на днях я был в Российской Академии Наук, провёл беседу со многими учёными, в том числе молодыми, кстати, очень грамотные ребята. Так вот мы обсудили, в частности и данную проблему, поговорили о текущей экономической обстановке в стране; они так же рассказали о своих планах на будущее. Вкратце, ответ на твой вопрос такой: эти ребята довольно быстро решают задачи, что позволяет им придумать алгоритм и написать код для задач всего раунда всего за два часа.
> Покажите, что алгоритм, который содержит не больше некоторого по- > постоянного количества вызовов процедуры с полиномиальным временем > работы, сам работает полиномиальное время. Если же алгоритм делает > полиномиальное число вызовов такой процедуры, то общее время работы > может быть экспоненциальным.
Посоны, откуда здесь экспоненциальное время выполнения?
>>905527 Спасибо. Только легче не стало. Может я неправильно понимаю эту задачу? Ну подставили мы в x^10 значение x=n^20, получили n^200, экспонента никак не получается.
>>906581 Тут не нужны никакие графы и поиски кратчайших путей. Это задача для 6ого класса. Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу. Код на богоподобной Яве по ссылке. http://ideone.com/34HGKf
>>906612 >Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу Частный случай поиска кратчайшего пути, вариант реализации с бинарным графом.
>>906628 Так то да, но тут время О(n) и памяти O(1), а у Дейкстры? Впрочем можешь не отвечать. Просто покажи реализацию, лучше всего на фибоначчевой куче, тебе явно это раз плюнуть, делов на 5 минут. А мне интересно.
>>906612 >Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу Так мой код тоже самое и делает, нет? Конечно, там есть дохуя костылей, но всё же.
>>906661 Прости, но твой код написан так, что его даже читать не хочется. В нем нем ясной выраженной мысли. Зачем ты проверяешь следующий символ в строке? Зачем тебе переменная up? И где у тебя хранится минимум переправ до текущей точки (и правого и левого) берега реки?
>>906673 >Зачем ты проверяешь следующий символ в строке? Для логичности, если сверху слева, конечно, но по картинке как будто сверху(т.е переменная up=1, а если снизу справа, ага, то соответственно up=0) идут два подряд (этот символ и следующий -- LL) притока, то выгоднее будет переправиться вниз, где таких притоков нет. Если сверху идёт лишь один приток, а второй снизу (LR), то выгоднее будет переправиться дальше вправо, чем переправиться вниз, а потом снова вверх. >И где у тебя хранится минимум переправ до текущей точки (и правого и левого) берега реки? Собственно, в переменной p, которая и выводится в конце. Правда, там по-другому описано, и нет отдельно левого и правого берега.
Я неофит просто, в этом году едва в регионалку по всеросу не попал.
>>906702 Действительно, у меня при притоках по всем сторонам (B) он поворачивает, хотя это совсем не обязательно. Спасибо, спустя ещё несколько костылей будут все сто баллов, а так пока что 60.
>>906723 Анончик, не делай так. Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед. Посмотри выше решение готовое. И просто разберись почему оно работает. В нем мы идем, как будто по обеим сторонам реки одновременно.
>>906758 >Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед Но почему? Извини, понять не могу. >И просто разберись почему оно работает. Хотелось бы всё же допилить своё решение, а если совсем не выйдет -- разобраться в чужих.
>>906643 Ну не на пять минут, но мне тоже интересно. Мои соображения: - в каждой точке графа у нас есть два возможных пути - выбирая каждый раз пусть с меньшим весом, вы в итоге получим кратчайший (в волновом алгоритме всегда обсчитываем только одну ветку) - переход протоки на стороне, где сейчас игрок, стоит 1 - переход на другую сторону учитывается вместе с переходом протоки на другой стороне (то есть результирующий вес на этом шаге либо 0, либо 2) Память не нужна, сложность O(n).
Хуй знает, где такое спрашивать, так что спрошу тут пожалуй, это лучше, чем ньюфаг-тред. Есть алгоритм Кнута-Морриса-Пратта. Можно ли им сделать поиск подстроки, если в заданной для поиска подстроке допустим символ, который бы допускал, что на его месте может быть любая другая подстрока?
Что почитать школьнику нужно больше примеров, чтобы научиться решать задачи на динамическое программирование? А как решать задачи на графы, про всякие j-е дороги между i-ми городами. Я учусь в 10 классе и недавно заинтересовался программированием, пытаюсь в задачи на Codeforces, но получается только А. Может, уже поздно вкатываться, но хотелось бы уметь это для себя.
Помогите, я нихуя не понимаю. 1 пик условия, остальные объяснение. на 3 пике: >Сложим все пары (ki, li)длин таких блоков в массив. Что это значит? То есть есть строка aabbbaaaaabbaa то в этот массив поместят(2,3) и (5,2)? И дальше - почему надо найти такое чтобы это выполнялось?
>>915679 >Что это значит? То есть есть строка aabbbaaaaabbaa то в этот массив поместят(2,3) и (5,2)? Сначала для пары (a,b) в массив поместят (2,5)(3,2). Затем для пары (b,a) -> (3,2)(5,2)
>>915679 >>915707 >>915708 Как это работает: Пусть у нас есть строка abbbaabbaaab, рассмотрим для начала только пару (a,b) Тогда странностью такой строки будет количество не повторяющихся странных подстрок вида {a}{b}. Для abbb - это 3. Для aabb - 4, для aaab - 3. Но при этом мы несколько раз посчитали одни и теже подстроки. Вопрос, как посчитать только различные варианты? Для этого представим ось координат с абсциссой колво 'a' и ординатой колво 'b'. И расположем на этой плоскости прямоугольники с одним углом в начале координат и вторым в нашем случае (3,1)(2,2)(1,3) почитаем площадь фигуры. Это и будет ответ без повторений. Теперь повторим все для пары ('b','a').
У тебя на третьей пикче алгоритм нахождения такой площади.
Как лучше считать хэш? По модулю 2^64 - 1 или 10^9 + 1? Первый больше, но зато второй простой. И как лучше хэшировать множество (то есть порядок не важен)?
Полный текст задачи на пике. Если своими словами, то у нас есть неизвестная последовательность нулей и единиц. И запросы на четность единиц в подпоследовательности с L элемента до R элемента. Вопрос, начиная с какого запроса последовательности удовлетворяющей всем запросам не существует?
>>917830 Попробуй сделать так: 1. сет с родителем 0 для чётных, а с 1 для нечётных. 2. Все цифры тогда придётся увеличивать на 1, т.е. вместо единицы будем использовать 2 и т.д. (так как 0 и 1 заняты) 3. unionSet будем использовать только тогда, когда findSet(x) != 0 && findSet(x) != 1 4. Прочитал 1 3 odd, вызываешь unionSet (1, 2), (1, 3), (1, 3), второй аргумент увеличен на 1, см. пункт 2. 5. Делаешь проверку. Суммируешь findSet от 2, 3, 4(увеличены на 1, input у нас 1, 2, 3) 5. Сумму проверяешь на чётность
>>923255 взлом решения мб? кто-то посмотрел твой код, который прошёл претесты, увидел что он выдаст неправильный ответ на какие-то допустимые входные и типа запустил твоё решение на этих входных
>>923464 На главной странице контеста нажимаем замок напротив решенной задачи. Переходим в раздел "комната", дабл-кликом по кол-ву очков открываем решение для просмотра. Находим ошибку Жмем кнопку взломать, пишем тест(грузим генератор) ???? профит
Поясните за вот эту задачу http://codeforces.com/problemset/problem/7/C Я ее решил через длинную арифметику: сначала нашел решение (x0, y0). Потом все решения имеют вид x = x0 + (b/d) k y = y0 - (a/d) k, где d = gcd(a, b), k - целое. Дальше я относительно k решаю систему неравенств -5e18 <= x0 + (b/d) k <= 5e18 -5e18 <= y0 - (a/d) k <= 5e18. Если хотя бы одно k подходит, я его беру и подставляю в формулы выше. Это и есть ответ. Посмотрел решения других людей - они тупо решают уравнение и все. У меня 2 вопроса: 1) почему не может быть такого, что решая это уравнение расширенным алгоритмом Евклида, мы получим какую-то точку, выходящую за ограничения, но при этом существует точка, которая нам подходит? 2) почему не может быть переполнения? насколько большими могут оказаться x и y, когда мы решаем линейное диофантово уравнение?
Блджад. Участовал в контесте на форсах (1400 мусор), решил только А и В. Остальные три были пиздец какой-то. В тренировках такая же хуйня, дальше В никогда не уходил. Причем я не понимаю - вроде основные алгоритмы знаю (да если меня разбудят в 4 утра и насильно посадят за комп, на изи напишу бинпоиск, сортировку за O(n*log(n)), бфс, беллмана-форда, дфс, дейкстру, поиск порядковой статистики, каркас минимальной длины итд). Задачи на динамику тоже решал, получается с шансом 40%, хардово спалить закономерность. Когда читаю разборы последних трех задач, охуеваю - как люди додумываются до ЭТИХ решений. Как вообще люди на олимпиадах побеждают? Я уже с этим тимусом проебался до 100 решенных задач, ацмп решал, читал Шеня. Короче, как вообще люди умудряются искать правильное решение в задачах, где хуй поймешь, какой алгоритм нужен? Тупо нарешивать овердохуя с архивов? И всё?
>>927755 Большинство олимпиадников -- олимпиадники по математике тоже (хотя есть исключения), это сильно прокачивает смекалочку, то есть умение понять, как же найти ключ к этой задаче.
>>927794 Нет, не обязательно. Просто они прокачивают скилл, которого тебе не хватает. Попробуй решать много-много простых задач -- на бинпоиск, поиск в глубину и простенькую динамику (в первых трёх задача на этом вашем КФ только это и нужно). Меньшикова на информатикс, региональные этапы, задачки по темам разным.
>>927755 > Я уже с этим тимусом проебался до 100 решенных задач Очень мало. Это сколько в сумме ты потратил на решение - 50 часов? Хз почему ты не побеждаешь на олимпиадах, когда целых 50 часов потратил. В доте-то, наверное, 1050 часов.
Каким образом можно надрочиться за 2 года, чтобы стать победителем на олимпиаде 1 уровня? Знания по математике хуевые, с программированием еще хуже, даже сортировку не могу написать.
>>929003 informatics.mccme.ru Сидишь и решаешь. Вместо Доты. Тебе должно быть настолько же интересно. Как прокачаешься, пишешь так же кодфорсы сможешь писать.
Как восстановить ответ в задаче о рюкзаке, используя O(N+L) памяти? (N предметов, L вместимость рюкзака) Знаю аналогичный алгоритм в задаче о расстоянии Ливенштейна, но он какой-то сложный (хотя задача вроде проще).
>>932655 Забавно, ты назвал Алгоритм Левештейна сложным, хотя это просто разделяй и властвуй. Обычно когда какой-нибудь алгоритм не до конца разбираешь, считаешь его сложным, хотя на самом деле ты просто не понял его идею. Если бы ты понял как работает Левенштейн, ты бы сразу понял как можно сделать то же самое для рюкзака. http://ideone.com/abUEBD
>>934821 Технически можно приебаться к копированию items при делении пополам - будет N*log(N) памяти, но так более читаемо. Понятно, что можно не копировать, а хранить [l, r]
Не поздно ли вкатываться?Аноним19/03/17 Вск 13:10:03#495№956844
В школе прогал с удовольствием и довольно много, но бессистемно и навыков, кроме непосредственного написания кода, не развил. Потому что долбоеб. Как итог, в 11 классе в олимпиадки не смог, пришлось идти на физику. Сейчас учусь в приличном вузе мфти, но направление скорее связано с математикой и физикой, буду менять. Так вот, летом у меня будет около двух свободных месяцев на то, что бы достичь в своем развитии в плане проганья хотя бы уровня хорошего школьного олимпиадника, с какого бока за это лучше взяться? Я так понимаю, сначала нужно освоить алгоритмы, был даже сайт где список из 80 штук, этого хватит для начала? Как распределить время между теорией и практикой? Есть ли где-то видео-курсы? Так-то я могу ботать по 8 часов, но нужна программа, координация, что бы кто-то вел, по книжкам это тяжело. Ангельский intermediate, речь понимаю, но трачу на это слишком много сил, на постоянный просмотр меня не хватит.
>>956896 Нравится формат, короткие вызовы на несколько часов. Хочется научиться быстрее решать задачи. Если получится, по вузику можно будет ходить как на понтах, с замдекана за руку здороваться
>>956844 1) Одному тяжело будет, тренер нужен. Если ты в мфти, с этим 100% проблем не будет. 2) Решай текущие контесты на codeforces + архив на codeforces, там есть разборы задач и можно смотреть чужие решения. Но вообще, ты какой-то аутист. Олимпиады нужны, чтобы поступить в вуз, а если ты уже поступил, то они нахуй не всрались. В вузе надо либо заниматься наукой (если дохуя умный), либо на работу устраиваться как можно быстрее, чтоб по окончанию вуза уже было много опыта.
>>957744 1. Искать тренера пока рано, как мне кажется. Никто не будет нянчить дауна без базовых алгоритмических знаний, разве что за большие деньги. Собственно, вопрос был про структурированный курс конкретно по спортивным алгоритмам, что бы направляли и объясняли фишки. В свое время начинал просто решать задачи, но сложилось впечатление что это довольно малоэффективный процесс.
Так со стороны для себя вижу несколько выгод: 1) Идея пачками макачить игрушки для айос на модных фреймворках, пусть даже за большие деньги, меня не очень прельщает. А вот идея написания высокоэффективного кода кажется гораздо интереснее, поэтому спортивное программирование кажется мне актуальнее для себя, чем тот же технотрек. 2) Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании, поэтому получить этот навык будет так или иначе полезно. При этом лучше сейчас, чем чеез 6 лет, когда придется начинать работать и гнаться за рынком. Тем более, что учить прикладные технологии сейчас не имеет смысла.
>>958018 > 1. Искать тренера пока рано, как мне кажется. Никто не будет нянчить дауна без базовых алгоритмических знаний, разве что за большие деньги. Блять, что значит нянчить? Ты просто ходишь на тренировки, где ты один или с командой таких же ньюфагов решаешь задачи, а потом идет разбор этих задач. После разбора можешь дорешивать задачи и задавать всякие вопросы. Фишка в том, что если ты решаешь один и не понимаешь, почему у тебя задача не принимается, ты можешь очень долго думать и в итоге все равно не додуматься. Намного лучше у кого-нибудь спросить.
> Идея макачить меня не прельщает. Ты понимаешь, что все, что не наука - это макакинг? Да, есть более высококвалифицированные макаки. Вот я немного шарю в алгоритмах и математике, но макакой я от этого быть не перестаю, потому что я не могу создать что-то новое, чего не было до меня. Я могу хуйнуть нейросеть и распознавать изображения, но не я же придумал алгоритм backpropagation, это будет просто реализация чужой идеи. Ничуть не лучше, чем сайты на пхп хуярить. Если не хочешь заниматься макакингом - поступай в магистратуру, потом в аспиранутру и т д. Если ты тупой как я и не можешь в науку, лучше сразу задумайся о будущей работе и начинай дрочить все разделы cs, а не только алгоритмы. Прочитай все книги Таненбаума.
> Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании На большинстве вакансий не спрашивают динамическое программирование, теорию чисел, геометрию, графы и прочую хуету. Из алгоритмов спрашивают что-нибудь "на смекалочку" (типа найти подмассив с максимальной суммой за O(n)) + то, что реально полезно знать в работе: деревья (красно-черные, b-tree и т д), хэши, сортировки и т д. На олимпиадах ты никогда не будешь писать красно-черное дерево / свою сортировку / свою хэш-таблицу.
Аноны, есть какие-нибудь методы по решению таких задач, как эта: http://acm.timus.ru/problem.aspx?space=1&num=1502 ? Я проебал на ней два часа, вывел какую-то ебанутую формулу, которая почему-то работает и получил AC. Вопрос - есть какие-нибудь статьи/книги, где рассказывается, как решать похожие задачи с нахождением формул?
>>959229 >то, что реально полезно знать в работе > (красно-черные, b-tree и т д), хэши, сортировки Прости, братишка, но по работе скорее всего это не пригодится. Пригодится умение распаковать протобуф, запаковать, написать конфиг, итд. Никогда тебе на работе не придётся задуматься о чём-нибудь реально сложном. Лично я таких работ не встречал.
>>961751 Во-первых, http://www.wolframalpha.com/input/?i=sum+(sum+(i+%2B+j),+j+%3D+i+to+n),+i+%3D+0+to+n Во-вторых, если ты это делаешь на контесте, когда время ограничено и ты не можешь пользоваться вольфрамом, ты можешь упростить эту сумму, чтобы она считалась за O(n) вместо O(n^2), но не искать конечную формулу (пикрелейтед). В-третьих, при желании можно продолжить выводить и вывести конечную формулу тупо в лоб, просто нужно терпение и внимательность. В-четвертых, этот анон >>962679 правильно заметил, решение в лоб проходит, потому что у тебя здесь примерно 5 на 10^7 раз выполняется ans += l + r, а это очень простая операция. Такая простая операция за секунду может успеть выполниться даже 10^9 раз. В среднем за секунду успевает выполниться около 10^8 операций (если это не какие-то сложные операции с дробными числами).
>>792098 (OP) Спрошу тут, ибо хуй знает, где еще спрашивать. Есть массив множеств перестановок A = [a_1, ... a_n]. n Относительно мало, для S_5 (группы перестановок порядка 5) всего 27, для S_6 94. Нужно для каждой пары (a_i, a_j) \in A проверить, совпадают ли у них подруппы, натянутые на данные множества перестановок. То есть: пусть a_i = {tau_1, .. tau_m}, a_j = {delta_1, .. delta_m}. Узнать, равны ли <tau_1, .. tau_m> и <delta_1, .. delta_m>. Можно ли это сделать за вменяемое время? Как вообще натянуть подгруппу на перестановки в комплуктере? Посоны, если кто-нибудь знает подходящую книжку, или пакет в каком-нибудь эре или петухоне, либо хоть что-нибудь способное помочь, напишите, пожалуйста.
>>963087 >Но для начала сформулируй вопрос понятней. Пусть так. Есть два множества перестановок A = {tau_1, ... tau_m} и B = {delta_1, ... delta_m}. Узнать, равны ли подгруппы <A> и <B>.
>>972160 Лол, вот это я тебя обманул. Извини, плохая память. Так это, после сабмита тебе должно выдать все входы и выходы (если ты не в олимпиадном режиме решаешь)
Как найти совершенное паросочетание минимального веса в двудольном графе? Между долями есть всё рёбра, если это важно (наверно нет, потому что можно надобавлять ребёр с весом ∞). http://informatics.mccme.ru/mod/statements/view.php?id=6555#1 - вот эта задача, короче
А как делать неасимптотические оптимизации? Я вот не знаю, разве что очевидные вещи типа: 1) Вот этого заклинания. std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); 2) Сделать один ресайз вместо множества пушбэков в векторе. (а кстати, быстрее ли вообще заменить векторы статическими массивами?) 3) Отсечения в переборе писать. Всяких брейков понаставить. Вот. Вообще компилятор очень умный и всякие штуки сам оптимизирует, да? Типа for (int i = 0; i < m n; ++i) {...}; Он тут не будет скорее всего умножать m на n много раз, а сделает типа int mn = m n; for (int i = 0; i < mn; ++i) {...}; (в теле цикла, понятно, эти переменные не трогают)
>>982275 for (int i = 0, to = m n; i < to; ++i) ... Вместо new Node использовать deque.push_back() && return &deque.back() Но обычно этим не заморачиваются и делают такие тест кейсы, чтобы твой перебор не влез даже с байтоебскими оптимизациями (ну это в нормальных контекстах)
>>982275 В идеале надо читать книги по архитектуре компьютеров и по компиляторам, но на контестах почти всегда можно обойтись без этих знаний. Иногда выстреливает, у меня было несколько примеров.
Например, была задача про дерево с N = 400000. Я подумал, что N какое-то большое и зачем авторы так сделали. Понял, что стэк может переполниться и сделал обход дерева не через рекурсию, а помещая номера вершин в очередь.
В другой раз я решал какую-то задачу через linked list и там были запросы, в результате которых могла создаться новая нода в листе, а могла и не создаться. Запросов там было 100000, но задача не прошла. До сих пор не уверен в чем дело, но видимо в том, что динамическое выделение памяти занимает много времени. Вот если бы компилятор видел, что я подряд в цикле выделяю, он бы соптимизировал и сразу выделил сколько нужно, а там были запросы. Потом я понял, что затупил, и что можно заменить linked list на deque, и задача прошла, потому что deque устроена как массив, который при необходимости увеличивается во сколько-то раз (в 2, кажется), соответственно, делается всего log N запросов на выделение нового участка памяти.
Еще была ситуация, что я решил писать код через лямбды, а компилятор какую-то лямбду скомпилировал во что-то хуевое, задача не проходила. Заменил на императивный вариант и прошла. С тех пор на контестах я все пишу в императивном стиле.
>>982598 >linked list >Запросов там было 100000, но задача не прошла. До сих пор не уверен в чем дело Может имел место произвольный доступ к элементам списка?
>>982598 >компилятор какую-то лямбду скомпилировал во что-то хуевое Вообще пушка. Ты сам смотрел на ассемблерный код, или просто так ляпнул что-то от балды? Я думаю, что ты просто не знаешь С++ и пишешь чушь.
>>982693 > Ты сам смотрел на ассемблерный код Зачем мне смотреть, если я и так знаю, что лямбды могут сконпелироваться в хуйню и не только в плюсах. Заменил лямбду на эквивалентный императивный вариант и зашло. Какой тут еще вывод можно сделать?
>>982673 Нет, там только в начале и в конце добавлялись элементы.
>>982798 >если я и так знаю Короче не слушайте этого шизика, он где-то как-то обжёгся на лямбдах (небось не отличает [=] от [&]), а обосновать или привести примеры не может.
Чтобы не стать такими как он всегда докапывайтесь до истины, если видите, что что-то не работает, а не "ща тут cout вставим чтобы глючить перестало"
>>982368 > &deque.back() Такие ссылки не инвалидируются при новых пушбэках? Или как-то можно указать, чтобы дэк на основе связного списка генерировался? Но тогда какая это оптимизация, если всё равно при каждом добавлении системный вызов.
>>982368 Ну не скажи. Разница между O(n) и O(n log n) весьма призрачная, и оптимизированный логарифм может работать быстрее, чем линейное решение, особенно если у него константа пожирнее. Изредка даже O(n^2) вместо O(n) может зайти, если тесты слабые, либо такое решение, что для него тест непросто придумать, особенно заранее, не зная решение. Конечно, чаще проще решить по честному, но сдать задачу, не решая, тоже весело.
Эй, отвечающие в тред, расскажите, когда и как вы начинали упарывать олимпиадки, какой лвл, где учились/учитесь/работаете. Что читали с самого начала, на какие курсы ходили?
Основные ресурсы с задачками:
codeforces.com - Клевый проект, чуть ли не еженедельные контесты. Система писькомерства рейтинга уровня ELO с Короткевичем 4к+. Задачки своеобразные, пилятся комьюнити, мало общего с задачками стандартного ACM, что продиктовано форматом соревнований. Так же codeforces выбирают площадкой для множества престижных соревнований уровня VK Cup, в тренировки заливаются все крупные контесты оффлайн.
acm.timus.ru - великолепный архив. Решишь 500 задач на тимусе - будешь гарантированно красным на кфе
informatics.mccme.ru - хорош для новичков
Дальше идут ресурсы, которые оп не юзал особенно по своему скудоумию:
acmp.ru - ничего сказать пока не могу
TopCoder.com - пендосский codeforces, регулярные контесты, открытые турниры и тому подобное
e-olymp.com - не знаю
FAQ
Что почитать?
Грэхэм, Кнут, Паташник "Конкретная математика"
Кормен "Алгоритмы. Построение и анализ"
Как вкатиться?
Читай книжки сверху, и решай как можно больше
____________________
Предыдущий тред тонет тут
Шапка за пять минут, надеюсь треду жить, принимаются предложения по оформлению