Решать на тимусе задачи по сложности от самых легких до сложных?
Все знают, что такое счастливый билетик.
Например:
123456
Сумма первых трех 5, сумма последующих 15. Билет несчастливый.
111003
Сумма первых трех чисел 3. Сумма последующих чисел 3. Билет счастливый.
Задача, посчитать сколько счастливых билетов между 100000 и 999999.
Выиграет самый красивый код.
Например:
123456
Сумма первых трех 5, сумма последующих 15. Билет несчастливый.
111003
Сумма первых трех чисел 3. Сумма последующих чисел 3. Билет счастливый.
Задача, посчитать сколько счастливых билетов между 100000 и 999999.
Выиграет самый красивый код.
print(50412)
Шах и мат
Шах и мат
знатное говноедство, даже я уважаю
[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
Cамый годный вариант на чистом си
Так ты на код смотри, а не на расширения файла
Просто CLion все проекты считает как C++
>codeforces.com
вроде отослал один, а он сыпится. нихуя не понимаю, где фак? ввод бинарный чтоль?
нет, все там в порядке
кидай свой код, может ты просто не умеешь в считывание значений
да вижу тут есть запускалка, потыкался, я так понял он в sdin пихает, а не в стартовые ключи - как я думал. хотя вроде логично, ведъ программа после ввода должна умереть?
вот ещё момент не вкурил: есть ли гарантия что 1 read вернёт мне весь ввод или нужно ещё дрочить всё ли ввелось? видимо да чёт приуныл
А смысл какой их решать?
В стартовые ключи это как. Там есть задачи с мегабайтами инпута, ключами не обойдёшься.
Твоя задача вывести правильный output и вернуть EXIT_SUCCESS.
Для интереса, это в основном хобби. Есть побочные профиты типа "в яндексе любят олимпиадников". Для школьников также помогает попасть на всякие бюджеты, ещё проводятся соревнования с неплохими призами, но это надо сильно угореть по теме.
я вот просто хочу подрочить байтики. на время - не интересно.
>Там есть задачи с мегабайтами инпута, ключами не обойдёшься.
ну наверно тоже верно, но можно было файлами заделать - а то ведь скорость будет сильно зависеть от того как реализован инпут в языке - а оно очень разнородно.
>хобби
Таки да, если не дрочиться по 2-3 5-часовый тренировки в неделю чтобы стать чемпионом мира.
Школьнику однозначно имеет смысл угореть, я сам жалею, что не хватало мотивации/не всегда мог себя заставить ботать в школьном возрасте, победителя всероса а не призера взял бы с легкостью. Все равно это лучше чем проебывать время на каэску какую-нибудь.
Поступление в любой топовый универ халявное, опять же.
Студентам активно задрачивать смысла нет, если не целиться на финал АСМ. Но таки полезные эффекты в виде "быстро решать задачки на собеседовании в Yandex/Google" возникают.
Ну еще, если не совсем донный, да и универ не совсем парашный, можно нахаляву за счет универа то есть ездить по всяким соревнованиям как и в пределах рашки, так и заграницу.
Раньше делали с файлами, но постепенно от этой практики отказались, может быть чтобы полностью избавиться от еботни с правами доступа. Кроме того, тебе же удобнее, сколько WA было получено на неверном названии файла… Причём в некоторых случаях это оказывалось решающим фактором.
СЪЕЗДИЛ НАХАЛЯВУ
@
В ПЕТРОЗАДРОТСК
Ну да, это само собой. А еще Москву, Париж, Будапешт, Белград и Катовице (Польша). И везде билеты + проживание - за счет универа
А сейчас люди получают WA на том, что ОЙ А ТУТ ФАЙЛЫ НУЖНЫ. Или ОЙ Я ФАЙЛЫ НЕ ЗАКОММЕНТИЛ (хотя нормальные пацаны юзают препроцессор для этого).
Хотя без файлов таки удобнее, да, жаль, что не везде так сейчас
Добавьте в шапку http://dl.gsu.by/
Сайт крут тем что там дохуй задач и он показывает количество пройденых тестов. Даже на сами тесты можно посмотреть.
Сайт крут тем что там дохуй задач и он показывает количество пройденых тестов. Даже на сами тесты можно посмотреть.
но вооще, где-нибудь в лине можно было бы перехватывать пару функций в libc и на любое имя файла давать один путь. наверняка и в винде такое можно провернуть.
Самый опущенный тип айтишников это олимпиадники.
> объявление счетчика цикла for в цикле for
> чистый Си
Опа, дед вылез.
Толсто.
В Москву эту куда, на МФТИшные сборы да на четверть, если рядом живёшь?
Да, МФТИшные сборы, они самые. Сам из Питера, поэтому четверть пишу у себя
сап, вопрос такой
вот на соревах стоят ограничения по памяти
но
в jvm языках же сама jvm автоматом отжирает до пизды памяти
получается jvm-блядки априори сразу сосут?
вот на соревах стоят ограничения по памяти
но
в jvm языках же сама jvm автоматом отжирает до пизды памяти
получается jvm-блядки априори сразу сосут?
Да. Алсо, ты ещё забыл про инициализацию машины, тоже время отжирает. Выбор языка в любом случае за тобой + ситуации, когда задача решается на С и не решается джавой, крайне редки.
олсо я совсем зеленый не понимаю пока как вкатиться
видел советуют книгу Шеня, она ок?
видел советуют книгу Шеня, она ок?
Это в случае, если ТЛ для Джавы стоит раза в 2 больше, что некоторые Online Judges делают по дефолту. А вообще зависит еще и от автора. Если он напишет какое-то заоптимизированное решение на плюсах и поставит жесткие ТЛи чтобы отсечь другое решение с чуть большей асимптотикой, то Джавакодеры соснут
Иди сразу на кодфорсы, читай параллельно емакс, дорешивай задачи и читай разборы. Для начала сойдёт, когда дело дойдёт до уровня суфавтоматов, уже сам разберёшься, что делать.
СОКОБАН)))0)
Зачем нужно олимпиадное программирование, если все держится на библиотеках и фреймворках? Оно же абсолютно не нужно в реальном мире. Лучше потратить время не на подготовку и дрочку алгоритмов, а на прикладную разработку и на свой гитхаб.
В спортзал и к стилистам всех четверых. Футболки блядь на халка, пошить соразмерные. Крайнему слева в жопе похудеть, перестать жрать говно, перейти на салатики и мясо. Бородачу как минимум выровнять бороду.
друг, где читать разборы? я заходил на рашен кап чето там, но там объяснение мне показалось уже для чуваков которые прорешали пару десятков контестов
На кодфорсах почти к каждому контесту пилят разбор авторы. Кроме этого, не стесняйся в случае чего спрашивать в комментах: пост вынесет на первое место в секции комменты, его увидят и ответят с вероятностью 99%.
>абсолютно
Радикально. В многих областях алгоритмы необходимы, пусть и не всем разработчикам.
Котёнка лучше не трогать, где ещё такое встретишь, при том что он относительно молод.
Писали же кучу раз
Школьникам есть однозначные профиты которые не очень сложно получить, да и олимпиадки на таком уровне таки сильно влияют на прогерские навыки
Студентам - хобби, помощь на собеседованиях.
Да и полезно таки некоторые алгоритмы писать самому, чтобы понять как работает что-то. Опять же, навыки писать оптимальный код на плюсах
Я не говорю про алгоритмы, они то очень нужны, я говорю про олимпиадную дрочку, которая вырабатывает плохой стиль кода (попробуй попиши читаемый код на время) и бесполезна в реальном мире.
А, ну в этом плане может быть.
Могу поспорить по следующим пунктам:
1. В целом развитие понимания, как всё работает, неасимптотическая оптимизация как, например, std::ios::sync_with_stdio
2. Навык дебага сложных конструкций.
3. Умение писать код быстро и правильно, то есть держать в голове много деталей
Отдельно скажу, что после многих лет олимпиад в проектах всё пишу максимально красиво, по другому уже и не хочется, но тут уже у всех своё. По крайней мере можно сказать, что само понимание красивого кода приходит после взаимодействия, а лучше написания некрасивого.
>как, например, std::ios::sync_with_stdio
Хуевый пример, если честно. В реальной жизни хрен понадобится
Хуёвый, но про плюсы тут особо ничего и не расскажешь. Хотя в целом вопрос I/O в C/C++ довольно занятный.
Вот про питон можно долго говорить, там абсолютно неочевидные вещи происходят.
Ребят, а я вот наоборот олимпиадник, а в промышленном полный ноль :с
Че ты врешь?
Ну ты же наверняка понимаешь почему так, или есть хотя бы предположения.
Просто не нравится?
Вполне вероятно, что ты просто мало промышленно кодил, тогда это нормально. В олимпиадках ты ж тоже не сразу начал норм участвовать наприер
>Конкретная математика
первая же задачка - мой пердак в небесах, ответ на неё - подлетаю к юпитеру. это просто пиздец какой-то.
Не смог решить вторую по сложности с начала задачу на тимусе.
Задавайте свои ответы
Задавайте свои ответы
обратный корень?
она сложная так-то, там на пушбэк поп
что такое пушбэк поп?
я на си пытался решить
Блять, ты тролль или ты серьезно?
Пиздец просто, >на пушбэк поп
Техника имени Семена, блять. Это как про любую задачу сказать "это задача на инт мейн", поеботень полная
Тебе надо знать, что такое массивы, как считывать-выводить вещественные числа, и как извлекать корень.
Первое - это лучше погугли и почитай в нормальном месте туториалы по языку, если таких основ не знаешь
Второе - считывать так:
double a;
scanf("%lf", &a);
и писать
printf("%f", a)
На самом деле, это верно для 11+ стандартов, в старых стандартах и читать и выводить с помощью %lf вроде
Третье это
#include <math.h>
...
a = sqrt(23.9);
кинь задачу
Я максимум решал 1010+ сложности на тимусе. Я успешнее
Как найти кратчайший маршрут между двумя вершинами в бинарном дереве?
Что такое бинарное дерево?
Я не понимаю зачем обсираться в присядку, одновременно обмазываясь говном и дрочить на коколимпидаки и нахуй не нужные алгоритмы
>Что такое бинарное дерево?
На пике.
>единственный маршрут
Из 9 в 2 можно идти пом пути 9 4 2 1 2.
>Находишь всех предков обоих вершин.
Не эффективно. Должен быть способ быстрее.
пик забыл
А нет его в памяти. Даже размер не известен. но в long long влазит. Выглядит как на той картинке. Наверно просто максимальный надо делить на 2 пока они не сравняются.
Числа между которыми маршрут прокладывать. Вывести нужно сам маршрут.
>Похоже, что это задача на пушбэк.
Скорей всего на int main() и return.
Ага. И я уже понял как решать. Поэтому спасибо и пока.
Ну это же не вся задача.
на пике моё предыдущее решение которое в спешке писал
1. В любом дереве маршрут всегда единственный, иначе бы там были циклы.
2. Задача сводится к нахождению наименьшего общего предка двух вершин, которую можно решить например алгоритмом Тарьяна.
То, что все лошади одной масти, можно доказать индукцией
по числу лошадей в определенном табуне. Вот так:
„Если существует только одна лошадь, то она своей масти,
так что база индукции тривиальна. Для индуктивного пере-
перехода предположим, что существует п лошадей (с номерами от
1 до п). По индуктивному предположению лошади с номера-
номерами от 1 до п — 1 одинаковой масти, и, аналогично, лошади с
номерами от 2 до п имеют одинаковую масть. Но лошади по-
посредине с номерами от 2 до п — 1 не могут изменять масть в
зависимости от того, как они сгруппированы,—это лошади, а
не хамелеоны. Поэтому в силу транзитивности лошади с номе-
номерами от 1 до п также должны быть одинаковой масти. Таким
образом, все п лошадей одинаковой масти. чтД*
Есть ли ошибка в приведенном рассуждении и какая имен-
именно?
просто это математика, мне сложно, нужно по другому мыслить, немного перестроить голову.
Это же очевидно, неверная база индукции. Самый первый переход для n=2 не работает, базой должен быть именно этот случай, что невозможно.
Тарьян offline, лучше всё-таки на sparse table делать.
Сап, посоны, пишу алгоритм Дейкстры. Что я делаю не так? Должно выводить 24 3 15, а выводит 24 32 20. Нумерация вершин с единицы.
https://ideone.com/eGhmMK
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 координатами. Как определить, находится ли точка внутри какого-либо многоугольника?
На двумерной плоскости имеем набор многоугольников с float координатами. Как определить, находится ли точка внутри какого-либо многоугольника?
Отклеилось.
Да, вспоминаю про трассировку луча. Но тогда ведь нужно проверять каждую грань каждого многоугольника?
Хотя можно применить небольшую оптимизацию и проверять только те многоугольники, с проекциями которых есть пересечения. Или еще лучше, с проекциями сторон которых есть пересечения.
В общем, спасибо, навел на мысли.
Точнее мы тут можем даже до одного сократить.
Если они выпуклые, то для каждого многоугольника можно делать проверку за log(число вершин)
Если задачу на кодфорсе взломали, то это хорошо т.к. она бы завалилась на основных тестах, а так есть возможность узнать об ошибке и доделать её?
Именно так, если ты ее не заблокировал, конечно
Когда разбор сегодняшнего кодфорса запилят (див2)? Где его смотреть?
Там разборы бывают? А див1 есть?
Вот тут сказали, что бывают:
Я хз, сегодня впервые написал.
Чо, обидно, со второй задачей вышло?)))
Проще, но на этот способ любят делать контртесты. Надёжнее пускать в рандомном направлении.
Я всегда использовал сумму полярных углов. Тема такая, для каждой грани ты считаешь, под каким ориентированным углом она видна из точки. Дальше считаешь сумму, если получилось 0, то ты снаружи, если 360 градусов – внутри. Случай на грани рассматривается отдельно.
Бывает, что ломают решения, которые не валятся на тестах.
Разбор появляется от сразу до нескольких дней, пали комменты к посту о контесте, там обычно спрашивают такие вещи.
мне сложно, а вот если есть задача - я могу её решить, как там написано, и так же индукцией доказать - не проблема. но когда меня спрашивают, например докажите что в задаче на столбы, используются все возможные комбинации - вообще не ебу как. да, для меня очевидно, что вот число и его бит может иметь 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 <- это
или что под этим ещё понимается?
> T(1) = 2
2 справа бы трахнул нет
Т.е слева -_-
Ничего не понял, кинь условие задачи, или что ты там доказываешь.
>Грэхэм, Кнут, Паташник "Конкретная математика"
Этой книги достаточно, чтобы понимать анализ алгоритмов, всякие асимптоты и прочее из следующей книжки? Или придется до кучи ещё математики наверстать? Мой уровень если что на уровне девятиклассника, лол.
Угу. А асимптотика там обсуждается аж в последней главе.
Как я и думал, все эти алгоритмы и интеллектуальные игры с ними для элиты, которую с рождения обучают не тому, что дают в обычной быдло-школе. Пойду дальше в дотку катать.
Просто начни с книжек попроще. "программирование: теоремы и задачи" Шеня, а потом вот это http://codeforces.com/blog/entry/12314
Ну и перед этим учебник школьный по математике, если совсем неуч.
Спасибо. Я настолько тупой, закончил школу, а не могу решить задачи с acmp.ru которые сложнее 30% по их шкале.
Зарегался на этом вашем кодефорсес. Где там выбирать задачи по уровню сложности и тематике?
Алсо, есть там что-нибудь по преобразованию Фурье?
Алсо, есть там что-нибудь по преобразованию Фурье?
Есть задача "ДНК роботов", поищи по названию.
>Бывает, что ломают решения, которые не валятся на тестах.
Ну вот. Ты меня запутал. Чётно обфусцирую решение на следующем контесте, а нечётно нет.
После множества таких казусов с недавних пор все успешные похеки добавляются в набор финальных тестов.
круто, жаль что я не видел этого в школьном возрасте
Есть ли простой алгоритм быстро возвести матрицу в квадрат?
Вот две произвольные матрицы либо за эн в кубе умножать, либо хитрый алгоритм. А тут может попроще?
Вот две произвольные матрицы либо за эн в кубе умножать, либо хитрый алгоритм. А тут может попроще?
Нет, нельзя, насколько я знаю. Есть только, как ты сказал, хитрые алгоритмы, либо частные случаи типа метода четырёх русских.
Ну у меня вот как раз частный случай, две одинаковые матрицы умножаем.
Я понимаю, вот и говорю, что я, по крайней мере, никогда о таком частном случае ничего особенного не слышал. Пиши Штрассена или гугли научные статьи на эту тему.
Впрочем, можешь ничего не гуглить, вот ответ на твой вопрос 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.
Аноны, подскажите алгоритм: дано произвольное количество 2d-вершин, нужно из них сделать многоугольник с непересекающимися гранями.
построение выпуклой оболочки
Вроде это не совсем то. Все точки должны быть задействованы.
Я написал примитивный алгоритм: проходим по точкам, отсортированным убывающе по y, и соединяем ближайшие по x, но иногда он фейлится.
Берёшь самую нижнюю-правую точку, ставишь её как начало координат. Считаешь полярные координаты остальных точек относительно центра. Сортируешь по углу, обходишь в этом порядке.
Дядя Сэджвик с Курсэры так учил
Я походу проще вариант нашел: пространство делится на 2 части по x (можно взять тупо width/2), слева и справа строятся ломаные кривые и потом соединяются.
>ломаные линии
Хотя тупо width/2 будет ошибкой, нужно чтобы хотя бы 2 точки было на одной из сторон.
Хотя нет, полностью неправильно, лел.
Ладно, буду думать.
> эти плечи
хуйня решение же очев
матрас из денег всё справит
Все нормас, быстрейшее из всех, O(n).
Проблема была только в разделении. Надо делить линией, которая проходит через самую верхнюю грань и через самую нижнюю. Теперь все без ошибок.
Теперь докажи корректность.
По-моему у тебя просто жадная эвристика.
Я думал о корректности.
Из любого набора разных точек можно сделать ломанную линию с непересекающимися кусками, соединяя точки одна за другой в одном направлении. Пересечений гарантированно не будет, если между точками в этом направлении нет других точек.
Мы получаем две ломанных линии, не пересекающиеся между собой. Вопрос только в том, можем ли мы безопасно соединить их концы. Ответ: да, т.к между концами больше нет других точек, т.к. мы заведомо взяли 2 верхние и 2 нижние точки и от каждой начали строить линию.
И все же это не n, а nlogn, т.к. надо сначала отсортировать точки в одном направлении.
Занятно, я всегда пользовался сортировкой по полярному углу. Сложность такая же, но алгоритм ка будто чуть попроще, нет двух частей, тупо сортировкой сразу достигаешь нужный порядок с другой стороны, может быть критична скорость работы с float
Mathematica
(1/Pi) Integrate[((Sin[10x] )/Sin[x])^6, {x, 0, Pi}]
Счастливых билетов: 55252
(1/Pi) Integrate[((Sin[10x] )/Sin[x])^6, {x, 0, Pi}]
Счастливых билетов: 55252
Элегантно, только погрешность численного интегрирования точность подпортила.
А вот в таком случае ты что делаешь? Чёрное - как получается по твоему описанию, зелёное - как должно быть.
В этом: https://www.hackerrank.com/w22 кто-нибудь участвует?
А интегрирование аналитическое, без погрешностей.
Хотя если оценить вид первообразной и по пределам оборвать, то можно свести все к вычислению 1109369452791600/20078358300
Зо o(n) низя т.к. если можно то можно числа за o(n) сортировать а так низя потому что низя
Нет, все верно у меня.
Главное не ошибиться с выбором лево-право у крайних отрезков. Я сначала выбирал тупо - если 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к символов. А вот время нужно экономить т.к. важна каждая миллисекунда.
Как решить?
Пример
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, само по себе оно не обновится.
Анончики, может у кого есть нормально отформатированная Конкретная математика в mobi/epub или прочем ebook формате? Я искал, форматировал и все тщетно. А пдф читать на 6 дюймовом киндле не шибко удобно и приятно. Заранее спасибо за ответ.
Вчера писал свой первый раунд на Codeforces, почувствовал себя дауном. Первая задача простая, ну действительно, чего ее решать, давайте посмотрим остальные. Вторая про графы, чет как-то слишком длинное условие, сложна. Третья про пифагоровы тройки. И тут я засел. Родил какое-то стремное решение через числа Фибоначчи (спасибо Википедии за это), а оно зависает на всех нечетных, а на четных выдает не всегда верные ответы. В итоге два часа просидел над этой задачей, ничего не решил, а когда открыл разбор - охуел от простоты и изящества. Это лечится или мне навеки оставаться тупым?
Поступил на программиста, называется.
Мама, мама, я буду кодить!
лечится. одноклассник не умел решать ничего кроме 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, я не понимаю.
> а когда открыл разбор - охуел от простоты и изящества.
Какое изящество, тут просто надо знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает, это знают только всякие дрочилы, которые нарешивают олимпиады по математике для школьников.
А если какие-нибудь методички, в которых подобные тайные знания раскрываются?
Не трать на это время, это полная хуйня. На cf есть нормальные задачи на какие-то определенные темы, решение которых помогает в понимании этих тем. То есть это задачи на какие-то алгоритмы или структуры данных, а не на знание того, что нечетное число можно представить в виде разности квадратов. Просто нужно уметь отличать хуету от нормальных задач.
скиена "олимпиадные задачи по программированию"
Я как-то хантился в майкрософт, к Дену Расковалову.
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
Как в Си вычислить корень 876652098643267843 ?
http://ideone.com/XVSbT2
long long int a;
самспросилсамответил
Пиздец быдлокод.
ХОДИШЬ ТАКОЙ НА ОЛИМПИАДЫ, БЕРЕШЬ ПРИЗОВЫЕ МЕСТА
@
ПРИГЛАШАЮТ РАБОТАТЬ В ЯНДЕКС
@
ПОСЛЕ НАПИСАННОГО ТОБОЙ ОБНОВЛЕНИЯ У ВИНДОВС ПОЛЬЗОВАТЕЛЕЙ СЛЕТАЕТ ВИНДОВС СО ВСЕМ СОДЕРЖИМЫМ ДИСКА Ц
@
С ПОЗОРОМ УВОЛЬНЯЮТ
@
КАРЬЕРА В ИТ ДЛЯ ТЕБЯ ЗАКОНЧЕНА, ПИЗДУЕШЬ РАБОТАТЬ ДВОРНИКОМ
ПОСЛЕ ПОДМЕТЕННОГО ТОБОЙ ПОДЪЕЗДА ПОЛОВИНА ЖИТЕЛЕЙ ПОСКАЛЬЗЫВАЮТСЯ И ЛОМАЮТ НОГИ
@
С ПОЗОРОМ УВОЛЬНЯЮТ
@
НЕ ОСТАЕТСЯ НИЧЕГО ДРУГОГО, КАК СТАТЬ НАЕМНЫМ УБИЙЦЕЙ ЗА ДОЗУ ГЕРОИНА
@
ЦЕЛЬ ИЗЛЕЧИВАЕТСЯ ОТ БОЛЕЗНЕЙ ПОД ТВОИМИ УДАРАМИ
@
ВЫГОНЯЮТ БЕЗ ПЕНСИИ
Рекурсивная функция в две строки, решающая одну из первых задач с тимуса. Что доебался до него?
Разве что while я заменил бы на простой if
На джаве кто-нибудь пишет? Поможете сопитимизировать? У меня TL.
http://codeforces.com/contest/709/problem/E
http://pastebin.com/pW573vzV
Время работы там O(n), в этом точно косяка нет. Я заменил рекурсию на while + stack, потому что до этого был stack overflow. То что инпут с помощью Scanner - это норм, потому что если бы инпут не успевал, у меня бы не доходило до stack overflow в первой версии. От лямбд я уже пробовал избавляться, тоже TL.
http://codeforces.com/contest/709/problem/E
http://pastebin.com/pW573vzV
Время работы там O(n), в этом точно косяка нет. Я заменил рекурсию на while + stack, потому что до этого был stack overflow. То что инпут с помощью Scanner - это норм, потому что если бы инпут не успевал, у меня бы не доходило до stack overflow в первой версии. От лямбд я уже пробовал избавляться, тоже TL.
Хотя сейчас замерил, инпут занимает 2 секунды. Сейчас попробую сканер заменить на что-то побыстрее.
Широковаты. Я от своих тоже в бугурт впадаю.
Оберни System.in в BufferedReader
Сделал. Сначала не сдалось, но потом я еще обернул System.out в BufferedOutputStream и сдалось.
Поясните зашквар или нет вставлять в резюме ссылку на свой профиль на codeforces? Устраиваюсь не в какой-нибудь яндекс, а обычным крудошлепом.
Какой рейтинг?
Не понял. А почему 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
Это шутка была (про то, что все знают, что такое комбинаторный интеграл). Но то, что (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
Подсказка: интегрирование по частям.
А комбинаторный интеграл это понятие тесно связанное с комбинаторной производной.
Комбинаторная производная определяется так: 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 ведёт.
Так ли это?
Нет, я сомневаюсь, что Егор будет вести курс по Android в сраном МИРЭА.
> 5 лет назад
Тогда была другая система рейтинга, так что на тот момент он был прав.
Самолет взлетает в X (целое, 0<=X<=23) часов по местному времени в часовом поясе номер M (целое, 0<=M<=23). После полета в течение K (целое, 1<=K<=12) часов он приземляется в часовом поясе номер N (целое, 0<=N<=23). Определите местное время в пункте приземления. Считать, что часовые пояса нумеруются с запада на восток.
Тупая задачка. Почему нельзя просто прибавить ко времени старта врем полета, а потом прибавить разность номеров часовых поясов?
Тупая задачка. Почему нельзя просто прибавить ко времени старта врем полета, а потом прибавить разность номеров часовых поясов?
Все, разобрался. Идите нахуй
А кто тебе сказал, что нельзя? Летал самолет или нет, значения не имеет, от этого разница во времени между часовыми поясами не изменится. Здесь просто спрашивается, какое время будет в другом часовом поясе через n-цать часов. И какое все это имеет отношение к погромированию?
Эй, умники. Есть задачка. У нас имеется n целых неотрицательных чисел, чья сумма не превосходит 10^5. Еще есть некое m до 10^4. Все эти n чисел мы хотим представить в виде целых долей этого числа m, причем нецелые доли мы вольны округлять в любую сторону по желанию левой пятки. Я тут набросал тупой жадник, который, конечно же, доказывать не умею, и он отхватывает wa2. Жадник настолько тупой, что он все округляет вверх, а потом, переокругляет вниз пока не получим нужную сумму, равную m
http://ideone.com/3x53a2
http://ideone.com/3x53a2
Дай ссылку на исходную задачу, потому что ты во-первых написал условие как мудак (блядь, неужели нельзя скриншот запостить хотя бы, и пару примером входа выхода), а во-вторых лучше засабмитить, чем какому-то петуху объяснять.
Ну, вот тебе скриншот. А самой задачи на публичных тестилках я не видел. Свой жадник пока что я опровергнуть так и не смог
Ну вот так-то лучше. Сам-то чувствуешь, что гораздо понятнее выглядит? Очевидная динамика же.
Я, конечно, толком в динамику не умею. Но тут и намеков не вижу. Не просветишь?
Хотя тут даже динамика не нужна, жадный алгоритм должен работать. У тебя, наверное, просто не проверяется, что если число нацело делится, то его двигать нельзя уже.
Так ceil же не должен целое число округлять. Или там с точностью может быть лажа?
Ну динамика, если интересно, такая: f(arr[i:], amount) - можно ли набрать amount сумму, округляя как-нибудь числа начиная с i-й позиции, как в рюкзаке, и по времени проходит - 50е6. Только, повторяюсь, она тут не нужна.
А ты потом даже от целых чисел берёшь и отнимаешь 1 на 25-й строчке.
Высрал контрпример http://ideone.com/kRzC4I
Не канает, см
Да. Я уже вижу. Спасибо, мил человек
Сколько сюда не захожу, так и не пойму, чем вы тут занимаетесь
Почему бы и нет.
Спортом вестимо.
> Спортом вестимо.
Игра в доту — это спорт. Решение олимпиадных задач по программированию — это не спорт. Выводы делай сам.
У всех cf лежит?
Нет
Пидора ответ.
Как научиться решать CTF?
Приходишь на ctf. Дальше все понятно.
Серьезно. Обычно есть отборочные туры, где есть возможность гуглить
Ладно. А что там знать и уметь надо?
Идешь на отборочный тур и узнаешь. Там бывают разные задания: криптография, сети, крекинг етц
Олимпач, я тебе задачу подвез. Пока из идей посортить стержни по максимальному расстоянию от конца до точки d, а потом как-то хитро посчитать. Хитро что-то не выдумывается
Допустим все числа нечетные, тогда просто расположим их так, чтобы их середины находились на оси x и будем зажигать от самого длинного к самому короткому. Допустим, нечетные, тогда то же самое.
Допустим есть четные и нечетные числа. Например, 2 стержня 4 и 5. Тогда придётся все числа той же четности, что и максимальное, зажечь с одного конца, чтобы сделать всех одной четности, а потом применить алгоритм из первого параграфа.
С четными и нечетными я хуйню написал.
Короче зажигаешь самый длинный стержень с двух сторон, а дальше изъебывайся как хочешь, но чтоб все в один момент лопнули. Это можно сделать.
В первую секунду зажигаешь самый длинный стержень с двух сторон, а стержни длины на 1 меньше - с одной стороны, во вторую секунду все стержни которые горят с одной стороны поджигаешь со второй, а все стержни на 1 меньше - с одной стороны. И так далее.
Вот это вот, судя по всему, верное решениие
А, там ещё и определённая точка должна загореться последней, вот я мудак.
ты ебанулся? база индукции очевидно верная. переход не верен (при п=2)
Я умею искать гамильтонов путь в неорграфе динамикой по подмножествам, где вершин не больше 20. А вот теперь мне надо проверить наличие гамильтонова пути в ацикличном орграфе с количеством вершин вплоть до 10^5. Вроде простая задача должна быть. Думаю пока в сторону топсорта какого-то
Сравни длину длиннейшего пути с количеством вершин + 1.
https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths
Честно говоря не понимаю зачем пишут топсорт делать. Наверное чтобы достичь O(N) вместо O(N*log(n)).
По идее достаточно для каждой вершины предрасчитать списки входящих соседей (если вершин с пустым списком >1, то гамильтонова пути сразу нет), а потом пока есть нерассмотренные вершины берёшь рандомную считаешь расстояние от истока до этой вершины как максимум среди её входящих соседей+1. Применяешь алгоритм рекурсивно, не забывая про мемоизацию.
Короче как поиск кратчайшего, только длиннейшего.
Эх, щас бы в 2016 перебором задачу решать, вместо динамического программирования
Да, спасибо. Я пытался делать дфс, который брейкается, когда глубина рекурсии становится равна количеству вершин. Но как-то это получало ва5.
Ты же понимаешь, что твои идеи на порядок сложнее и для осознания, и для написания. Топсорт - это одна строчка в дфсе
Окей. Как быстро проверять достижимость каждой вершины из каждой по матрице достижимости? Вершин всего тысяча, но флойд не вариант, потому что там сверху еще будет логн от бинпоиска висеть. Граф плотный, поэтому бфс меня тоже смущает. Или нормально?
В матрице достижимости все элементы должны быть равны 1.
Действительно. Но это я, наверное, плохо выразился. Я еще подумаю, пожалуй
Исходную то задачу расскажи.
Я, кажется, придумал, что хочу по матрице смежности быстро строить матрицу достижимости
Подсказка, попробуй отсортировать ребра по весу.
Пиздец я проебался, думал граф неориентированный, тогда это просто бинпоиск и SCC
Нужны две функции. Одна принимает английский неправильный глагол, а возвращает его первую форму, а вторая получает рандомное слово и составляет кучу других слов из таких-же букв. Какие есть способы это сделать быстро?
BFS/DFS, компоненты связности. Предподсчёт за V^2, дальше ответ за 1.
бумп
Пререквизиты для Кормена и Кнутопаташика есть ли? Скожите пожалуйста.
Для Кормена только мозг нужен, ну там подумать иногда придётся. Кнутопаташника не читал.
У Кормена есть в конце книги поясняется за математику
Парни, есть какой нибудь сайт, где перечислены основные олимпиадные алгоритмы? А то я знаю только викиалгоритмы, а он бесполезен для этого
e-maxx
огромнейшее спасибо
Что, как поживаете? Я вот тут недавно школьную командную олимпиадку писал. Суть в том, что я-то алгоритмов довольно много знаю, могу написать. Префикс, з функции, декартачи, до, всякие графы, хэши. Но, сука, проблема в том, что в команде я ничего не придумывал. Мне говорили: "пиши топсорт, потом проверяй наличие соседних ребер". Или: "Склей строчки, посчитай префикс функцию, пока суффикс совпадает с префиксом, удаляй их. Я, бля, даже условия оригинального не знаю.
Это все круто, но на личной олимпиаде не проканает. Неумение быстро выдумывать решения - это приговор? Или еще есть шанс до феврали задрочить задачки из первой полутысячи тимуса?
Это все круто, но на личной олимпиаде не проканает. Неумение быстро выдумывать решения - это приговор? Или еще есть шанс до феврали задрочить задачки из первой полутысячи тимуса?
Есть программа с кучей функций. У каждой функции есть название. Известно количество обращений к каждой функции за последнее время.
Надо назначить функциям однобуквенные хоткеи так, чтобы сумма чисел обращений к функциям, которым назначены хоткеи, была максимальна.
Хоткеем функции можно назначить только букву, входяшую в её название.
Знаю про венгерский алгоритм, но у меня вес дуги из функции в каждую из допустимых клавиш одинаков. Есть ли что-то быстрее для такого случая?
Надо назначить функциям однобуквенные хоткеи так, чтобы сумма чисел обращений к функциям, которым назначены хоткеи, была максимальна.
Хоткеем функции можно назначить только букву, входяшую в её название.
Знаю про венгерский алгоритм, но у меня вес дуги из функции в каждую из допустимых клавиш одинаков. Есть ли что-то быстрее для такого случая?
на то в команде всегда и есть два прогера, один комп, и один математик который придумывает решения, сечешь?
Да. Но мне до студенческих командных нужно дописать личные олимпиадки, где один прогер и один математик в моем лице
Вы меня удивляете.
Пишу на крестах и пухтоне.
Последнее время само-собой приходится дрочить адгоритмизацию и математику, причем комбинаторику и статистику (что ненавижу, лучше дифуры).
Я чет не понимаю, как программист может не мочь в такое? Что за бред? Это как себя не уважать.
Пишу на крестах и пухтоне.
Последнее время само-собой приходится дрочить адгоритмизацию и математику, причем комбинаторику и статистику (что ненавижу, лучше дифуры).
Я чет не понимаю, как программист может не мочь в такое? Что за бред? Это как себя не уважать.
>адгоритмизацию и математику, причем комбинаторику и статистику (что ненавижу, лучше дифуры)
держите матаноблядь!11
>адгоритмизацию
А что это за дисциплина?
hellburnization is a part of CS
не все такие умные и не все так рано начинали, мне вот 30 лет и на тимусе у меня 50 задач, в школе был далек от программистов, даже не знал об этом, но как сейчас выяснилось тогда по матеше я обходил парней ныне уже участников финала мира acm icpc
>статистику
А что с ней не так?
Даже гуманитароблядки её усваивают.
Для программирования пруфы нужны ужО Штоле?
Спроси в machine learning треде.
Пишу алгоритм для игры. В ней нужно набрать максимум очков. Их количество не может уменьшаться. Есть фактор случайности. игра похожа на монополию и количество возможных исходов одного хода меньше чем у шахмат При этом игра может закончиться совсем неожиданно если неколько ходов подряд кубик будет плохо падать. Значит обычный minmax не подойдёт т.к. при большой глубине поиска лучший из худших всегда будет проигрыш. И что делать с линией горизонта? Ведь здесь нельзя форсировать поиск при шахе как в махматах. Реквестирую литературу про программирование ии для игр с влиянием рандома.
>обычный 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
Но это совсем из другой оперы
Но ты все-равно подумай про рандомизированные алгоритмы
Хорошо, спасибо. На паре по дискретной математике задали.:(
Вы че ебнулись? никак.
> никак
А доказать?
Руки бы тебе блять оторвать за такой код, хуесос
С трудом даются задачи из Конкретной математики. Это нормально? Продолжать задрачивать или прочитать что-нибудь полегче сначала?
А куда легче? Учебник за 5 класс?
Да, спасибо, подходит
анон, в какой порядке решать задачи на codeforces? самые популярные, новые, только A, B..., только div 2 или без разницы?
Отсортируй по количеству решивших. Начинай решать. Если чуешь, что очень легко идет, листай на следующую страницу
спасибо, так и сделаю
Ну че молчим, епта, давайте задачи решать
Если ещё не поздно, вот тебе подсказка: почитай как устроен raid5.
http://ideone.com/iTglQT
Ты внимательно прочитал условие?
Особенно про то, что размеры строк r^2, а памяти - r, и что она неперезаписываемая?
Да, задачка решается для строк размера r^2 , r бит неперзаписываемой памяти и r+1 запросе. Я думал, это очевидно.
Стандартная задачка егэ:
Из ряда натуральных чисел выбрать произвольное количество чисел так, чтобы их сумма не делилась на 6. При этом сумму надо максимизировать. На выход количество выбранных чисел и их сумму. Я не совсем ньюфаг в олимпиадном программировании, но тут встал в тупик. А егэ сдавать надо
Из ряда натуральных чисел выбрать произвольное количество чисел так, чтобы их сумма не делилась на 6. При этом сумму надо максимизировать. На выход количество выбранных чисел и их сумму. Я не совсем ньюфаг в олимпиадном программировании, но тут встал в тупик. А егэ сдавать надо
Динамическое программирование: f(i, c) = максимальная сумма подпоследовательности arr[:i], делящаяся на c.
s/делящаяся на c/дающая c в остатке при делении на 6/
Как насчёт взять все, а потом при необходимости выбросить наименьшее, не делящееся на 6?
Ну не томи тогда, рассказывай.
Я бы на твоём месте ещё подумал, задача-то простая. Но если совсем зашёл в тупик, то вот
http://lpaste.net/339079
Ввёл тебе за щёку.
Я понял задачу так, что обязательно использовать ровно r+1 запрос.
В таком случае возникает проблема, что на каком-то шаге мы можем обнаружить расхождение, но мы обязаны сделать остальные шаги, и непонятно как передать на эти шаги информацию о том, что различия уже найдены.
Нет, ты неправильно понял задачу. Обычно такие странные условия обговариваются. Например, было бы написано "сделав ровно r+1 запрос"
Думаю ты прав, держи няшку.
Может тут есть кто-нибудь, кто тоже участвует во всероссийской олимпиаде для 11 классов? Сейчас пробный тур проходит как раз.
И еще может кто-нибуд в технокубке участвовал? Какого уровня там задачи? Там вообще ебанутые какие-то правила с этими взломами, не знаю осилю ли я там хороший результат показать.
И еще может кто-нибуд в технокубке участвовал? Какого уровня там задачи? Там вообще ебанутые какие-то правила с этими взломами, не знаю осилю ли я там хороший результат показать.
Ну, участвовал в твоем технокубке. Из-за того, что не в том порядке стал решать задачи, занял не 70-какое-то, а 150 с хуем место. Не понравилось
Ебать, как такое делать? Пока что думаю запилить граф и перебирать по нему все варианты, но это же наверняка будет слишком медленно.
Хули тут думать-то, жадный алгоритм же.
Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i.
пиздец, деление и остаток от деления двумя операциями... Охуеть просто.
Ну а что ты хотел, я тогда только начал вкатываться в си и программирование вообще
>среди работ с дедлайном >= i.
А если таких нет, то ничего не назначать, а потом делать дополнительный проход, заполняя дни без назначений?
И как находить такие дни - поддерживать отсортированную по штрафу коллекцию, и в неё докидывать работы из заранее подготовленного списка работ, сгруппированных по дедлайну?
Мне кажется проще назначать день работе с наибольшим штрафом. Если есть свободные дни до дедлайна, то забираем последний. Иначе забираем последний из дней после дедлайна.
Какую теорию погуглить для олимпиадного программирования? Я просто совсем неадвно вкатился и пока что просто на логике всё делаю. Жадные алгоритмы, динамическое алгоритмы, что ещё?
Способы представления графов в памяти, DFS/BFS, алгоритм Дейкстры, комбинаторика на уровне итерации по всем перестановкам и сочетаниям, бинарный поиск, алгоритм Эвклида, решето Эратосфена, генерация пифагоровых троек, метод ветвей и границ.
На самом деле сам поймёшь что нужно когда будешь натыкатьсся на трудные задачи.
Как научиьься реализовывать алгоритмы? Смотрю в интернете всякие видео уроки по популярным алгоритмам, типа quicksort, но реализовать на языке который изучаю не могу. Сто делать?
Как научиьься выступать в суде защитником в деле об ебле козы бабы Нюры? Смотрю в интернете всякие видео уроки по выступлениям-заседаниям, типа quicksort, но выступить в суде в котором выступаю не могу. Сто делать?
Находишь в интернете реализацию ксорта на твоем языке. Понимаешь. Потом переписываешь, можно подглядывать. Как переписал, закрываешь. На следующий день без подглядывания пиши.
Спасибо.
Задвай себе вопрос "а что надо делать" и делай. Потом "а что теперь?" и так далее. После каждого такого шага чекай всё ли правильно работает.
Спасибо, няши
а как можно лучше?
divmod
тысячи способов, пиши какой удобнее.
> Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i.
И какая у этого алгоритмическая сложность? По-моему, не меньше O(N^2). Многовато.
Про кучу не слышал?
Продублирую тут, пожалуй.
Сап. Есть в треде алгоритмодрочеры?
Есть таблица связей в бд (postgres): юзер id - группа id.
Нужно выделить несколько секций юзеров (нужно, чтобы было максимум N юзеров в каждой такой секции), которые входят в группы "эксклюзивно".
Другими словами. Допустим N=1000. В секции #1 будет 10 групп, в которые входят только юзеры из этой секции, всего 980 юзеров в секции #1. В секции #2 будет 14 групп, в которые входят только юзеры из секции #2, всего 900 юзеров в этой секции. Всех остальных относим в последнюю секцию. Нужно найти такие вот секции, приблизительно.
Какой тут алгоритм применять?
Главное чтобы быстрее работало, какая-то точность разбития на секции (типа, чтобы максимально скомпоновать юзеров по N=1000 в секции) не нужна.
Пока вижу просто тупо ходить в цикле по группам (в порядке возрастания популярности групп, навеhное), собирать юзеров, пока не наберется 1000, после чего собирать следующую.
Сап. Есть в треде алгоритмодрочеры?
Есть таблица связей в бд (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 быть не должно.
Это строго обязательно? Это условие сильно усложняет задачу.
Сап. Я школьник, 10 класс. Алгоритмы знаю на уровне "quick sort, binary search, bfs, dfs, dijkstra". Такой вопрос - можно ли за год вкатиться в олимпиады так, чтобы получить хоть какие-то бонусы для поступления? И на что следует обратить внимание? Готов сидеть у книжек часами каждый день. Если что, пишу на плюсах.
>codeforces.com
>acm.timus.ru
>informatics.mccme.ru
>acmp.ru
>TopCoder.com
>etc
Скажите, а есть возможность на каком-нибудь из этих ресурсах сдавать задания на питоне?
Думаю можно. Выясни какие олимпиады тебе подходят, посмотри задачи прошлых лет. Нарешивай подобные задачи и читай теорию.
Да
Есть знакомые, которые из твоего положения и хуже брали себе потом диплом всероса, так что дрочи задачки. Посмотри на иоип, например
А подскажи, пожалуйста, на каком из них конкретно можно, если знаешь.
На топкодере вроде нельзя. Но вообще не надо писать олимпиады на питоне
Ты сам не можешь посмотреть?
на всех, даже etc
>Это строго обязательно? Это условие сильно усложняет задачу.
Да.
как самые популярные темы задач на codeforces? дп, жадные алгоритмы, графы, структуры данных...
что задрачивать, чтобы стать хотя бы синим?
что задрачивать, чтобы стать хотя бы синим?
На синего хватит простых графов, бинпоиска, качественного конструктива. Сложные алгоритмы начинаются после Ddiv2
спасибо
>Не надо писать на питоне
Почему?
>(c for c in str(x))
Достаточно просто str(x)
Спасибо
это сюда
Потому что рано или поздно ты столкнешься с тл. Мало где на олимпиадах гарантируют решабельность на питоне
> Как я уже написал, группы - это как группы в вк. То есть, например, соберу секцию #1, где будет группа любителей хентая 500чел + группа любителей гуро 400чел (из них 100, например, входят в группу хентая) + группа любителей golang 10чел. В других секциях любителей хентая, гуро и golang быть не должно.
> И т.д. Большие группы, типа мдк, где >1000чел, не входят в секции. Но их подписчики могут быть любителями хентая, гуро, golang.
Ну что же вы, бэтманы?
Я думал, в треде есть бородатые гики, что пояснят по хардкору, какой мне алгоритм нужен.
Сколько групп всего?
Если не больше нескольких тысяч, то можно представить их в виде графа, в котором две вершины соединены если в соотв. группах нет общих членов. Перебираешь в нём клики Броном-Кербошем, и когда находишь подходящую удаляешь её из графа. В принципе может и не обязательно хранить граф в явном виде, в конце концов проверить наличие дуги между группами можно глянув на пользователей.
Но лучше делай как я уже написал
>Выбирай очередную группу рандомом пока не наберёшь достаточно, делай несколько подходов, выбирай лучший результат.
Можешь ещё отранжировать группы по аутичности, то есть отношению количества пользователей группы к количеству других групп в которых они состоят (или суммарному количеству пользователей в которых они состоят). Начинать наполнение секции лучше с аутистов.
Вангую что результаты тебя огорчат из-за того что есть боты, вступающие в дохуярд групп.
Я вот вообще не пробовал олимпиадное программирование раньше, но опыта в пограммировании каких-то практических вещей и всякой хуйни у меня куча. И вот в этом году я неплохо так начал в него вкатываться. 11-класс
Кто-то сказал Данилюку, что это не кодфорс, чтобы решать с конца?
Анончики, не нашел ваш тред на нулевой и поднимаю этот, вроде бы актуальный.
Интересует решение задания "743D - Хлоя и приятные подарки" на codefoces
Разбор здесь http://codeforces.com/blog/entry/49049 , но я в упор не понимаю, как его реализовать.
Кому не лень и кто шарит, можете разжевать идиоту.
Интересует решение задания "743D - Хлоя и приятные подарки" на codefoces
Разбор здесь http://codeforces.com/blog/entry/49049 , но я в упор не понимаю, как его реализовать.
Кому не лень и кто шарит, можете разжевать идиоту.
бамп посту
Бампать последний пост, каеф
>я в упор не понимаю, как его реализовать
Там же решение на С++. Да и рекурсивное решение тупое как с перестановками:
Вывести все перестановки N чисел.
Перестановка N чисел - это перестановка первого числа и последовательности N-1. И так повторять пока N не будет равно 2, а два элемента переставить может даже школьник.
>решение тупое
>Вывести все перестановки N чисел.
На минуточку N до 2*10^5.
Вот если ты вообще не в теме, но нахуя лезть в каждую бочку затычкой?
ну рейт же, по-моему красиво.
Как лучше себя прокачивать? Мотивации изучать что то новое совсем нету. На codeforces голубенький.
Ну и все, нахуй тебе еще что-то? Или ты хочешь стать олимпипдником?
Да, я же школьник
На минуточку ты долбаеб, а первоначальная задача легко решается рекуррентно за n операций. Я же привел задачу намного сложнее, которая тоже легко решается похожим образом.
Толку в этих задачах все равно 0, а автора кода надо бить палкой по голове за такой код
Тогда у тебя дохуя мотивации. От халявного поступления в вуз и повышенной стипухи, до чемпионата мира в пендосии. Открыл книгу и начал читать, нахуй
анон, помоги решить задачу. https://puu.sh/sWIUR/cf666599d0.png
ну тут сразу понятно что вершины надо не удалять, а добавлять в обратном порядке.
дальше очевидный флойд уоршел
получается 500^3, норм тебе?
только смотри не объебись - в двух внутренних циклах надо итерироваться по всем вершинам, а не только по добавленным.
>получается 500^3, норм тебе?
>только смотри не объебись - в двух внутренних циклах надо итерироваться по всем вершинам, а не только по добавленным.
Спасибо большое.
>Sleep(1000)
Проиграл. Нахуя?
не умирай
Какая сложность у алгоритма Евклида для нахождения gcd?
O(\log \min(a,b))
logn
Доказательство?
Зуб даю.
На что мне твой зуб?
В чем секрет чуваков, которые на codeforces делают все задачи раунда за 2 ебаных часа? А?А?
То есть секрет чуваков, которые делают это за час тебя не интересует?
Буду краток. знаешь, буквально на днях я был в Российской Академии
Наук, провёл беседу со многими учёными, в том числе молодыми, кстати,
очень грамотные ребята. Так вот мы обсудили, в частности и данную
проблему, поговорили о текущей экономической обстановке в стране; они
так же рассказали о своих планах на будущее.
Вкратце, ответ на твой вопрос такой: эти ребята довольно быстро решают задачи, что позволяет им придумать алгоритм и написать код для задач всего раунда всего за два часа.
> Покажите, что алгоритм, который содержит не больше некоторого по-
> постоянного количества вызовов процедуры с полиномиальным временем
> работы, сам работает полиномиальное время. Если же алгоритм делает
> полиномиальное число вызовов такой процедуры, то общее время работы
> может быть экспоненциальным.
Посоны, откуда здесь экспоненциальное время выполнения?
Выглядит странно. Очевидно, что суперпозиция полиномов есть полином. Может, там процедура может сама себя дёргать или алгоритм?
Секрет в том, что родились с более подходящей для решения подобных задач генетикой
У тебя мифологическое мышление
ага, иди поспорь с нейробиологическими исследованиями.
Уровня фантазий третьеклассника
можешь жить своими маняфантазями дальше
Пиздец, вот вам спорить нехуй делать. Лучше бы над подумали.
Задача из Кормена. Из раздела NP.
У меня вот прямо щас лежит открытая в туалете глава про NP, но ничего наводящего на мысль не нахожу. Подскажешь конкретнее?
NP полнота>>>Полиномиальное время>>>>Упражнения
Спасибо. Только легче не стало.
Может я неправильно понимаю эту задачу? Ну подставили мы в x^10 значение x=n^20, получили n^200, экспонента никак не получается.
Тут шизофазия, смотрите
Бля у третьего дедка волосы как солнце хех
Вообще-то там один дед, где ты увидел третьего?
Ебался с этой хуйнёй полночи, в итоге только 6/11 тестов проходит :^( Аноним 05/01/17 Чтв 17:11:46 #390 №906492
Сам код (естественно, Паскаль):
http://rgho.st/6smPy2ygw
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, которая и выводится в конце. Правда, там по-другому описано, и нет отдельно левого и правого берега.
Я неофит просто, в этом году едва в регионалку по всеросу не попал.
Кажется, нашел в твоем решении ошибку.
Проверь вход LLRB
Действительно, у меня при притоках по всем сторонам (B) он поворачивает, хотя это совсем не обязательно.
Спасибо, спустя ещё несколько костылей будут все сто баллов, а так пока что 60.
Анончик, не делай так. Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед. Посмотри выше решение готовое. И просто разберись почему оно работает. В нем мы идем, как будто по обеим сторонам реки одновременно.
>Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед
Но почему? Извини, понять не могу.
>И просто разберись почему оно работает.
Хотелось бы всё же допилить своё решение, а если совсем не выйдет -- разобраться в чужих.
Ну не на пять минут, но мне тоже интересно. Мои соображения:
- в каждой точке графа у нас есть два возможных пути
- выбирая каждый раз пусть с меньшим весом, вы в итоге получим кратчайший (в волновом алгоритме всегда обсчитываем только одну ветку)
- переход протоки на стороне, где сейчас игрок, стоит 1
- переход на другую сторону учитывается вместе с переходом протоки на другой стороне (то есть результирующий вес на этом шаге либо 0, либо 2)
Память не нужна, сложность O(n).
Хотя да, заняло минут 7-10.
Тут есть маленький нюанс, но пусть спрашивающий сам догадается. Я могу дать подсказку.
опечатка: 1 либо 2*
Считать надо 2 шага, этот и следующий (как сумму), а при прочих равных выбирать правый берег.
Код покажи.
Я про третьего чувака, он дед.
Сам ты dead, ёпта.
Лул
Сап, анончики, какой набор скиллов нужно выучить/повторить для предстоящей областной?
мимо-школьник
мимо-школьник
Хуй знает, где такое спрашивать, так что спрошу тут пожалуй, это лучше, чем ньюфаг-тред. Есть алгоритм Кнута-Морриса-Пратта. Можно ли им сделать поиск подстроки, если в заданной для поиска подстроке допустим символ, который бы допускал, что на его месте может быть любая другая подстрока?
Задача о ноп?
Есть раздел на acmp.ru с областными олимпиадами, там можно задачки порешать.
Что почитать школьнику нужно больше примеров, чтобы научиться решать задачи на динамическое программирование? А как решать задачи на графы, про всякие j-е дороги между i-ми городами. Я учусь в 10 классе и недавно заинтересовался программированием, пытаюсь в задачи на Codeforces, но получается только А.
Может, уже поздно вкатываться, но хотелось бы уметь это для себя.
Может, уже поздно вкатываться, но хотелось бы уметь это для себя.
Вкатываться не поздно, читай Шеня, Окулова и архивы олимпиад (mccme.ru и прочее, что есть в шапке)
Добра тебе
Для всех, кто вкатывается в ОП на курсере очередной тысячный раз стартует курс по алгоритмам Седжвика.
https://www.coursera.org/learn/algorithms-part1
https://www.coursera.org/learn/java-data-structures-algorithms-2
Быстро проходишь оба курса.
Перестаешь быть зеленым на форсах.
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/info
ОЛИМПИАДНОЕ ПРОГРАММИРОВАНИЕ
Для форсов и ОП итмошный куср лучше, причем сильно лучше. Но у него выше уровень входа. В нем мало теории и много отличных задач.
Объясните как ваша параша помогает вам в реальном программировании?
Никак. Но те кто в 11 классе могут назадротить олимпиаду и пройти в топ вуз.
> постсовок
> топ вуз
топ кек
Сайты верстать не поможет. Так что можешь не париться.
Как просмотреть материалы курса, если он кончился?
Кстати, если не был зарегистрирован, то никак.
Есть список презентаций из учебных видео.
https://courses.edx.org/courses/course-v1:ITMOx+I2CPx+3T2016/bf78f3a948074b16ba7146b1be3b4850/
Список задач с разборами добрые люди дожны были выложить на гитхаб.
Помогите, я нихуя не понимаю. 1 пик условия, остальные объяснение.
на 3 пике:
>Сложим все пары (ki, li)длин таких блоков в массив.
Что это значит? То есть есть строка aabbbaaaaabbaa то в этот массив поместят(2,3) и (5,2)?
И дальше - почему надо найти такое чтобы это выполнялось?
на 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)
А не, ты прав (2,3)(5,2) и (3,5)(2,2)
Как это работает:
Пусть у нас есть строка 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?
Первый больше, но зато второй простой.
И как лучше хэшировать множество (то есть порядок не важен)?
Первый больше, но зато второй простой.
И как лучше хэшировать множество (то есть порядок не важен)?
Если имеются средние знания алгоритмов, на каком ресурсе советуете решать подряд задачи?
Ох ебать я набухался, чувствую себя быдлом, ааааа, мимо готовлюсь к области, ахахахаха
Пиздец
Решай на ацмп
какой на форсах, сколько на тимусе?
Посоветуйте, как вкатиться в алгоритмы и структуры данных с нуля школьнику?
Так я не для олимпиад хочу вкатиться, а просто, чтобы перестать писать велосипеды
1) по модулю 2^32 - 1, это быстрее
2) любой ассоциативной операцией от хешэй элементов (я часто xor использую)
Полный текст задачи на пике. Если своими словами, то у нас есть неизвестная последовательность нулей и единиц. И запросы на четность единиц в подпоследовательности с L элемента до R элемента. Вопрос, начиная с какого запроса последовательности удовлетворяющей всем запросам не существует?
Как решить используя DSU?
Как решить используя 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. Но что с этим делать не ясно.
можно зарегистрироваться и решать в любое время
Олимпиудники, как вы в файлы ввод/вывод перенаправляете?
Парни, объясните тупому, что такое взлом задачи во время контеста на cf?
взлом решения мб?
кто-то посмотрел твой код, который прошёл претесты, увидел что он выдаст неправильный ответ на какие-то допустимые входные и типа запустил твоё решение на этих входных
>запустил
ясно, а как можно посмотреть код до окончания контеста?
На главной странице контеста нажимаем замок напротив решенной задачи.
Переходим в раздел "комната", дабл-кликом по кол-ву очков открываем решение для просмотра.
Находим ошибку
Жмем кнопку взломать, пишем тест(грузим генератор)
????
профит
спасибо
Как CTF начать тащить?
v
Поясните за вот эту задачу
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, когда мы решаем линейное диофантово уравнение?
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 решенных задач, ацмп решал, читал Шеня.
Короче, как вообще люди умудряются искать правильное решение в задачах, где хуй поймешь, какой алгоритм нужен? Тупо нарешивать овердохуя с архивов? И всё?
Короче, как вообще люди умудряются искать правильное решение в задачах, где хуй поймешь, какой алгоритм нужен? Тупо нарешивать овердохуя с архивов? И всё?
Большинство олимпиадников -- олимпиадники по математике тоже (хотя есть исключения), это сильно прокачивает смекалочку, то есть умение понять, как же найти ключ к этой задаче.
Никогда не увлекался олимпами по матану. Значит, нужно забить болт на форсы, ибо без скиллов с математических олимпиад никак не апнуться?
Нет, не обязательно. Просто они прокачивают скилл, которого тебе не хватает.
Попробуй решать много-много простых задач -- на бинпоиск, поиск в глубину и простенькую динамику (в первых трёх задача на этом вашем КФ только это и нужно). Меньшикова на информатикс, региональные этапы, задачки по темам разным.
бамп
Мда, ты что, не быдлокодер?
Написал на питоне, получил ОК и нормас.
> писать олимпиады на питоне
как там на 1400 птс?))0
> Я уже с этим тимусом проебался до 100 решенных задач
Очень мало. Это сколько в сумме ты потратил на решение - 50 часов? Хз почему ты не побеждаешь на олимпиадах, когда целых 50 часов потратил. В доте-то, наверное, 1050 часов.
100500 часов в дотке и все равно в брозе, потому что тима не тянет =)
Ну так если длинная арифметика нужна.
Лол, что за хуйня, если меня ночью разбудить, я нихуя не напишу. Мимо-2000-на-кф
> напишу бинпоиск
До слёз с этого знатока.
Первый див, помоги с раз все равно мимо проходил. Пожалуйста.
Нужен опыт именно в олимпиадных задачах, со временем начинаешь узнавать неочевидные использования того или иного алгоритма и решаешь.
В школе ходил на олимпиады по математике, там та же хуйня была, если видел несколько сотен задачек то почти всегда сразу знаешь куда копать.
Каким образом можно надрочиться за 2 года, чтобы стать победителем на олимпиаде 1 уровня? Знания по математике хуевые, с программированием еще хуже, даже сортировку не могу написать.
informatics.mccme.ru
Сидишь и решаешь. Вместо Доты. Тебе должно быть настолько же интересно.
Как прокачаешься, пишешь так же кодфорсы сможешь писать.
Помогите решить задачу про RSA
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).
Что вообще там может не работать?
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 треду
Как восстановить ответ в задаче о рюкзаке, используя O(N+L) памяти? (N предметов, L вместимость рюкзака)
Знаю аналогичный алгоритм в задаче о расстоянии Ливенштейна, но он какой-то сложный (хотя задача вроде проще).
Знаю аналогичный алгоритм в задаче о расстоянии Ливенштейна, но он какой-то сложный (хотя задача вроде проще).
Проиграл со сложного алгоритма о расстоянии Левенштейна.
https://www.cs.colostate.edu/~cs575dl/Sp2015/Lectures/Knapsack.pdf
Забавно, ты назвал Алгоритм Левештейна сложным, хотя это просто разделяй и властвуй. Обычно когда какой-нибудь алгоритм не до конца разбираешь, считаешь его сложным, хотя на самом деле ты просто не понял его идею.
Если бы ты понял как работает Левенштейн, ты бы сразу понял как можно сделать то же самое для рюкзака.
http://ideone.com/abUEBD
Алё.
Линейное количество памяти + восстановление ответа.
Проиграл с петушка, который не умеет по коду определить сложность по памяти.
Технически можно приебаться к копированию items при делении пополам - будет N*log(N) памяти, но так более читаемо. Понятно, что можно не копировать, а хранить [l, r]
Не тони.
В школе прогал с удовольствием и довольно много, но бессистемно и навыков, кроме непосредственного написания кода, не развил. Потому что долбоеб.
Как итог, в 11 классе в олимпиадки не смог, пришлось идти на физику. Сейчас учусь в приличном вузе мфти, но направление скорее связано с математикой и физикой, буду менять.
Так вот, летом у меня будет около двух свободных месяцев на то, что бы достичь в своем развитии в плане проганья хотя бы уровня хорошего школьного олимпиадника, с какого бока за это лучше взяться? Я так понимаю, сначала нужно освоить алгоритмы, был даже сайт где список из 80 штук, этого хватит для начала? Как распределить время между теорией и практикой?
Есть ли где-то видео-курсы? Так-то я могу ботать по 8 часов, но нужна программа, координация, что бы кто-то вел, по книжкам это тяжело. Ангельский intermediate, речь понимаю, но трачу на это слишком много сил, на постоянный просмотр меня не хватит.
Как итог, в 11 классе в олимпиадки не смог, пришлось идти на физику. Сейчас учусь в приличном вузе мфти, но направление скорее связано с математикой и физикой, буду менять.
Так вот, летом у меня будет около двух свободных месяцев на то, что бы достичь в своем развитии в плане проганья хотя бы уровня хорошего школьного олимпиадника, с какого бока за это лучше взяться? Я так понимаю, сначала нужно освоить алгоритмы, был даже сайт где список из 80 штук, этого хватит для начала? Как распределить время между теорией и практикой?
Есть ли где-то видео-курсы? Так-то я могу ботать по 8 часов, но нужна программа, координация, что бы кто-то вел, по книжкам это тяжело. Ангельский intermediate, речь понимаю, но трачу на это слишком много сил, на постоянный просмотр меня не хватит.
Вебмакак сейчас очень много, поэтому лучше вкатываться в низкоуровневое программирование и embedded.
Алло тут тред олимпиадного программирования, я про него и спрашиваю
Embedded-макак сейчас очень много, поэтому лучше вкатываться в высокоуровневое программирование и веб.
>олимпиадное программирование после школы
Зачем?
Вкатиться в алгоритмы и структуры данных необходимо, но олимпиады не нужны.
Нравится формат, короткие вызовы на несколько часов. Хочется научиться быстрее решать задачи.
Если получится, по вузику можно будет ходить как на понтах, с замдекана за руку здороваться
Котятки, напоминаю что открыта регистрация в код джем.
1) Одному тяжело будет, тренер нужен. Если ты в мфти, с этим 100% проблем не будет.
2) Решай текущие контесты на codeforces + архив на codeforces, там есть разборы задач и можно смотреть чужие решения.
Но вообще, ты какой-то аутист. Олимпиады нужны, чтобы поступить в вуз, а если ты уже поступил, то они нахуй не всрались. В вузе надо либо заниматься наукой (если дохуя умный), либо на работу устраиваться как можно быстрее, чтоб по окончанию вуза уже было много опыта.
1. Искать тренера пока рано, как мне кажется. Никто не будет нянчить дауна без базовых алгоритмических знаний, разве что за большие деньги. Собственно, вопрос был про структурированный курс конкретно по спортивным алгоритмам, что бы направляли и объясняли фишки. В свое время начинал просто решать задачи, но сложилось впечатление что это довольно малоэффективный процесс.
Так со стороны для себя вижу несколько выгод:
1) Идея пачками макачить игрушки для айос на модных фреймворках, пусть даже за большие деньги, меня не очень прельщает.
А вот идея написания высокоэффективного кода кажется гораздо интереснее, поэтому спортивное программирование кажется мне актуальнее для себя, чем тот же технотрек.
2) Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании, поэтому получить этот навык будет так или иначе полезно. При этом лучше сейчас, чем чеез 6 лет, когда придется начинать работать и гнаться за рынком. Тем более, что учить прикладные технологии сейчас не имеет смысла.
>был даже сайт где список из 80 штук
Это который?
> 1. Искать тренера пока рано, как мне кажется. Никто не будет нянчить дауна без базовых алгоритмических знаний, разве что за большие деньги.
Блять, что значит нянчить? Ты просто ходишь на тренировки, где ты один или с командой таких же ньюфагов решаешь задачи, а потом идет разбор этих задач. После разбора можешь дорешивать задачи и задавать всякие вопросы. Фишка в том, что если ты решаешь один и не понимаешь, почему у тебя задача не принимается, ты можешь очень долго думать и в итоге все равно не додуматься. Намного лучше у кого-нибудь спросить.
> Идея макачить меня не прельщает.
Ты понимаешь, что все, что не наука - это макакинг? Да, есть более высококвалифицированные макаки. Вот я немного шарю в алгоритмах и математике, но макакой я от этого быть не перестаю, потому что я не могу создать что-то новое, чего не было до меня. Я могу хуйнуть нейросеть и распознавать изображения, но не я же придумал алгоритм backpropagation, это будет просто реализация чужой идеи. Ничуть не лучше, чем сайты на пхп хуярить. Если не хочешь заниматься макакингом - поступай в магистратуру, потом в аспиранутру и т д. Если ты тупой как я и не можешь в науку, лучше сразу задумайся о будущей работе и начинай дрочить все разделы cs, а не только алгоритмы. Прочитай все книги Таненбаума.
> Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании
На большинстве вакансий не спрашивают динамическое программирование, теорию чисел, геометрию, графы и прочую хуету. Из алгоритмов спрашивают что-нибудь "на смекалочку" (типа найти подмассив с максимальной суммой за O(n)) + то, что реально полезно знать в работе: деревья (красно-черные, b-tree и т д), хэши, сортировки и т д. На олимпиадах ты никогда не будешь писать красно-черное дерево / свою сортировку / свою хэш-таблицу.
Анон, помоги. Что-то не получается решить элементарнейшую задачу на тимусе (сложность 81) http://acm.timus.ru/problem.aspx?space=1&num=1106.
Мой код:
http://acm.timus.ru/forum/thread.aspx?id=36064&upd=636260865438522774
Моё решение заключается в том, чтобы с помощью BFS покрасить все вершины и записать в ответ те, которые имеют одинаковый цвет
Мой код:
http://acm.timus.ru/forum/thread.aspx?id=36064&upd=636260865438522774
Моё решение заключается в том, чтобы с помощью BFS покрасить все вершины и записать в ответ те, которые имеют одинаковый цвет
Аноны, есть какие-нибудь методы по решению таких задач, как эта: http://acm.timus.ru/problem.aspx?space=1&num=1502 ?
Я проебал на ней два часа, вывел какую-то ебанутую формулу, которая почему-то работает и получил AC. Вопрос - есть какие-нибудь статьи/книги, где рассказывается, как решать похожие задачи с нахождением формул?
Я проебал на ней два часа, вывел какую-то ебанутую формулу, которая почему-то работает и получил AC. Вопрос - есть какие-нибудь статьи/книги, где рассказывается, как решать похожие задачи с нахождением формул?
Накидайте плз задач на cf или тимусе на префикс- или z-функцию.
Ты че, поехавший?
#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+%2B+j),+j+%3D+i+to+n),+i+%3D+0+to+n
Во-вторых, если ты это делаешь на контесте, когда время ограничено и ты не можешь пользоваться вольфрамом, ты можешь упростить эту сумму, чтобы она считалась за O(n) вместо O(n^2), но не искать конечную формулу (пикрелейтед).
В-третьих, при желании можно продолжить выводить и вывести конечную формулу тупо в лоб, просто нужно терпение и внимательность.
В-четвертых, этот анон правильно заметил, решение в лоб проходит, потому что у тебя здесь примерно 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.
Вот эта хуйня не дает мне покоя, как блять это сука работает?
Ты че, ебан? Суфмассив + lcp
Ещё суффдерево можно + дфс, но раз ты такое спрашиваешь, вряд ли ты его напишешь с первого раза.
Можно ли на КФ как-то смотреть тесты, если соревнование уже прошло?
Нет. Если не получается, скидывай сюда, кто-нибудь решит.
Да там классическая задача, я просто баг в реализации не мог найти (уже нашёл).
Лол, вот это я тебя обманул. Извини, плохая память. Так это, после сабмита тебе должно выдать все входы и выходы (если ты не в олимпиадном режиме решаешь)
С этого момента поподробнее.
Как найти совершенное паросочетание минимального веса в двудольном графе?
Между долями есть всё рёбра, если это важно (наверно нет, потому что можно надобавлять ребёр с весом ∞).
http://informatics.mccme.ru/mod/statements/view.php?id=6555#1 - вот эта задача, короче
Между долями есть всё рёбра, если это важно (наверно нет, потому что можно надобавлять ребёр с весом ∞).
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) {...};
(в теле цикла, понятно, эти переменные не трогают)
Я вот не знаю, разве что очевидные вещи типа:
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, но задача не прошла. До сих пор не уверен в чем дело
Может имел место произвольный доступ к элементам списка?
>компилятор какую-то лямбду скомпилировал во что-то хуевое
Вообще пушка.
Ты сам смотрел на ассемблерный код, или просто так ляпнул что-то от балды? Я думаю, что ты просто не знаешь С++ и пишешь чушь.
> Ты сам смотрел на ассемблерный код
Зачем мне смотреть, если я и так знаю, что лямбды могут сконпелироваться в хуйню и не только в плюсах. Заменил лямбду на эквивалентный императивный вариант и зашло. Какой тут еще вывод можно сделать?
Нет, там только в начале и в конце добавлялись элементы.
>если я и так знаю
Короче не слушайте этого шизика, он где-то как-то обжёгся на лямбдах (небось не отличает [=] от [&]), а обосновать или привести примеры не может.
Чтобы не стать такими как он всегда докапывайтесь до истины, если видите, что что-то не работает, а не "ща тут cout вставим чтобы глючить перестало"
> &deque.back()
Такие ссылки не инвалидируются при новых пушбэках? Или как-то можно указать, чтобы дэк на основе связного списка генерировался? Но тогда какая это оптимизация, если всё равно при каждом добавлении системный вызов.
Ну не скажи. Разница между O(n) и O(n log n) весьма призрачная, и оптимизированный логарифм может работать быстрее, чем линейное решение, особенно если у него константа пожирнее.
Изредка даже O(n^2) вместо O(n) может зайти, если тесты слабые, либо такое решение, что для него тест непросто придумать, особенно заранее, не зная решение.
Конечно, чаще проще решить по честному, но сдать задачу, не решая, тоже весело.
Ты вообще представляешь что такое deque в С++? Как он внутри устроен? Почитай cppreference прежде чем такие вопросы задавать.
Эй, отвечающие в тред, расскажите, когда и как вы начинали упарывать олимпиадки, какой лвл, где учились/учитесь/работаете. Что читали с самого начала, на какие курсы ходили?
Ходил на курсы в академю ШАГ, но там скучно был и я вместо занятий ходил к твоей мамке заниматься любовью.
Основные ресурсы с задачками:
codeforces.com - Клевый проект, чуть ли не еженедельные контесты. Система писькомерства рейтинга уровня ELO с Короткевичем 4к+. Задачки своеобразные, пилятся комьюнити, мало общего с задачками стандартного ACM, что продиктовано форматом соревнований. Так же codeforces выбирают площадкой для множества престижных соревнований уровня VK Cup, в тренировки заливаются все крупные контесты оффлайн.
acm.timus.ru - великолепный архив. Решишь 500 задач на тимусе - будешь гарантированно красным на кфе
informatics.mccme.ru - хорош для новичков
Дальше идут ресурсы, которые оп не юзал особенно по своему скудоумию:
acmp.ru - ничего сказать пока не могу
TopCoder.com - пендосский codeforces, регулярные контесты, открытые турниры и тому подобное
e-olymp.com - не знаю
FAQ
Что почитать?
Грэхэм, Кнут, Паташник "Конкретная математика"
Кормен "Алгоритмы. Построение и анализ"
Как вкатиться?
Читай книжки сверху, и решай как можно больше
____________________
Предыдущий тред тонет тут
Шапка за пять минут, надеюсь треду жить, принимаются предложения по оформлению