Вы видите копию треда, сохраненную 23 мая 2017 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Основные ресурсы с задачками:
codeforces.com - Клевый проект, чуть ли не еженедельные контесты. Система писькомерства рейтинга уровня ELO с Короткевичем 4к+. Задачки своеобразные, пилятся комьюнити, мало общего с задачками стандартного ACM, что продиктовано форматом соревнований. Так же codeforces выбирают площадкой для множества престижных соревнований уровня VK Cup, в тренировки заливаются все крупные контесты оффлайн.
acm.timus.ru - великолепный архив. Решишь 500 задач на тимусе - будешь гарантированно красным на кфе
informatics.mccme.ru - хорош для новичков
Дальше идут ресурсы, которые оп не юзал особенно по своему скудоумию:
acmp.ru - ничего сказать пока не могу
TopCoder.com - пендосский codeforces, регулярные контесты, открытые турниры и тому подобное
e-olymp.com - не знаю
FAQ
Что почитать?
Грэхэм, Кнут, Паташник "Конкретная математика"
Кормен "Алгоритмы. Построение и анализ"
Как вкатиться?
Читай книжки сверху, и решай как можно больше
____________________
Предыдущий тред тонет тут >>706304 (OP)
Шапка за пять минут, надеюсь треду жить, принимаются предложения по оформлению
Решать на тимусе задачи по сложности от самых легких до сложных?
Например:
123456
Сумма первых трех 5, сумма последующих 15. Билет несчастливый.
111003
Сумма первых трех чисел 3. Сумма последующих чисел 3. Билет счастливый.
Задача, посчитать сколько счастливых билетов между 100000 и 999999.
Выиграет самый красивый код.
Шах и мат
знатное говноедство, даже я уважаю
[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]
http://ideone.com/rHkZk5
>codeforces.com
вроде отослал один, а он сыпится. нихуя не понимаю, где фак? ввод бинарный чтоль?
да вижу тут есть запускалка, потыкался, я так понял он в sdin пихает, а не в стартовые ключи - как я думал. хотя вроде логично, ведъ программа после ввода должна умереть?
А смысл какой их решать?
В стартовые ключи это как. Там есть задачи с мегабайтами инпута, ключами не обойдёшься.
Твоя задача вывести правильный output и вернуть EXIT_SUCCESS.
>>792801
Для интереса, это в основном хобби. Есть побочные профиты типа "в яндексе любят олимпиадников". Для школьников также помогает попасть на всякие бюджеты, ещё проводятся соревнования с неплохими призами, но это надо сильно угореть по теме.
я вот просто хочу подрочить байтики. на время - не интересно.
>Там есть задачи с мегабайтами инпута, ключами не обойдёшься.
ну наверно тоже верно, но можно было файлами заделать - а то ведь скорость будет сильно зависеть от того как реализован инпут в языке - а оно очень разнородно.
>хобби
Таки да, если не дрочиться по 2-3 5-часовый тренировки в неделю чтобы стать чемпионом мира.
Школьнику однозначно имеет смысл угореть, я сам жалею, что не хватало мотивации/не всегда мог себя заставить ботать в школьном возрасте, победителя всероса а не призера взял бы с легкостью. Все равно это лучше чем проебывать время на каэску какую-нибудь.
Поступление в любой топовый универ халявное, опять же.
Студентам активно задрачивать смысла нет, если не целиться на финал АСМ. Но таки полезные эффекты в виде "быстро решать задачки на собеседовании в Yandex/Google" возникают.
Ну еще, если не совсем донный, да и универ не совсем парашный, можно нахаляву за счет универа то есть ездить по всяким соревнованиям как и в пределах рашки, так и заграницу.
Раньше делали с файлами, но постепенно от этой практики отказались, может быть чтобы полностью избавиться от еботни с правами доступа. Кроме того, тебе же удобнее, сколько WA было получено на неверном названии файла… Причём в некоторых случаях это оказывалось решающим фактором.
>>792866
СЪЕЗДИЛ НАХАЛЯВУ
@
В ПЕТРОЗАДРОТСК
Ну да, это само собой. А еще Москву, Париж, Будапешт, Белград и Катовице (Польша). И везде билеты + проживание - за счет универа
А сейчас люди получают WA на том, что ОЙ А ТУТ ФАЙЛЫ НУЖНЫ. Или ОЙ Я ФАЙЛЫ НЕ ЗАКОММЕНТИЛ (хотя нормальные пацаны юзают препроцессор для этого).
Хотя без файлов таки удобнее, да, жаль, что не везде так сейчас
Сайт крут тем что там дохуй задач и он показывает количество пройденых тестов. Даже на сами тесты можно посмотреть.
но вооще, где-нибудь в лине можно было бы перехватывать пару функций в libc и на любое имя файла давать один путь. наверняка и в винде такое можно провернуть.
Да, МФТИшные сборы, они самые. Сам из Питера, поэтому четверть пишу у себя
вот на соревах стоят ограничения по памяти
но
в jvm языках же сама jvm автоматом отжирает до пизды памяти
получается jvm-блядки априори сразу сосут?
Да. Алсо, ты ещё забыл про инициализацию машины, тоже время отжирает. Выбор языка в любом случае за тобой + ситуации, когда задача решается на С и не решается джавой, крайне редки.
видел советуют книгу Шеня, она ок?
Это в случае, если ТЛ для Джавы стоит раза в 2 больше, что некоторые Online Judges делают по дефолту. А вообще зависит еще и от автора. Если он напишет какое-то заоптимизированное решение на плюсах и поставит жесткие ТЛи чтобы отсечь другое решение с чуть большей асимптотикой, то Джавакодеры соснут
Иди сразу на кодфорсы, читай параллельно емакс, дорешивай задачи и читай разборы. Для начала сойдёт, когда дело дойдёт до уровня суфавтоматов, уже сам разберёшься, что делать.
>>793042
СОКОБАН)))0)
В спортзал и к стилистам всех четверых. Футболки блядь на халка, пошить соразмерные. Крайнему слева в жопе похудеть, перестать жрать говно, перейти на салатики и мясо. Бородачу как минимум выровнять бороду.
друг, где читать разборы? я заходил на рашен кап чето там, но там объяснение мне показалось уже для чуваков которые прорешали пару десятков контестов
На кодфорсах почти к каждому контесту пилят разбор авторы. Кроме этого, не стесняйся в случае чего спрашивать в комментах: пост вынесет на первое место в секции комменты, его увидят и ответят с вероятностью 99%.
>>793052
>абсолютно
Радикально. В многих областях алгоритмы необходимы, пусть и не всем разработчикам.
>>793053
Котёнка лучше не трогать, где ещё такое встретишь, при том что он относительно молод.
Писали же кучу раз
Школьникам есть однозначные профиты которые не очень сложно получить, да и олимпиадки на таком уровне таки сильно влияют на прогерские навыки
Студентам - хобби, помощь на собеседованиях.
Да и полезно таки некоторые алгоритмы писать самому, чтобы понять как работает что-то. Опять же, навыки писать оптимальный код на плюсах
Я не говорю про алгоритмы, они то очень нужны, я говорю про олимпиадную дрочку, которая вырабатывает плохой стиль кода (попробуй попиши читаемый код на время) и бесполезна в реальном мире.
А, ну в этом плане может быть.
Могу поспорить по следующим пунктам:
1. В целом развитие понимания, как всё работает, неасимптотическая оптимизация как, например, std::ios::sync_with_stdio
2. Навык дебага сложных конструкций.
3. Умение писать код быстро и правильно, то есть держать в голове много деталей
Отдельно скажу, что после многих лет олимпиад в проектах всё пишу максимально красиво, по другому уже и не хочется, но тут уже у всех своё. По крайней мере можно сказать, что само понимание красивого кода приходит после взаимодействия, а лучше написания некрасивого.
>как, например, std::ios::sync_with_stdio
Хуевый пример, если честно. В реальной жизни хрен понадобится
Хуёвый, но про плюсы тут особо ничего и не расскажешь. Хотя в целом вопрос I/O в C/C++ довольно занятный.
Вот про питон можно долго говорить, там абсолютно неочевидные вещи происходят.
Че ты врешь?
Ну ты же наверняка понимаешь почему так, или есть хотя бы предположения.
Просто не нравится?
Вполне вероятно, что ты просто мало промышленно кодил, тогда это нормально. В олимпиадках ты ж тоже не сразу начал норм участвовать наприер
>Конкретная математика
первая же задачка - мой пердак в небесах, ответ на неё - подлетаю к юпитеру. это просто пиздец какой-то.
Задавайте свои ответы
Блять, ты тролль или ты серьезно?
Пиздец просто, >на пушбэк поп
Техника имени Семена, блять. Это как про любую задачу сказать "это задача на инт мейн", поеботень полная
>>795406
Тебе надо знать, что такое массивы, как считывать-выводить вещественные числа, и как извлекать корень.
Первое - это лучше погугли и почитай в нормальном месте туториалы по языку, если таких основ не знаешь
Второе - считывать так:
double a;
scanf("%lf", &a);
и писать
printf("%f", a)
На самом деле, это верно для 11+ стандартов, в старых стандартах и читать и выводить с помощью %lf вроде
Третье это
#include <math.h>
...
a = sqrt(23.9);
Я максимум решал 1010+ сложности на тимусе. Я успешнее
Что такое бинарное дерево?
Я не понимаю зачем обсираться в присядку, одновременно обмазываясь говном и дрочить на коколимпидаки и нахуй не нужные алгоритмы
>Что такое бинарное дерево?
На пике.
>>796427
>единственный маршрут
Из 9 в 2 можно идти пом пути 9 4 2 1 2.
>Находишь всех предков обоих вершин.
Не эффективно. Должен быть способ быстрее.
пик забыл
А нет его в памяти. Даже размер не известен. но в long long влазит. Выглядит как на той картинке. Наверно просто максимальный надо делить на 2 пока они не сравняются.
Числа между которыми маршрут прокладывать. Вывести нужно сам маршрут.
1. В любом дереве маршрут всегда единственный, иначе бы там были циклы.
2. Задача сводится к нахождению наименьшего общего предка двух вершин, которую можно решить например алгоритмом Тарьяна.
То, что все лошади одной масти, можно доказать индукцией
по числу лошадей в определенном табуне. Вот так:
„Если существует только одна лошадь, то она своей масти,
так что база индукции тривиальна. Для индуктивного пере-
перехода предположим, что существует п лошадей (с номерами от
1 до п). По индуктивному предположению лошади с номера-
номерами от 1 до п — 1 одинаковой масти, и, аналогично, лошади с
номерами от 2 до п имеют одинаковую масть. Но лошади по-
посредине с номерами от 2 до п — 1 не могут изменять масть в
зависимости от того, как они сгруппированы,—это лошади, а
не хамелеоны. Поэтому в силу транзитивности лошади с номе-
номерами от 1 до п также должны быть одинаковой масти. Таким
образом, все п лошадей одинаковой масти. чтД*
Есть ли ошибка в приведенном рассуждении и какая имен-
именно?
>>795392
просто это математика, мне сложно, нужно по другому мыслить, немного перестроить голову.
Это же очевидно, неверная база индукции. Самый первый переход для n=2 не работает, базой должен быть именно этот случай, что невозможно.
Тарьян offline, лучше всё-таки на sparse table делать.
https://ideone.com/eGhmMK
Граф ориентированный или нет? У тебя в коде он ориентированный, а в задаче как? Видимо, в ней он неориентированный, тогда надо делать
adj_list[begin].push_back (make_pair(end, weigth));
adj_list[end].push_back (make_pair(begin, weigth));
У тебя нет второй строчки
Неориентированный, и еще допустимы мультирёбра, но в тестовых данных для примера мультирёбер нет. Какие изменения в алгоритме надо сделать, чтобы обрабатывать мультиграфы?
Да, этот фикс помог. Матрица неорграфа симметричная, и списки тоже делаются симметрично.
Говорят, что мультиграф надо немного иначе обрабатывать.
Нет, не надо. Лишние ребра тебе ничего плохого не делают: ты все равно в итоге выберешь из всех мультиребер ребро с наименьшим весом. В принципе, если их совсем много, то можно когда строишь граф, просто среди всех ребер, соединяющих одинаковые пары вершин, оставить только ребро с минимальным весом, но алгоритм будет работать корректно и без этого
Блин, тогда я даже не знаю, почему программа проходит все тесты, кроме двух.
https://ideone.com/pJfxfM
А, скорее всего, я вывожу INF там, где по условию надо выводить -1. Сейчас проверю, должно помочь.
И все-таки странно, что авторы обращают внимание на то, что могут попадаться мультиграфы.
Ну например это может быть важно в случае, если человек юзает матрицу смежности вместо списка смежности хотя тогда бы по TL бы не прошло скорее всего. И, как правило, в задачах по умолчанию граф простой, поэтому выделение того, что есть кратные ребра, является некоторым правилом хорошего тона, можно сказать.
На двумерной плоскости имеем набор многоугольников с float координатами. Как определить, находится ли точка внутри какого-либо многоугольника?
Отклеилось.
Да, вспоминаю про трассировку луча. Но тогда ведь нужно проверять каждую грань каждого многоугольника?
Хотя можно применить небольшую оптимизацию и проверять только те многоугольники, с проекциями которых есть пересечения. Или еще лучше, с проекциями сторон которых есть пересечения.
В общем, спасибо, навел на мысли.
Точнее мы тут можем даже до одного сократить.
Если они выпуклые, то для каждого многоугольника можно делать проверку за log(число вершин)
Именно так, если ты ее не заблокировал, конечно
Проще, но на этот способ любят делать контртесты. Надёжнее пускать в рандомном направлении.
>>798379
Я всегда использовал сумму полярных углов. Тема такая, для каждой грани ты считаешь, под каким ориентированным углом она видна из точки. Дальше считаешь сумму, если получилось 0, то ты снаружи, если 360 градусов – внутри. Случай на грани рассматривается отдельно.
>>800440
Бывает, что ломают решения, которые не валятся на тестах.
>>800574
Разбор появляется от сразу до нескольких дней, пали комменты к посту о контесте, там обычно спрашивают такие вещи.
мне сложно, а вот если есть задача - я могу её решить, как там написано, и так же индукцией доказать - не проблема. но когда меня спрашивают, например докажите что в задаче на столбы, используются все возможные комбинации - вообще не ебу как. да, для меня очевидно, что вот число и его бит может иметь 3 значения, тогда число с n бит имеет 3^n-1 возможных комбинации - даже не представляю как это доказывают.
> Почему 3, а не 2?
потому что это из усложненной задачи 2. но я не проверял в ответах заебало чувствовать себя говном
> Откуда -1?
потому что ноль не учитываем - там задача сформулирована так, вродъ.
> А ты попробуй индукцией
как? замкнутая форму уже есть, я её вывел из рекуррентной, опять же, из прошлой задачи. дальше то что?
> 2 Найдите кратчайшую последовательность перекладываний, перемещающих башню из n дисков с левого колышка А на правый колышек В, если прямой обмен дисками между А и В запрещен. (Каждое перекладывание должно производиться через средний колышек. Как обычно, больший диск нельзя
класть на меньший.)
> 3 Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения нам встретятся все допустимые варианты размещения n дисков на трех колышках.
>как? замкнутая форму уже есть, я её вывел из рекуррентной, опять же, из прошлой задачи. дальше то что?
в смысле, я человек тупой, не математик, и не имею этот склад ума, я так понял, что индукция способ доказать что замкнутая форма формулы верна - путём поставления её в рекуррентную.
n > 0
T(0) = 0
T(1) = 1
T(n) = T(n-1)@3 + 2
T(n) = 3^(n)-1
T(n) = T(n-1)@3 + 2 = (3^(n-1)-1)@3 + 2 = 3^n-1 <- это
или что под этим ещё понимается?
Ничего не понял, кинь условие задачи, или что ты там доказываешь.
>Грэхэм, Кнут, Паташник "Конкретная математика"
Этой книги достаточно, чтобы понимать анализ алгоритмов, всякие асимптоты и прочее из следующей книжки? Или придется до кучи ещё математики наверстать? Мой уровень если что на уровне девятиклассника, лол.
Угу. А асимптотика там обсуждается аж в последней главе.
Как я и думал, все эти алгоритмы и интеллектуальные игры с ними для элиты, которую с рождения обучают не тому, что дают в обычной быдло-школе. Пойду дальше в дотку катать.
Просто начни с книжек попроще. "программирование: теоремы и задачи" Шеня, а потом вот это http://codeforces.com/blog/entry/12314
Ну и перед этим учебник школьный по математике, если совсем неуч.
Спасибо. Я настолько тупой, закончил школу, а не могу решить задачи с acmp.ru которые сложнее 30% по их шкале.
Алсо, есть там что-нибудь по преобразованию Фурье?
>Бывает, что ломают решения, которые не валятся на тестах.
Ну вот. Ты меня запутал. Чётно обфусцирую решение на следующем контесте, а нечётно нет.
После множества таких казусов с недавних пор все успешные похеки добавляются в набор финальных тестов.
круто, жаль что я не видел этого в школьном возрасте
Вот две произвольные матрицы либо за эн в кубе умножать, либо хитрый алгоритм. А тут может попроще?
Нет, нельзя, насколько я знаю. Есть только, как ты сказал, хитрые алгоритмы, либо частные случаи типа метода четырёх русских.
Я понимаю, вот и говорю, что я, по крайней мере, никогда о таком частном случае ничего особенного не слышал. Пиши Штрассена или гугли научные статьи на эту тему.
>>805633
Впрочем, можешь ничего не гуглить, вот ответ на твой вопрос http://math.stackexchange.com/questions/20873/whats-the-fastest-way-to-take-powers-of-a-square-matrix
Рассказываю, почему я бросил олимпиадное программирование. Когда я начинал, то думал, что там задачи чисто на смекалку, для решения которых не требуется никаких предварительных знаний. Но это оказалось не так. Есть определенное количество узкоспециализированных тем, например, динамическое программирование или древовидные структуры данных, в которых надо быть хорошо прошаренным, чтобы решать олимпиадные задачи. Если кто не понял, что я сказал, приведу такой пример: если вы попытаетесь доказать хотя бы теорему Пифагора, ничего о геометрии не зная вообще, то у вас ничего не выйдет. Так вот я задумался однажды, стоит ли задрачиваться в темах, которые котируются на олимпиадном программировании, если они мне скорее всего не пригодятся в работе. Лучше уж потрачу это время на изучение чего-нибудь более практичного.
Я бы не бросал, если бы было много свободного времени, но его нет.
Ты прав, в принципе, если не считать, что в некоторых местах типа яндекса и вк олимпиадников очень любят. Да и в целом на базовом уровне почти везде спрашивают, но базовый CS и так все должны знать просто по роду профессии.
Тут замкнутый круг.
В "базовый CS" входит комбинаторика, теория чисел, графы, динамическое программирование. Это активно используется на олимпиадах и во всяких гуглах. Но никак не изучается глубоко в вузах (кроме парфеновской кафедры и еще схожих) и не применяется в рф-it. Кроме сам знаешь где. Тоесть олимпиадное программирование, или тот же Скиена, это единственный способ рф-студенту окунуться в то "а что же там пишут в гуглах, что у нас нет". Да и без олимпиадной подготовки ты будешь о-о-чень долго вникать во всякие crack the coding interview и elements of programming interview.
Вроде это не совсем то. Все точки должны быть задействованы.
Я написал примитивный алгоритм: проходим по точкам, отсортированным убывающе по y, и соединяем ближайшие по x, но иногда он фейлится.
Берёшь самую нижнюю-правую точку, ставишь её как начало координат. Считаешь полярные координаты остальных точек относительно центра. Сортируешь по углу, обходишь в этом порядке.
Дядя Сэджвик с Курсэры так учил
Я походу проще вариант нашел: пространство делится на 2 части по x (можно взять тупо width/2), слева и справа строятся ломаные кривые и потом соединяются.
Хотя тупо width/2 будет ошибкой, нужно чтобы хотя бы 2 точки было на одной из сторон.
матрас из денег всё справит
Все нормас, быстрейшее из всех, O(n).
Проблема была только в разделении. Надо делить линией, которая проходит через самую верхнюю грань и через самую нижнюю. Теперь все без ошибок.
Я думал о корректности.
Из любого набора разных точек можно сделать ломанную линию с непересекающимися кусками, соединяя точки одна за другой в одном направлении. Пересечений гарантированно не будет, если между точками в этом направлении нет других точек.
Мы получаем две ломанных линии, не пересекающиеся между собой. Вопрос только в том, можем ли мы безопасно соединить их концы. Ответ: да, т.к между концами больше нет других точек, т.к. мы заведомо взяли 2 верхние и 2 нижние точки и от каждой начали строить линию.
И все же это не n, а nlogn, т.к. надо сначала отсортировать точки в одном направлении.
Занятно, я всегда пользовался сортировкой по полярному углу. Сложность такая же, но алгоритм ка будто чуть попроще, нет двух частей, тупо сортировкой сразу достигаешь нужный порядок с другой стороны, может быть критична скорость работы с float
(1/Pi) Integrate[((Sin[10x] )/Sin[x])^6, {x, 0, Pi}]
Счастливых билетов: 55252
А вот в таком случае ты что делаешь? Чёрное - как получается по твоему описанию, зелёное - как должно быть.
А интегрирование аналитическое, без погрешностей.
Хотя если оценить вид первообразной и по пределам оборвать, то можно свести все к вычислению 1109369452791600/20078358300
Нет, все верно у меня.
Главное не ошибиться с выбором лево-право у крайних отрезков. Я сначала выбирал тупо - если p1.x < p2.x, то p1 уходит влево, но это не всегда так. Пример на второй пикче.
Понял твое решение, скорее всего, оно лучше.
Хотел придумать корнер-кейс, но сам же на него ответил. При равенстве угла, если он [0; 90], то сортируем по Y возрастающе, если же больше, то убывающе.
Допустим, мы проходим против часовой стрелки от нижней точки. Если мы сначала возьмем по убывающей, то получатся вершины 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к символов. А вот время нужно экономить т.к. важна каждая миллисекунда.
Как решить?
Что за "ассоциативный массив", он совсем медленный, или можно к нему обращаться лишний раз в процессе апдейта?
Пока вижу так: держим массив с координатами всех скобок. Когда надо делать апдейт находим бинарным поиском первую скобку правее места удаления, и начиная с неё до конца массива фиксим каждую скобку.
То есть:
1. Уменьшаем адрес каждой скобки на размер удалённого куска. Скорее всего это подразумевает удаление записи из ассоциативного массива, и добавление новой с другим ключом.
2. Если это закрывающая скобка, а соотв. открывающая левее точки удаления, то обновляем сдвиг в открывающей.
3. Уменьшаем адрес скобки в нашем вспомогательном массиве на размер удалённого куска.
>он совсем медленный
Совсем быстрый. За константу обращение.
>бинарным поиском
И как им искать скобки в не отсортированной строке?
И работает это долго и не правильно.
Вот тест ((abc)()) После удаления любой буквы скобки выделенные жирным трогать не надо. Пока думаю делать вспомогательный массив где отсортированы координаты всех закрывающихся скобок.
Вот например тест "((a)b(c)d)" и удаляем b. В вспомогательном массиве будет 3 7 9. С помощью ассоциативного узнаём координату закрывающейся скобки и проверяем есть ли между ними удалёный элемент. Так должно быть быстрее, но после каждого удаления заново по массиву проходить не хочу, а как после всех удалений применить этот метод не знаю т.к. удалять можно несколько элементов подряд и их потом ещё запоминать придётся.
Всё зависит от требований: много запросов – меняй за линию, это как угодно можно делать, быстрее за раз всё обновить нельзя, будешь на запросы за 1 отвечать. Много удалений, мало запросов – делай вспомогательный массив "текущей версии" для каждого индекса, и вспомогательное дерево типа дерева отрезков для "обновления" индексов за логарифм и взятия за логарифм (с дальнейшей записью в оригинальный массив и обновлением номера версии, чтобы между вырезаниями только один раз каждый индекс заново считать).
А как сделать чтобы пока поступают запросы просто заменяешь символы на пробел, а потом за раз всё удаляешь и скобки корректируешь? Это быстрее всего должно работать. Запросы обычно не большие. Несколько байт. Но может много запросов на небольшой участок строки быть.
>И как им искать скобки в не отсортированной строке?
Для "((abc)())" массив индексов скобок будет [0, 1, 5, 6, 7, 8]
как видишь он отсортирован.
>И работает это долго
Удаление символа в середине строки это уже медленно.
>и не правильно
>После удаления любой буквы скобки выделенные жирным трогать не надо.
В ассоциативном массиве были записи 6:1 и 7:-1, а должны стать 5:1 и 6:-1, само по себе оно не обновится.
лечится. одноклассник не умел решать ничего кроме a и иногда b, а через 1.5. года стал призером всероса.
А у меня в С неправильное решение принялось. Должен быть 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, я не понимаю.
>>825960
> а когда открыл разбор - охуел от простоты и изящества.
Какое изящество, тут просто надо знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает, это знают только всякие дрочилы, которые нарешивают олимпиады по математике для школьников.
А если какие-нибудь методички, в которых подобные тайные знания раскрываются?
Не трать на это время, это полная хуйня. На cf есть нормальные задачи на какие-то определенные темы, решение которых помогает в понимании этих тем. То есть это задачи на какие-то алгоритмы или структуры данных, а не на знание того, что нечетное число можно представить в виде разности квадратов. Просто нужно уметь отличать хуету от нормальных задач.
скиена "олимпиадные задачи по программированию"
>>824692
Я как-то хантился в майкрософт, к Дену Расковалову.
https://www.linkedin.com/in/raskovalov/ru
Он говорит, что только масштабы и время. Тоесть кодфорсес к собеседованиям мало отношения имеет. Так что чтобы решать олимпиады нужно быть задротом и дрочить много именно задачки. Там может быть ад на теорию чисел и комбинаторику. Как в прожект ейлера. После 300 задачек начнешь уже решать без задней мысли. А это полгода дрочильни где-то.
Спасибо.
А что там на собеседованиях спрашивают? Понятно, что разглашать конкретную информацию нельзя, но разгласи неконкретную.
http://poincare.matf.bg.ac.rs/~jelenagr/ASP/testHeadHunter.pdf можешь начать тут, а потом careercup.com
послал бы нахуй за такие вопросы на собеседовании
Говно. Не нашёл вопроса про то, в какую сторону едет автобус.
Здесь обсуждают олимпиаду для поступления в вузы ?
Как в Си вычислить корень 876652098643267843 ?
http://ideone.com/XVSbT2
ХОДИШЬ ТАКОЙ НА ОЛИМПИАДЫ, БЕРЕШЬ ПРИЗОВЫЕ МЕСТА
@
ПРИГЛАШАЮТ РАБОТАТЬ В ЯНДЕКС
@
ПОСЛЕ НАПИСАННОГО ТОБОЙ ОБНОВЛЕНИЯ У ВИНДОВС ПОЛЬЗОВАТЕЛЕЙ СЛЕТАЕТ ВИНДОВС СО ВСЕМ СОДЕРЖИМЫМ ДИСКА Ц
@
С ПОЗОРОМ УВОЛЬНЯЮТ
@
КАРЬЕРА В ИТ ДЛЯ ТЕБЯ ЗАКОНЧЕНА, ПИЗДУЕШЬ РАБОТАТЬ ДВОРНИКОМ
ПОСЛЕ ПОДМЕТЕННОГО ТОБОЙ ПОДЪЕЗДА ПОЛОВИНА ЖИТЕЛЕЙ ПОСКАЛЬЗЫВАЮТСЯ И ЛОМАЮТ НОГИ
@
С ПОЗОРОМ УВОЛЬНЯЮТ
@
НЕ ОСТАЕТСЯ НИЧЕГО ДРУГОГО, КАК СТАТЬ НАЕМНЫМ УБИЙЦЕЙ ЗА ДОЗУ ГЕРОИНА
@
ЦЕЛЬ ИЗЛЕЧИВАЕТСЯ ОТ БОЛЕЗНЕЙ ПОД ТВОИМИ УДАРАМИ
@
ВЫГОНЯЮТ БЕЗ ПЕНСИИ
Рекурсивная функция в две строки, решающая одну из первых задач с тимуса. Что доебался до него?
Разве что while я заменил бы на простой if
http://codeforces.com/contest/709/problem/E
http://pastebin.com/pW573vzV
Время работы там O(n), в этом точно косяка нет. Я заменил рекурсию на while + stack, потому что до этого был stack overflow. То что инпут с помощью Scanner - это норм, потому что если бы инпут не успевал, у меня бы не доходило до stack overflow в первой версии. От лямбд я уже пробовал избавляться, тоже TL.
Хотя сейчас замерил, инпут занимает 2 секунды. Сейчас попробую сканер заменить на что-то побыстрее.
Широковаты. Я от своих тоже в бугурт впадаю.
Сделал. Сначала не сдалось, но потом я еще обернул System.out в BufferedOutputStream и сдалось.
Не понял. А почему BufferedReader не помог? Какая выгода от BufferedOutputStream?
Помог, где-то на полторы секунды быстрее стало, но этого было недостаточно.
> Какая выгода от BufferedOutputStream?
В этой задаче аутпут 400000 и выводится по 1 символу, а это очень долго. А buffered сначала ниче не выводит, а когда делаешь flush, выводит все сразу.
Максимум 1650 было.
>знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает
Если ты не знаешь, что комбинаторный интеграл от 2n+1 равен n(n-1)+n, что ты вообще делаешь в этом треде?
Хуйня для дрочил или специалистов по комбинаторике. Вот ты сколько статей уже написал?
>комбинаторный интеграл
Чоблядь?
Интеграл от 2n+1 равен n^2+n+C, чо ты мне загоняешь? и что за хуйню ты написал, n(n-1)+n = n^2
А комбинаторный интеграл это понятие тесно связанное с комбинаторной производной.
Комбинаторная производная определяется так: 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
Подсказка: интегрирование по частям.
А комбинаторный интеграл это понятие тесно связанное с комбинаторной производной.
Комбинаторная производная определяется так: 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
Подсказка: интегрирование по частям.
Это сколько, 1200-1400 что ли? Могу просто так тебе помочь если че, спрашивай. Я максимум был синим.
1400 - 1600. У меня вопросов особо нет. Надо только надрочиться. А одному это уныленько.
Ты хочешь сказать, что у тебя в городе нет ни одного места, куда можно ходить на тренировки по асм?
Есть. Но этого разве достаточно?
Нет, я сомневаюсь, что Егор будет вести курс по Android в сраном МИРЭА.
Тупая задачка. Почему нельзя просто прибавить ко времени старта врем полета, а потом прибавить разность номеров часовых поясов?
Все, разобрался. Идите нахуй
А кто тебе сказал, что нельзя? Летал самолет или нет, значения не имеет, от этого разница во времени между часовыми поясами не изменится. Здесь просто спрашивается, какое время будет в другом часовом поясе через n-цать часов. И какое все это имеет отношение к погромированию?
http://ideone.com/3x53a2
Дай ссылку на исходную задачу, потому что ты во-первых написал условие как мудак (блядь, неужели нельзя скриншот запостить хотя бы, и пару примером входа выхода), а во-вторых лучше засабмитить, чем какому-то петуху объяснять.
Ну, вот тебе скриншот. А самой задачи на публичных тестилках я не видел. Свой жадник пока что я опровергнуть так и не смог
Ну вот так-то лучше. Сам-то чувствуешь, что гораздо понятнее выглядит? Очевидная динамика же.
Я, конечно, толком в динамику не умею. Но тут и намеков не вижу. Не просветишь?
Хотя тут даже динамика не нужна, жадный алгоритм должен работать. У тебя, наверное, просто не проверяется, что если число нацело делится, то его двигать нельзя уже.
Так ceil же не должен целое число округлять. Или там с точностью может быть лажа?
Да. Я уже вижу. Спасибо, мил человек
> Спортом вестимо.
Игра в доту — это спорт. Решение олимпиадных задач по программированию — это не спорт. Выводы делай сам.
Пидора ответ.
Приходишь на ctf. Дальше все понятно.
Серьезно. Обычно есть отборочные туры, где есть возможность гуглить
Идешь на отборочный тур и узнаешь. Там бывают разные задания: криптография, сети, крекинг етц
Допустим все числа нечетные, тогда просто расположим их так, чтобы их середины находились на оси x и будем зажигать от самого длинного к самому короткому. Допустим, нечетные, тогда то же самое.
Допустим есть четные и нечетные числа. Например, 2 стержня 4 и 5. Тогда придётся все числа той же четности, что и максимальное, зажечь с одного конца, чтобы сделать всех одной четности, а потом применить алгоритм из первого параграфа.
С четными и нечетными я хуйню написал.
Короче зажигаешь самый длинный стержень с двух сторон, а дальше изъебывайся как хочешь, но чтоб все в один момент лопнули. Это можно сделать.
В первую секунду зажигаешь самый длинный стержень с двух сторон, а стержни длины на 1 меньше - с одной стороны, во вторую секунду все стержни которые горят с одной стороны поджигаешь со второй, а все стержни на 1 меньше - с одной стороны. И так далее.
А, там ещё и определённая точка должна загореться последней, вот я мудак.
ты ебанулся? база индукции очевидно верная. переход не верен (при п=2)
Сравни длину длиннейшего пути с количеством вершин + 1.
https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths
>>846526
Честно говоря не понимаю зачем пишут топсорт делать. Наверное чтобы достичь O(N) вместо O(N*log(n)).
По идее достаточно для каждой вершины предрасчитать списки входящих соседей (если вершин с пустым списком >1, то гамильтонова пути сразу нет), а потом пока есть нерассмотренные вершины берёшь рандомную считаешь расстояние от истока до этой вершины как максимум среди её входящих соседей+1. Применяешь алгоритм рекурсивно, не забывая про мемоизацию.
Короче как поиск кратчайшего, только длиннейшего.
Эх, щас бы в 2016 перебором задачу решать, вместо динамического программирования
>>846965
Я, кажется, придумал, что хочу по матрице смежности быстро строить матрицу достижимости
Пиздец я проебался, думал граф неориентированный, тогда это просто бинпоиск и SCC
BFS/DFS, компоненты связности. Предподсчёт за V^2, дальше ответ за 1.
Пререквизиты для Кормена и Кнутопаташика есть ли? Скожите пожалуйста.
У Кормена есть в конце книги поясняется за математику
огромнейшее спасибо
Это все круто, но на личной олимпиаде не проканает. Неумение быстро выдумывать решения - это приговор? Или еще есть шанс до феврали задрочить задачки из первой полутысячи тимуса?
Надо назначить функциям однобуквенные хоткеи так, чтобы сумма чисел обращений к функциям, которым назначены хоткеи, была максимальна.
Хоткеем функции можно назначить только букву, входяшую в её название.
Знаю про венгерский алгоритм, но у меня вес дуги из функции в каждую из допустимых клавиш одинаков. Есть ли что-то быстрее для такого случая?
на то в команде всегда и есть два прогера, один комп, и один математик который придумывает решения, сечешь?
Да. Но мне до студенческих командных нужно дописать личные олимпиадки, где один прогер и один математик в моем лице
Пишу на крестах и пухтоне.
Последнее время само-собой приходится дрочить адгоритмизацию и математику, причем комбинаторику и статистику (что ненавижу, лучше дифуры).
Я чет не понимаю, как программист может не мочь в такое? Что за бред? Это как себя не уважать.
>адгоритмизацию и математику, причем комбинаторику и статистику (что ненавижу, лучше дифуры)
держите матаноблядь!11
hellburnization is a part of CS
не все такие умные и не все так рано начинали, мне вот 30 лет и на тимусе у меня 50 задач, в школе был далек от программистов, даже не знал об этом, но как сейчас выяснилось тогда по матеше я обходил парней ныне уже участников финала мира acm icpc
>обычный minmax не подойдёт т.к. при большой глубине поиска лучший из худших всегда будет проигрыш
Не понял проблему. Оцениваешь все исходы броска кубика, и считаешь матожидание оценок. Или не просто матожидание, а матожидание от некоторой функции, учитывающей твоё отношение к риску. Например если надо срочно догонять противника имеет смысл оценивать нулём исходы, которые не дают тебе достаточно очков.
>похожа на монополию
Пиши эвристический алгоритм.
Если хочешь можно ещё сделать обход дерева ограниченной глубины, а по достижении дна считать оценку. Эвристикой опять же. Альтернативно можно использовать метод Монте-Карло. Берёшь начальное положение и много-много раз отыгрываешь его до конца каким-то простым алгоритмом за обоих игроков, а потом по результатам отыгрышей даёшь оценку положению. Но мне кажется эвристика будет точнее.
>Реквестирую литературу
Ты слишком напрягаешься, смотри как люди делают:
https://github.com/intrepidcoder/monopoly/blob/gh-pages/ai.js
https://github.com/DepthDeluxe/Monopoly/blob/master/src/monopoly/AIPlayer.java
> обход дерева ограниченной глубины, а по достижении дна считать оценку
Так и хочу. Но уже на небольшой глубине можно получить большую оценку, но это будет проигрыш и конец игры. Если в одну и ту же сторону идти, то скоро проиграешь. А в алгоритме перебираются все возможные направления и все возможные броски кубика. Потом смотриться на конкретную глубину и выбираеться тот ход минималиный профит от которого самый большой. Что делать с этими проигрышными тупиками?
И исходники читать не интересно. Хоть статьи скинь.
>получить большую оценку, но это будет проигрыш и конец игры
Оценка не обязательно равна количеству очков. Это может быть и разность очков у тебя и противника, и сложная функция, учитывающая ещё и ситуацию на доске.
Никто не запрещает тебе назначать проигрышам оценку 0.
Так может быть так что все ходы проигрышные. Надо что-то выбрать из тех нулей. Может их в 2 очереди проверять? А с горизонтом что делать? Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный. А алгоритм только на 5 вглубь смотрит и войдёт в проинрышную ветку из которой не выйти.
Ну, так, ты мне какой-то теорию категорий с универсальной алгеброй тычешь. Статистика тут при чём?
>Так может быть так что все ходы проигрышные. Надо что-то выбрать из тех нулей.
Если у всех стратегий одинаковая оценка, то выбираешь рандомно.
>А с горизонтом что делать?
Ну блин, делай как в шахматах делают. По достижении дна оценивай положение на доске эвристикой. В шахматах фигурам назначают цену, цены имеющихся фигур складывают, и ещё как-то расположение учитывают, хз как. Так получают примерную оценку для позиций на дне. Тебе тоже надо придумать эвристику для оценки позиции. Как это сделать я подсказать не могу, тут надо пробовать варианты и проявлять изобретательность.
Попробуй решить https://projecteuler.net/problem=84 может придумаешь как прикрутить себе сети Маркова.
>Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный.
В настолке с кубиком такое нереально. Там слишком много рандома. По этой же причине нет смысла делать сложный алгоритм - разница в уровне игры по сравнению с тривиальным "покупай всё что можешь" будет практически незаметна человеку.
Чего? На диаграмме показаны соотношения между распределениями случайных величин.
len([x for x in range(100000, 999999) if sum(map(lambda x: int(x[0]) - int(x[1]),
zip(str(x // 1000), str(x % 1000)))) == 0])
Ошибка вышла:
len([x for x in range(100000, 1000000) if sum(map(lambda x: int(x[0]) - int(x[1]),
zip(str(x // 1000).ljust(3, '0'), str(x % 1000).ljust(3, '0')))) == 0])
Мне это напомнило задачу с прошлогоднего полуфинала или даже финала. Копни в эту сторону Насколько я помню, там отчасти рандомизированный алгоритм. Сперва что-то поспрашивать, а потом решать.
Прости, я тебе наврал. Мне почему-то вспомнилась задача J https://neerc.ifmo.ru/archive/2015/neerc-2015.pdf
Но это совсем из другой оперы
http://rce.su/randomizirovannyj-protokol-svyazi-chast-1/
Вот это попробуй почитать.
А откуда задача?
Хорошо, спасибо. На паре по дискретной математике задали.:(
Да, спасибо, подходит
Отсортируй по количеству решивших. Начинай решать. Если чуешь, что очень легко идет, листай на следующую страницу
спасибо, так и сделаю
http://ideone.com/iTglQT
>>875130
Ты внимательно прочитал условие?
Особенно про то, что размеры строк r^2, а памяти - r, и что она неперезаписываемая?
Да, задачка решается для строк размера r^2 , r бит неперзаписываемой памяти и r+1 запросе. Я думал, это очевидно.
Из ряда натуральных чисел выбрать произвольное количество чисел так, чтобы их сумма не делилась на 6. При этом сумму надо максимизировать. На выход количество выбранных чисел и их сумму. Я не совсем ньюфаг в олимпиадном программировании, но тут встал в тупик. А егэ сдавать надо
Динамическое программирование: f(i, c) = максимальная сумма подпоследовательности arr[:i], делящаяся на c.
s/делящаяся на c/дающая c в остатке при делении на 6/
Как насчёт взять все, а потом при необходимости выбросить наименьшее, не делящееся на 6?
Я бы на твоём месте ещё подумал, задача-то простая. Но если совсем зашёл в тупик, то вот
http://lpaste.net/339079
Ввёл тебе за щёку.
Я понял задачу так, что обязательно использовать ровно r+1 запрос.
В таком случае возникает проблема, что на каком-то шаге мы можем обнаружить расхождение, но мы обязаны сделать остальные шаги, и непонятно как передать на эти шаги информацию о том, что различия уже найдены.
Нет, ты неправильно понял задачу. Обычно такие странные условия обговариваются. Например, было бы написано "сделав ровно r+1 запрос"
Думаю ты прав, держи няшку.
И еще может кто-нибуд в технокубке участвовал? Какого уровня там задачи? Там вообще ебанутые какие-то правила с этими взломами, не знаю осилю ли я там хороший результат показать.
Ну, участвовал в твоем технокубке. Из-за того, что не в том порядке стал решать задачи, занял не 70-какое-то, а 150 с хуем место. Не понравилось
Хули тут думать-то, жадный алгоритм же.
Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i.
Ну а что ты хотел, я тогда только начал вкатываться в си и программирование вообще
>среди работ с дедлайном >= i.
А если таких нет, то ничего не назначать, а потом делать дополнительный проход, заполняя дни без назначений?
И как находить такие дни - поддерживать отсортированную по штрафу коллекцию, и в неё докидывать работы из заранее подготовленного списка работ, сгруппированных по дедлайну?
Мне кажется проще назначать день работе с наибольшим штрафом. Если есть свободные дни до дедлайна, то забираем последний. Иначе забираем последний из дней после дедлайна.
Способы представления графов в памяти, DFS/BFS, алгоритм Дейкстры, комбинаторика на уровне итерации по всем перестановкам и сочетаниям, бинарный поиск, алгоритм Эвклида, решето Эратосфена, генерация пифагоровых троек, метод ветвей и границ.
На самом деле сам поймёшь что нужно когда будешь натыкатьсся на трудные задачи.
Как научиьься выступать в суде защитником в деле об ебле козы бабы Нюры? Смотрю в интернете всякие видео уроки по выступлениям-заседаниям, типа quicksort, но выступить в суде в котором выступаю не могу. Сто делать?
Находишь в интернете реализацию ксорта на твоем языке. Понимаешь. Потом переписываешь, можно подглядывать. Как переписал, закрываешь. На следующий день без подглядывания пиши.
Спасибо.
Задвай себе вопрос "а что надо делать" и делай. Потом "а что теперь?" и так далее. После каждого такого шага чекай всё ли правильно работает.
> Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i.
И какая у этого алгоритмическая сложность? По-моему, не меньше O(N^2). Многовато.
Про кучу не слышал?
Сап. Есть в треде алгоритмодрочеры?
Есть таблица связей в бд (postgres): юзер id - группа id.
Нужно выделить несколько секций юзеров (нужно, чтобы было максимум N юзеров в каждой такой секции), которые входят в группы "эксклюзивно".
Другими словами. Допустим N=1000. В секции #1 будет 10 групп, в которые входят только юзеры из этой секции, всего 980 юзеров в секции #1. В секции #2 будет 14 групп, в которые входят только юзеры из секции #2, всего 900 юзеров в этой секции. Всех остальных относим в последнюю секцию. Нужно найти такие вот секции, приблизительно.
Какой тут алгоритм применять?
Главное чтобы быстрее работало, какая-то точность разбития на секции (типа, чтобы максимально скомпоновать юзеров по N=1000 в секции) не нужна.
Пока вижу просто тупо ходить в цикле по группам (в порядке возрастания популярности групп, навеhное), собирать юзеров, пока не наберется 1000, после чего собирать следующую.
Трудно что-то сказать не зная как распределены пользователи по группам и что значит "приблизительно" и "эксклюзивно".
Выбирай очередную группу рандомом пока не наберёшь достаточно, делай несколько подходов, выбирай лучший результат.
>не зная как распределены пользователи по группам
Как угодно, считай, это группы в вк.
>"приблизительно"
Я имел, ввиду, что не хочу найти лучшее решение из возможных (где секции максимально укомплектованы - по 999, 998 юзеров, например, в каждой), а более быстрое (то есть, пусть там в каждой секции будет по 900-1000 юзеров, это ок).
>"эксклюзивно"
Это я просто так назвал, не знаю как правильно. Смысл - в каждой секции должны быть группы, в которые входят только юзеры из этой секции, не пересекаясь с другими секциями.
Как я уже написал, группы - это как группы в вк. То есть, например, соберу секцию #1, где будет группа любителей хентая 500чел + группа любителей гуро 400чел (из них 100, например, входят в группу хентая) + группа любителей golang 10чел. В других секциях любителей хентая, гуро и golang быть не должно.
И т.д. Большие группы, типа мдк, где >1000чел, не входят в секции. Но их подписчики могут быть любителями хентая, гуро, golang.
>В других секциях любителей хентая, гуро и golang быть не должно.
Это строго обязательно? Это условие сильно усложняет задачу.
>codeforces.com
>acm.timus.ru
>informatics.mccme.ru
>acmp.ru
>TopCoder.com
>etc
Скажите, а есть возможность на каком-нибудь из этих ресурсах сдавать задания на питоне?
Думаю можно. Выясни какие олимпиады тебе подходят, посмотри задачи прошлых лет. Нарешивай подобные задачи и читай теорию.
Да
>>881549
Есть знакомые, которые из твоего положения и хуже брали себе потом диплом всероса, так что дрочи задачки. Посмотри на иоип, например
На топкодере вроде нельзя. Но вообще не надо писать олимпиады на питоне
Ты сам не можешь посмотреть?
на всех, даже etc
что задрачивать, чтобы стать хотя бы синим?
На синего хватит простых графов, бинпоиска, качественного конструктива. Сложные алгоритмы начинаются после Ddiv2
спасибо
Спасибо
Потому что рано или поздно ты столкнешься с тл. Мало где на олимпиадах гарантируют решабельность на питоне
> Как я уже написал, группы - это как группы в вк. То есть, например, соберу секцию #1, где будет группа любителей хентая 500чел + группа любителей гуро 400чел (из них 100, например, входят в группу хентая) + группа любителей golang 10чел. В других секциях любителей хентая, гуро и golang быть не должно.
> И т.д. Большие группы, типа мдк, где >1000чел, не входят в секции. Но их подписчики могут быть любителями хентая, гуро, golang.
Ну что же вы, бэтманы?
Я думал, в треде есть бородатые гики, что пояснят по хардкору, какой мне алгоритм нужен.
Сколько групп всего?
Если не больше нескольких тысяч, то можно представить их в виде графа, в котором две вершины соединены если в соотв. группах нет общих членов. Перебираешь в нём клики Броном-Кербошем, и когда находишь подходящую удаляешь её из графа. В принципе может и не обязательно хранить граф в явном виде, в конце концов проверить наличие дуги между группами можно глянув на пользователей.
Но лучше делай как я уже написал >>881503
>Выбирай очередную группу рандомом пока не наберёшь достаточно, делай несколько подходов, выбирай лучший результат.
Можешь ещё отранжировать группы по аутичности, то есть отношению количества пользователей группы к количеству других групп в которых они состоят (или суммарному количеству пользователей в которых они состоят). Начинать наполнение секции лучше с аутистов.
Вангую что результаты тебя огорчат из-за того что есть боты, вступающие в дохуярд групп.
Я вот вообще не пробовал олимпиадное программирование раньше, но опыта в пограммировании каких-то практических вещей и всякой хуйни у меня куча. И вот в этом году я неплохо так начал в него вкатываться. 11-класс
Интересует решение задания "743D - Хлоя и приятные подарки" на codefoces
Разбор здесь http://codeforces.com/blog/entry/49049 , но я в упор не понимаю, как его реализовать.
Кому не лень и кто шарит, можете разжевать идиоту.
бамп посту
>я в упор не понимаю, как его реализовать
Там же решение на С++. Да и рекурсивное решение тупое как с перестановками:
Вывести все перестановки N чисел.
Перестановка N чисел - это перестановка первого числа и последовательности N-1. И так повторять пока N не будет равно 2, а два элемента переставить может даже школьник.
>решение тупое
>Вывести все перестановки N чисел.
На минуточку N до 2*10^5.
Вот если ты вообще не в теме, но нахуя лезть в каждую бочку затычкой?
На минуточку ты долбаеб, а первоначальная задача легко решается рекуррентно за n операций. Я же привел задачу намного сложнее, которая тоже легко решается похожим образом.
Толку в этих задачах все равно 0, а автора кода надо бить палкой по голове за такой код
Тогда у тебя дохуя мотивации. От халявного поступления в вуз и повышенной стипухи, до чемпионата мира в пендосии. Открыл книгу и начал читать, нахуй
ну тут сразу понятно что вершины надо не удалять, а добавлять в обратном порядке.
дальше очевидный флойд уоршел
получается 500^3, норм тебе?
только смотри не объебись - в двух внутренних циклах надо итерироваться по всем вершинам, а не только по добавленным.
На что мне твой зуб?
То есть секрет чуваков, которые делают это за час тебя не интересует?
Буду краток. знаешь, буквально на днях я был в Российской Академии
Наук, провёл беседу со многими учёными, в том числе молодыми, кстати,
очень грамотные ребята. Так вот мы обсудили, в частности и данную
проблему, поговорили о текущей экономической обстановке в стране; они
так же рассказали о своих планах на будущее.
Вкратце, ответ на твой вопрос такой: эти ребята довольно быстро решают задачи, что позволяет им придумать алгоритм и написать код для задач всего раунда всего за два часа.
> Покажите, что алгоритм, который содержит не больше некоторого по-
> постоянного количества вызовов процедуры с полиномиальным временем
> работы, сам работает полиномиальное время. Если же алгоритм делает
> полиномиальное число вызовов такой процедуры, то общее время работы
> может быть экспоненциальным.
Посоны, откуда здесь экспоненциальное время выполнения?
Выглядит странно. Очевидно, что суперпозиция полиномов есть полином. Может, там процедура может сама себя дёргать или алгоритм?
Секрет в том, что родились с более подходящей для решения подобных задач генетикой
У меня вот прямо щас лежит открытая в туалете глава про NP, но ничего наводящего на мысль не нахожу. Подскажешь конкретнее?
Спасибо. Только легче не стало.
Может я неправильно понимаю эту задачу? Ну подставили мы в x^10 значение x=n^20, получили n^200, экспонента никак не получается.
Тут шизофазия, смотрите
Бля у третьего дедка волосы как солнце хех
http://rgho.st/6smPy2ygw
Задача Эйлера в классическом виде же?
#3296 Поход (6-9)
Темы: [Динамическое программирование: два параметра]
Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2011, Задача D ]
Тут не нужны никакие графы и поиски кратчайших путей.
Это задача для 6ого класса. Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу. Код на богоподобной Яве по ссылке.
http://ideone.com/34HGKf
>Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу
Частный случай поиска кратчайшего пути, вариант реализации с бинарным графом.
Так то да, но тут время О(n) и памяти O(1), а у Дейкстры? Впрочем можешь не отвечать. Просто покажи реализацию, лучше всего на фибоначчевой куче, тебе явно это раз плюнуть, делов на 5 минут. А мне интересно.
>Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу
Так мой код тоже самое и делает, нет? Конечно, там есть дохуя костылей, но всё же.
Прости, но твой код написан так, что его даже читать не хочется. В нем нем ясной выраженной мысли. Зачем ты проверяешь следующий символ в строке? Зачем тебе переменная up? И где у тебя хранится минимум переправ до текущей точки (и правого и левого) берега реки?
>Зачем ты проверяешь следующий символ в строке?
Для логичности, если сверху слева, конечно, но по картинке как будто сверху(т.е переменная up=1, а если снизу справа, ага, то соответственно up=0) идут два подряд (этот символ и следующий -- LL) притока, то выгоднее будет переправиться вниз, где таких притоков нет. Если сверху идёт лишь один приток, а второй снизу (LR), то выгоднее будет переправиться дальше вправо, чем переправиться вниз, а потом снова вверх.
>И где у тебя хранится минимум переправ до текущей точки (и правого и левого) берега реки?
Собственно, в переменной p, которая и выводится в конце. Правда, там по-другому описано, и нет отдельно левого и правого берега.
Я неофит просто, в этом году едва в регионалку по всеросу не попал.
Действительно, у меня при притоках по всем сторонам (B) он поворачивает, хотя это совсем не обязательно.
Спасибо, спустя ещё несколько костылей будут все сто баллов, а так пока что 60.
Анончик, не делай так. Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед. Посмотри выше решение готовое. И просто разберись почему оно работает. В нем мы идем, как будто по обеим сторонам реки одновременно.
>Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед
Но почему? Извини, понять не могу.
>И просто разберись почему оно работает.
Хотелось бы всё же допилить своё решение, а если совсем не выйдет -- разобраться в чужих.
Ну не на пять минут, но мне тоже интересно. Мои соображения:
- в каждой точке графа у нас есть два возможных пути
- выбирая каждый раз пусть с меньшим весом, вы в итоге получим кратчайший (в волновом алгоритме всегда обсчитываем только одну ветку)
- переход протоки на стороне, где сейчас игрок, стоит 1
- переход на другую сторону учитывается вместе с переходом протоки на другой стороне (то есть результирующий вес на этом шаге либо 0, либо 2)
Память не нужна, сложность O(n).
Хотя да, заняло минут 7-10.
Тут есть маленький нюанс, но пусть спрашивающий сам догадается. Я могу дать подсказку.
опечатка: 1 либо 2*
Считать надо 2 шага, этот и следующий (как сумму), а при прочих равных выбирать правый берег.
Код покажи.
Лул
мимо-школьник
Задача о ноп?
Может, уже поздно вкатываться, но хотелось бы уметь это для себя.
Вкатываться не поздно, читай Шеня, Окулова и архивы олимпиад (mccme.ru и прочее, что есть в шапке)
Добра тебе
https://www.coursera.org/learn/algorithms-part1
https://www.coursera.org/learn/java-data-structures-algorithms-2
Быстро проходишь оба курса.
Перестаешь быть зеленым на форсах.
молоток, какой теперь? как к этому шел?
да они офигенные, это 2011 год в Орландо
Для форсов и ОП итмошный куср лучше, причем сильно лучше. Но у него выше уровень входа. В нем мало теории и много отличных задач.
Сайты верстать не поможет. Так что можешь не париться.
Кстати, если не был зарегистрирован, то никак.
Есть список презентаций из учебных видео.
https://courses.edx.org/courses/course-v1:ITMOx+I2CPx+3T2016/bf78f3a948074b16ba7146b1be3b4850/
Список задач с разборами добрые люди дожны были выложить на гитхаб.
на 3 пике:
>Сложим все пары (ki, li)длин таких блоков в массив.
Что это значит? То есть есть строка aabbbaaaaabbaa то в этот массив поместят(2,3) и (5,2)?
И дальше - почему надо найти такое чтобы это выполнялось?
>Что это значит? То есть есть строка aabbbaaaaabbaa то в этот массив поместят(2,3) и (5,2)?
Сначала для пары (a,b) в массив поместят (2,5)(3,2).
Затем для пары (b,a) -> (3,2)(5,2)
>>915707
>>915708
Как это работает:
Пусть у нас есть строка abbbaabbaaab, рассмотрим для начала только пару (a,b)
Тогда странностью такой строки будет количество не повторяющихся странных подстрок вида {a}{b}. Для abbb - это 3. Для aabb - 4, для aaab - 3. Но при этом мы несколько раз посчитали одни и теже подстроки.
Вопрос, как посчитать только различные варианты?
Для этого представим ось координат с абсциссой колво 'a' и ординатой колво 'b'. И расположем на этой плоскости прямоугольники с одним углом в начале координат и вторым в нашем случае (3,1)(2,2)(1,3) почитаем площадь фигуры. Это и будет ответ без повторений. Теперь повторим все для пары ('b','a').
У тебя на третьей пикче алгоритм нахождения такой площади.
Дошло, спасибо.
Первый больше, но зато второй простой.
И как лучше хэшировать множество (то есть порядок не важен)?
Решай на ацмп
какой на форсах, сколько на тимусе?
Так я не для олимпиад хочу вкатиться, а просто, чтобы перестать писать велосипеды
1) по модулю 2^32 - 1, это быстрее
2) любой ассоциативной операцией от хешэй элементов (я часто xor использую)
Как решить используя DSU?
Попробуй сделать так:
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. Сумму проверяешь на чётность
Пункт 4. Не ясен. Почему для четного отрезка все внутренние точки добавляются в нечетное множество?
Вот на пикче есть объяснение с форсов, но я его тоже не понимаю.
Т.е. вот есть запрос l r odd. Это значит, что либо (1,l-1)=odd и (1,r)=odd либо (1,l-1)=even и (1,r)=even. Но что с этим делать не ясно.
взлом решения мб?
кто-то посмотрел твой код, который прошёл претесты, увидел что он выдаст неправильный ответ на какие-то допустимые входные и типа запустил твоё решение на этих входных
На главной странице контеста нажимаем замок напротив решенной задачи.
Переходим в раздел "комната", дабл-кликом по кол-ву очков открываем решение для просмотра.
Находим ошибку
Жмем кнопку взломать, пишем тест(грузим генератор)
????
профит
спасибо
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, когда мы решаем линейное диофантово уравнение?
Короче, как вообще люди умудряются искать правильное решение в задачах, где хуй поймешь, какой алгоритм нужен? Тупо нарешивать овердохуя с архивов? И всё?
Большинство олимпиадников -- олимпиадники по математике тоже (хотя есть исключения), это сильно прокачивает смекалочку, то есть умение понять, как же найти ключ к этой задаче.
Никогда не увлекался олимпами по матану. Значит, нужно забить болт на форсы, ибо без скиллов с математических олимпиад никак не апнуться?
Нет, не обязательно. Просто они прокачивают скилл, которого тебе не хватает.
Попробуй решать много-много простых задач -- на бинпоиск, поиск в глубину и простенькую динамику (в первых трёх задача на этом вашем КФ только это и нужно). Меньшикова на информатикс, региональные этапы, задачки по темам разным.
> Я уже с этим тимусом проебался до 100 решенных задач
Очень мало. Это сколько в сумме ты потратил на решение - 50 часов? Хз почему ты не побеждаешь на олимпиадах, когда целых 50 часов потратил. В доте-то, наверное, 1050 часов.
100500 часов в дотке и все равно в брозе, потому что тима не тянет =)
Ну так если длинная арифметика нужна.
Лол, что за хуйня, если меня ночью разбудить, я нихуя не напишу. Мимо-2000-на-кф
Нужен опыт именно в олимпиадных задачах, со временем начинаешь узнавать неочевидные использования того или иного алгоритма и решаешь.
В школе ходил на олимпиады по математике, там та же хуйня была, если видел несколько сотен задачек то почти всегда сразу знаешь куда копать.
informatics.mccme.ru
Сидишь и решаешь. Вместо Доты. Тебе должно быть настолько же интересно.
Как прокачаешься, пишешь так же кодфорсы сможешь писать.
http://acm.timus.ru/problem.aspx?space=1&num=1141
Я прям не ебу, почему у меня WA
http://pastebin.com/Vg6Sj7Cf
Я просто вычисляю
d = eφ(φ(n)) - 1 (mod φ(n)),
m = cd (mod n).
Что вообще там может не работать?
Как там круды поживают?
Pizda треду
Знаю аналогичный алгоритм в задаче о расстоянии Ливенштейна, но он какой-то сложный (хотя задача вроде проще).
Проиграл со сложного алгоритма о расстоянии Левенштейна.
https://www.cs.colostate.edu/~cs575dl/Sp2015/Lectures/Knapsack.pdf
Забавно, ты назвал Алгоритм Левештейна сложным, хотя это просто разделяй и властвуй. Обычно когда какой-нибудь алгоритм не до конца разбираешь, считаешь его сложным, хотя на самом деле ты просто не понял его идею.
Если бы ты понял как работает Левенштейн, ты бы сразу понял как можно сделать то же самое для рюкзака.
http://ideone.com/abUEBD
Технически можно приебаться к копированию items при делении пополам - будет N*log(N) памяти, но так более читаемо. Понятно, что можно не копировать, а хранить [l, r]
Как итог, в 11 классе в олимпиадки не смог, пришлось идти на физику. Сейчас учусь в приличном вузе мфти, но направление скорее связано с математикой и физикой, буду менять.
Так вот, летом у меня будет около двух свободных месяцев на то, что бы достичь в своем развитии в плане проганья хотя бы уровня хорошего школьного олимпиадника, с какого бока за это лучше взяться? Я так понимаю, сначала нужно освоить алгоритмы, был даже сайт где список из 80 штук, этого хватит для начала? Как распределить время между теорией и практикой?
Есть ли где-то видео-курсы? Так-то я могу ботать по 8 часов, но нужна программа, координация, что бы кто-то вел, по книжкам это тяжело. Ангельский intermediate, речь понимаю, но трачу на это слишком много сил, на постоянный просмотр меня не хватит.
Вебмакак сейчас очень много, поэтому лучше вкатываться в низкоуровневое программирование и embedded.
Embedded-макак сейчас очень много, поэтому лучше вкатываться в высокоуровневое программирование и веб.
>олимпиадное программирование после школы
Зачем?
Вкатиться в алгоритмы и структуры данных необходимо, но олимпиады не нужны.
Нравится формат, короткие вызовы на несколько часов. Хочется научиться быстрее решать задачи.
Если получится, по вузику можно будет ходить как на понтах, с замдекана за руку здороваться
1) Одному тяжело будет, тренер нужен. Если ты в мфти, с этим 100% проблем не будет.
2) Решай текущие контесты на codeforces + архив на codeforces, там есть разборы задач и можно смотреть чужие решения.
Но вообще, ты какой-то аутист. Олимпиады нужны, чтобы поступить в вуз, а если ты уже поступил, то они нахуй не всрались. В вузе надо либо заниматься наукой (если дохуя умный), либо на работу устраиваться как можно быстрее, чтоб по окончанию вуза уже было много опыта.
1. Искать тренера пока рано, как мне кажется. Никто не будет нянчить дауна без базовых алгоритмических знаний, разве что за большие деньги. Собственно, вопрос был про структурированный курс конкретно по спортивным алгоритмам, что бы направляли и объясняли фишки. В свое время начинал просто решать задачи, но сложилось впечатление что это довольно малоэффективный процесс.
Так со стороны для себя вижу несколько выгод:
1) Идея пачками макачить игрушки для айос на модных фреймворках, пусть даже за большие деньги, меня не очень прельщает.
А вот идея написания высокоэффективного кода кажется гораздо интереснее, поэтому спортивное программирование кажется мне актуальнее для себя, чем тот же технотрек.
2) Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании, поэтому получить этот навык будет так или иначе полезно. При этом лучше сейчас, чем чеез 6 лет, когда придется начинать работать и гнаться за рынком. Тем более, что учить прикладные технологии сейчас не имеет смысла.
> 1. Искать тренера пока рано, как мне кажется. Никто не будет нянчить дауна без базовых алгоритмических знаний, разве что за большие деньги.
Блять, что значит нянчить? Ты просто ходишь на тренировки, где ты один или с командой таких же ньюфагов решаешь задачи, а потом идет разбор этих задач. После разбора можешь дорешивать задачи и задавать всякие вопросы. Фишка в том, что если ты решаешь один и не понимаешь, почему у тебя задача не принимается, ты можешь очень долго думать и в итоге все равно не додуматься. Намного лучше у кого-нибудь спросить.
> Идея макачить меня не прельщает.
Ты понимаешь, что все, что не наука - это макакинг? Да, есть более высококвалифицированные макаки. Вот я немного шарю в алгоритмах и математике, но макакой я от этого быть не перестаю, потому что я не могу создать что-то новое, чего не было до меня. Я могу хуйнуть нейросеть и распознавать изображения, но не я же придумал алгоритм backpropagation, это будет просто реализация чужой идеи. Ничуть не лучше, чем сайты на пхп хуярить. Если не хочешь заниматься макакингом - поступай в магистратуру, потом в аспиранутру и т д. Если ты тупой как я и не можешь в науку, лучше сразу задумайся о будущей работе и начинай дрочить все разделы cs, а не только алгоритмы. Прочитай все книги Таненбаума.
> Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании
На большинстве вакансий не спрашивают динамическое программирование, теорию чисел, геометрию, графы и прочую хуету. Из алгоритмов спрашивают что-нибудь "на смекалочку" (типа найти подмассив с максимальной суммой за O(n)) + то, что реально полезно знать в работе: деревья (красно-черные, b-tree и т д), хэши, сортировки и т д. На олимпиадах ты никогда не будешь писать красно-черное дерево / свою сортировку / свою хэш-таблицу.
Мой код:
http://acm.timus.ru/forum/thread.aspx?id=36064&upd=636260865438522774
Моё решение заключается в том, чтобы с помощью BFS покрасить все вершины и записать в ответ те, которые имеют одинаковый цвет
Я проебал на ней два часа, вывел какую-то ебанутую формулу, которая почему-то работает и получил AC. Вопрос - есть какие-нибудь статьи/книги, где рассказывается, как решать похожие задачи с нахождением формул?
Ты че, поехавший?
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
int64_t ans = 0;
for (int l = 0; l <= n; ++l) {
for (int r = l; r <= n; ++r) {
ans += l + r;
}
}
cout << ans << endl;
}
>то, что реально полезно знать в работе
> (красно-черные, b-tree и т д), хэши, сортировки
Прости, братишка, но по работе скорее всего это не пригодится. Пригодится умение распаковать протобуф, запаковать, написать конфиг, итд. Никогда тебе на работе не придётся задуматься о чём-нибудь реально сложном. Лично я таких работ не встречал.
Во-первых,
http://www.wolframalpha.com/input/?i=sum+(sum+(i+++j),+j+=+i+to+n),+i+=+0+to+n
Во-вторых, если ты это делаешь на контесте, когда время ограничено и ты не можешь пользоваться вольфрамом, ты можешь упростить эту сумму, чтобы она считалась за O(n) вместо O(n^2), но не искать конечную формулу (пикрелейтед).
В-третьих, при желании можно продолжить выводить и вывести конечную формулу тупо в лоб, просто нужно терпение и внимательность.
В-четвертых, этот анон >>962679 правильно заметил, решение в лоб проходит, потому что у тебя здесь примерно 5 на 10^7 раз выполняется ans += l + r, а это очень простая операция. Такая простая операция за секунду может успеть выполниться даже 10^9 раз. В среднем за секунду успевает выполниться около 10^8 операций (если это не какие-то сложные операции с дробными числами).
Спрошу тут, ибо хуй знает, где еще спрашивать.
Есть массив множеств перестановок 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>.
Можно ли это сделать за вменяемое время? Как вообще натянуть подгруппу на перестановки в комплуктере?
Посоны, если кто-нибудь знает подходящую книжку, или пакет в каком-нибудь эре или петухоне, либо хоть что-нибудь способное помочь, напишите, пожалуйста.
>Спрошу тут, ибо хуй знает, где еще спрашивать.
Маттред в /sci/, dxdy, math.stackexchange.com
Но для начала сформулируй вопрос понятней.
>Но для начала сформулируй вопрос понятней.
Пусть так.
Есть два множества перестановок A = {tau_1, ... tau_m} и B = {delta_1, ... delta_m}.
Узнать, равны ли подгруппы <A> и <B>.
A, B подмножества группы перестановок S_n.
Ещё суффдерево можно + дфс, но раз ты такое спрашиваешь, вряд ли ты его напишешь с первого раза.
Лол, вот это я тебя обманул. Извини, плохая память. Так это, после сабмита тебе должно выдать все входы и выходы (если ты не в олимпиадном режиме решаешь)
Между долями есть всё рёбра, если это важно (наверно нет, потому что можно надобавлять ребёр с весом ∞).
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) {...};
(в теле цикла, понятно, эти переменные не трогают)
for (int i = 0, to = m n; i < to; ++i) ...
Вместо new Node использовать deque.push_back() && return &deque.back()
Но обычно этим не заморачиваются и делают такие тест кейсы, чтобы твой перебор не влез даже с байтоебскими оптимизациями (ну это в нормальных контекстах)
> Он тут не будет скорее всего умножать m на n много раз, а сделает типа
> int mn = m n;
Да. Эта оптимизация называется hoisting.
В идеале надо читать книги по архитектуре компьютеров и по компиляторам, но на контестах почти всегда можно обойтись без этих знаний. Иногда выстреливает, у меня было несколько примеров.
Например, была задача про дерево с N = 400000. Я подумал, что N какое-то большое и зачем авторы так сделали. Понял, что стэк может переполниться и сделал обход дерева не через рекурсию, а помещая номера вершин в очередь.
В другой раз я решал какую-то задачу через linked list и там были запросы, в результате которых могла создаться новая нода в листе, а могла и не создаться. Запросов там было 100000, но задача не прошла. До сих пор не уверен в чем дело, но видимо в том, что динамическое выделение памяти занимает много времени. Вот если бы компилятор видел, что я подряд в цикле выделяю, он бы соптимизировал и сразу выделил сколько нужно, а там были запросы. Потом я понял, что затупил, и что можно заменить linked list на deque, и задача прошла, потому что deque устроена как массив, который при необходимости увеличивается во сколько-то раз (в 2, кажется), соответственно, делается всего log N запросов на выделение нового участка памяти.
Еще была ситуация, что я решил писать код через лямбды, а компилятор какую-то лямбду скомпилировал во что-то хуевое, задача не проходила. Заменил на императивный вариант и прошла. С тех пор на контестах я все пишу в императивном стиле.
>linked list
>Запросов там было 100000, но задача не прошла. До сих пор не уверен в чем дело
Может имел место произвольный доступ к элементам списка?
>компилятор какую-то лямбду скомпилировал во что-то хуевое
Вообще пушка.
Ты сам смотрел на ассемблерный код, или просто так ляпнул что-то от балды? Я думаю, что ты просто не знаешь С++ и пишешь чушь.
> Ты сам смотрел на ассемблерный код
Зачем мне смотреть, если я и так знаю, что лямбды могут сконпелироваться в хуйню и не только в плюсах. Заменил лямбду на эквивалентный императивный вариант и зашло. Какой тут еще вывод можно сделать?
>>982673
Нет, там только в начале и в конце добавлялись элементы.
>если я и так знаю
Короче не слушайте этого шизика, он где-то как-то обжёгся на лямбдах (небось не отличает [=] от [&]), а обосновать или привести примеры не может.
Чтобы не стать такими как он всегда докапывайтесь до истины, если видите, что что-то не работает, а не "ща тут cout вставим чтобы глючить перестало"
> &deque.back()
Такие ссылки не инвалидируются при новых пушбэках? Или как-то можно указать, чтобы дэк на основе связного списка генерировался? Но тогда какая это оптимизация, если всё равно при каждом добавлении системный вызов.
Ну не скажи. Разница между O(n) и O(n log n) весьма призрачная, и оптимизированный логарифм может работать быстрее, чем линейное решение, особенно если у него константа пожирнее.
Изредка даже O(n^2) вместо O(n) может зайти, если тесты слабые, либо такое решение, что для него тест непросто придумать, особенно заранее, не зная решение.
Конечно, чаще проще решить по честному, но сдать задачу, не решая, тоже весело.
Ты вообще представляешь что такое deque в С++? Как он внутри устроен? Почитай cppreference прежде чем такие вопросы задавать.
Ходил на курсы в академю ШАГ, но там скучно был и я вместо занятий ходил к твоей мамке заниматься любовью.
Вы видите копию треда, сохраненную 23 мая 2017 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.