>>792098 (OP)
Решать на тимусе задачи по сложности от самых легких до сложных?

Все знают, что такое счастливый билетик.

Например:
123456
Сумма первых трех 5, сумма последующих 15. Билет несчастливый.

111003
Сумма первых трех чисел 3. Сумма последующих чисел 3. Билет счастливый.

Задача, посчитать сколько счастливых билетов между 100000 и 999999.

Выиграет самый красивый код.

print(50412)
Шах и мат

>>792282
знатное говноедство, даже я уважаю

http://ideone.com/CEDdGe

>>792140
[code lang="python3"]sum(sum(map(int, (c for c in str(x)))) == sum(map(int, (c for c in str(y)))) for x in range(100, 1000) for y in range(0, 1000))[/code]

http://ideone.com/rHkZk5

>>792140
http://ideone.com/SaQEJX
жаль, что не от 000000, так бы было сильно красивее

>>792731
Так ты на код смотри, а не на расширения файла
Просто CLion все проекты считает как C++

>>792098 (OP)
>codeforces.com
вроде отослал один, а он сыпится. нихуя не понимаю, где фак? ввод бинарный чтоль?

>>792738
нет, все там в порядке
кидай свой код, может ты просто не умеешь в считывание значений

>>792739
да вижу тут есть запускалка, потыкался, я так понял он в sdin пихает, а не в стартовые ключи - как я думал. хотя вроде логично, ведъ программа после ввода должна умереть?

вот ещё момент не вкурил: есть ли гарантия что 1 read вернёт мне весь ввод или нужно ещё дрочить всё ли ввелось? видимо да чёт приуныл

>>792098 (OP)
А смысл какой их решать?

>>792745
В стартовые ключи это как. Там есть задачи с мегабайтами инпута, ключами не обойдёшься.
Твоя задача вывести правильный output и вернуть EXIT_SUCCESS.
>>792801
Для интереса, это в основном хобби. Есть побочные профиты типа "в яндексе любят олимпиадников". Для школьников также помогает попасть на всякие бюджеты, ещё проводятся соревнования с неплохими призами, но это надо сильно угореть по теме.

>>792801
я вот просто хочу подрочить байтики. на время - не интересно.

>>792818
>Там есть задачи с мегабайтами инпута, ключами не обойдёшься.
ну наверно тоже верно, но можно было файлами заделать - а то ведь скорость будет сильно зависеть от того как реализован инпут в языке - а оно очень разнородно.

>>792818
>хобби
Таки да, если не дрочиться по 2-3 5-часовый тренировки в неделю чтобы стать чемпионом мира.
Школьнику однозначно имеет смысл угореть, я сам жалею, что не хватало мотивации/не всегда мог себя заставить ботать в школьном возрасте, победителя всероса а не призера взял бы с легкостью. Все равно это лучше чем проебывать время на каэску какую-нибудь.
Поступление в любой топовый универ халявное, опять же.

Студентам активно задрачивать смысла нет, если не целиться на финал АСМ. Но таки полезные эффекты в виде "быстро решать задачки на собеседовании в Yandex/Google" возникают.
Ну еще, если не совсем донный, да и универ не совсем парашный, можно нахаляву за счет универа то есть ездить по всяким соревнованиям как и в пределах рашки, так и заграницу.

>>792838
Раньше делали с файлами, но постепенно от этой практики отказались, может быть чтобы полностью избавиться от еботни с правами доступа. Кроме того, тебе же удобнее, сколько WA было получено на неверном названии файла… Причём в некоторых случаях это оказывалось решающим фактором.

>>792866
СЪЕЗДИЛ НАХАЛЯВУ
@
В ПЕТРОЗАДРОТСК

>>792879
Ну да, это само собой. А еще Москву, Париж, Будапешт, Белград и Катовице (Польша). И везде билеты + проживание - за счет универа

>>792879
А сейчас люди получают WA на том, что ОЙ А ТУТ ФАЙЛЫ НУЖНЫ. Или ОЙ Я ФАЙЛЫ НЕ ЗАКОММЕНТИЛ (хотя нормальные пацаны юзают препроцессор для этого).
Хотя без файлов таки удобнее, да, жаль, что не везде так сейчас

Добавьте в шапку http://dl.gsu.by/
Сайт крут тем что там дохуй задач и он показывает количество пройденых тестов. Даже на сами тесты можно посмотреть.

>>792922
но вооще, где-нибудь в лине можно было бы перехватывать пару функций в libc и на любое имя файла давать один путь. наверняка и в винде такое можно провернуть.

Самый опущенный тип айтишников это олимпиадники.

>>792733
> объявление счетчика цикла for в цикле for
> чистый Си

>>792956
Опа, дед вылез.

>>792953
Толсто.

>>792919
В Москву эту куда, на МФТИшные сборы да на четверть, если рядом живёшь?

>>792969
Да, МФТИшные сборы, они самые. Сам из Питера, поэтому четверть пишу у себя

сап, вопрос такой
вот на соревах стоят ограничения по памяти
но
в jvm языках же сама jvm автоматом отжирает до пизды памяти
получается jvm-блядки априори сразу сосут?

>>793026
Да. Алсо, ты ещё забыл про инициализацию машины, тоже время отжирает. Выбор языка в любом случае за тобой + ситуации, когда задача решается на С и не решается джавой, крайне редки.

олсо я совсем зеленый не понимаю пока как вкатиться
видел советуют книгу Шеня, она ок?

>>793033
Это в случае, если ТЛ для Джавы стоит раза в 2 больше, что некоторые Online Judges делают по дефолту. А вообще зависит еще и от автора. Если он напишет какое-то заоптимизированное решение на плюсах и поставит жесткие ТЛи чтобы отсечь другое решение с чуть большей асимптотикой, то Джавакодеры соснут

>>793038
Иди сразу на кодфорсы, читай параллельно емакс, дорешивай задачи и читай разборы. Для начала сойдёт, когда дело дойдёт до уровня суфавтоматов, уже сам разберёшься, что делать.

>>793042
СОКОБАН)))0)

Зачем нужно олимпиадное программирование, если все держится на библиотеках и фреймворках? Оно же абсолютно не нужно в реальном мире. Лучше потратить время не на подготовку и дрочку алгоритмов, а на прикладную разработку и на свой гитхаб.

>>792098 (OP)
В спортзал и к стилистам всех четверых. Футболки блядь на халка, пошить соразмерные. Крайнему слева в жопе похудеть, перестать жрать говно, перейти на салатики и мясо. Бородачу как минимум выровнять бороду.

>>793047
друг, где читать разборы? я заходил на рашен кап чето там, но там объяснение мне показалось уже для чуваков которые прорешали пару десятков контестов

>>793056
На кодфорсах почти к каждому контесту пилят разбор авторы. Кроме этого, не стесняйся в случае чего спрашивать в комментах: пост вынесет на первое место в секции комменты, его увидят и ответят с вероятностью 99%.

>>793052
>абсолютно
Радикально. В многих областях алгоритмы необходимы, пусть и не всем разработчикам.

>>793053
Котёнка лучше не трогать, где ещё такое встретишь, при том что он относительно молод.

>>793052
Писали же кучу раз
Школьникам есть однозначные профиты которые не очень сложно получить, да и олимпиадки на таком уровне таки сильно влияют на прогерские навыки
Студентам - хобби, помощь на собеседованиях.
Да и полезно таки некоторые алгоритмы писать самому, чтобы понять как работает что-то. Опять же, навыки писать оптимальный код на плюсах

>>793060
Я не говорю про алгоритмы, они то очень нужны, я говорю про олимпиадную дрочку, которая вырабатывает плохой стиль кода (попробуй попиши читаемый код на время) и бесполезна в реальном мире.

>>793065
А, ну в этом плане может быть.

Могу поспорить по следующим пунктам:
1. В целом развитие понимания, как всё работает, неасимптотическая оптимизация как, например, std::ios::sync_with_stdio
2. Навык дебага сложных конструкций.
3. Умение писать код быстро и правильно, то есть держать в голове много деталей

Отдельно скажу, что после многих лет олимпиад в проектах всё пишу максимально красиво, по другому уже и не хочется, но тут уже у всех своё. По крайней мере можно сказать, что само понимание красивого кода приходит после взаимодействия, а лучше написания некрасивого.

>>793073
>как, например, std::ios::sync_with_stdio
Хуевый пример, если честно. В реальной жизни хрен понадобится

>>793082
Хуёвый, но про плюсы тут особо ничего и не расскажешь. Хотя в целом вопрос I/O в C/C++ довольно занятный.

Вот про питон можно долго говорить, там абсолютно неочевидные вещи происходят.

Ребят, а я вот наоборот олимпиадник, а в промышленном полный ноль :с

>>793658
Че ты врешь?

>>793658
Ну ты же наверняка понимаешь почему так, или есть хотя бы предположения.
Просто не нравится?
Вполне вероятно, что ты просто мало промышленно кодил, тогда это нормально. В олимпиадках ты ж тоже не сразу начал норм участвовать наприер

>>792098 (OP)
>Конкретная математика
первая же задачка - мой пердак в небесах, ответ на неё - подлетаю к юпитеру. это просто пиздец какой-то.

Не смог решить вторую по сложности с начала задачу на тимусе.
Задавайте свои ответы

>>795372
обратный корень?
она сложная так-то, там на пушбэк поп

>>795402
что такое пушбэк поп?
я на си пытался решить

>>795402
Блять, ты тролль или ты серьезно?
Пиздец просто, >на пушбэк поп
Техника имени Семена, блять. Это как про любую задачу сказать "это задача на инт мейн", поеботень полная

>>795406
Тебе надо знать, что такое массивы, как считывать-выводить вещественные числа, и как извлекать корень.
Первое - это лучше погугли и почитай в нормальном месте туториалы по языку, если таких основ не знаешь
Второе - считывать так:
double a;
scanf("%lf", &a);
и писать
printf("%f", a)
На самом деле, это верно для 11+ стандартов, в старых стандартах и читать и выводить с помощью %lf вроде
Третье это
#include <math.h>
...
a = sqrt(23.9);

>>795326
кинь задачу

>>795372
Я максимум решал 1010+ сложности на тимусе. Я успешнее

Как найти кратчайший маршрут между двумя вершинами в бинарном дереве?

>>796352
Что такое бинарное дерево?
Я не понимаю зачем обсираться в присядку, одновременно обмазываясь говном и дрочить на коколимпидаки и нахуй не нужные алгоритмы

>>796398
>Что такое бинарное дерево?
На пике.

>>796427
>единственный маршрут
Из 9 в 2 можно идти пом пути 9 4 2 1 2.
>Находишь всех предков обоих вершин.
Не эффективно. Должен быть способ быстрее.

>>796903
А нет его в памяти. Даже размер не известен. но в long long влазит. Выглядит как на той картинке. Наверно просто максимальный надо делить на 2 пока они не сравняются.

>>796914
Числа между которыми маршрут прокладывать. Вывести нужно сам маршрут.

>>796920
>Похоже, что это задача на пушбэк.
Скорей всего на int main() и return.

>>796352
1. В любом дереве маршрут всегда единственный, иначе бы там были циклы.
2. Задача сводится к нахождению наименьшего общего предка двух вершин, которую можно решить например алгоритмом Тарьяна.

>>796208
То, что все лошади одной масти, можно доказать индукцией
по числу лошадей в определенном табуне. Вот так:
„Если существует только одна лошадь, то она своей масти,
так что база индукции тривиальна. Для индуктивного пере-
перехода предположим, что существует п лошадей (с номерами от
1 до п). По индуктивному предположению лошади с номера-
номерами от 1 до п — 1 одинаковой масти, и, аналогично, лошади с
номерами от 2 до п имеют одинаковую масть. Но лошади по-
посредине с номерами от 2 до п — 1 не могут изменять масть в
зависимости от того, как они сгруппированы,—это лошади, а
не хамелеоны. Поэтому в силу транзитивности лошади с номе-
номерами от 1 до п также должны быть одинаковой масти. Таким
образом, все п лошадей одинаковой масти. чтД*
Есть ли ошибка в приведенном рассуждении и какая имен-
именно?

>>795392
просто это математика, мне сложно, нужно по другому мыслить, немного перестроить голову.

>>797322
Это же очевидно, неверная база индукции. Самый первый переход для n=2 не работает, базой должен быть именно этот случай, что невозможно.

>>796935
Тарьян offline, лучше всё-таки на sparse table делать.

Сап, посоны, пишу алгоритм Дейкстры. Что я делаю не так? Должно выводить 24 3 15, а выводит 24 32 20. Нумерация вершин с единицы.

https://ideone.com/eGhmMK

>>797948
Граф ориентированный или нет? У тебя в коде он ориентированный, а в задаче как? Видимо, в ней он неориентированный, тогда надо делать
adj_list[begin].push_back (make_pair(end, weigth));
adj_list[end].push_back (make_pair(begin, weigth));
У тебя нет второй строчки

>>797964
Неориентированный, и еще допустимы мультирёбра, но в тестовых данных для примера мультирёбер нет. Какие изменения в алгоритме надо сделать, чтобы обрабатывать мультиграфы?

>>797969
Эм. Никаких (зачем?). А вот тот фикс, что я предложил, сделать таки надо.

>>797975
Да, этот фикс помог. Матрица неорграфа симметричная, и списки тоже делаются симметрично.

Говорят, что мультиграф надо немного иначе обрабатывать.

>>797980
Нет, не надо. Лишние ребра тебе ничего плохого не делают: ты все равно в итоге выберешь из всех мультиребер ребро с наименьшим весом. В принципе, если их совсем много, то можно когда строишь граф, просто среди всех ребер, соединяющих одинаковые пары вершин, оставить только ребро с минимальным весом, но алгоритм будет работать корректно и без этого

>>797981
Блин, тогда я даже не знаю, почему программа проходит все тесты, кроме двух.

https://ideone.com/pJfxfM

>>797982
А, скорее всего, я вывожу INF там, где по условию надо выводить -1. Сейчас проверю, должно помочь.

И все-таки странно, что авторы обращают внимание на то, что могут попадаться мультиграфы.

>>797984
Ну например это может быть важно в случае, если человек юзает матрицу смежности вместо списка смежности хотя тогда бы по TL бы не прошло скорее всего. И, как правило, в задачах по умолчанию граф простой, поэтому выделение того, что есть кратные ребра, является некоторым правилом хорошего тона, можно сказать.

Посоны, смотрите.
На двумерной плоскости имеем набор многоугольников с float координатами. Как определить, находится ли точка внутри какого-либо многоугольника?

>>798379
Если они выпуклые, то для каждого многоугольника можно делать проверку за log(число вершин)

Если задачу на кодфорсе взломали, то это хорошо т.к. она бы завалилась на основных тестах, а так есть возможность узнать об ошибке и доделать её?

>>800440
Именно так, если ты ее не заблокировал, конечно

Когда разбор сегодняшнего кодфорса запилят (див2)? Где его смотреть?

>>800574
Там разборы бывают? А див1 есть?

>>800579
Вот тут сказали, что бывают: >>793060
Я хз, сегодня впервые написал.

Чо, обидно, со второй задачей вышло?)))

>>798398
Проще, но на этот способ любят делать контртесты. Надёжнее пускать в рандомном направлении.
>>798379
Я всегда использовал сумму полярных углов. Тема такая, для каждой грани ты считаешь, под каким ориентированным углом она видна из точки. Дальше считаешь сумму, если получилось 0, то ты снаружи, если 360 градусов – внутри. Случай на грани рассматривается отдельно.
>>800440
Бывает, что ломают решения, которые не валятся на тестах.
>>800574
Разбор появляется от сразу до нескольких дней, пали комменты к посту о контесте, там обычно спрашивают такие вещи.

>>797533
мне сложно, а вот если есть задача - я могу её решить, как там написано, и так же индукцией доказать - не проблема. но когда меня спрашивают, например докажите что в задаче на столбы, используются все возможные комбинации - вообще не ебу как. да, для меня очевидно, что вот число и его бит может иметь 3 значения, тогда число с n бит имеет 3^n-1 возможных комбинации - даже не представляю как это доказывают.

>>800960
> Почему 3, а не 2?
потому что это из усложненной задачи 2. но я не проверял в ответах заебало чувствовать себя говном

> Откуда -1?
потому что ноль не учитываем - там задача сформулирована так, вродъ.

> А ты попробуй индукцией
как? замкнутая форму уже есть, я её вывел из рекуррентной, опять же, из прошлой задачи. дальше то что?


> 2 Найдите кратчайшую последовательность перекладываний, перемещающих башню из n дисков с левого колышка А на правый колышек В, если прямой обмен дисками между А и В запрещен. (Каждое перекладывание должно производиться через средний колышек. Как обычно, больший диск нельзя
класть на меньший.)
> 3 Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения нам встретятся все допустимые варианты размещения n дисков на трех колышках.

>>800963
>как? замкнутая форму уже есть, я её вывел из рекуррентной, опять же, из прошлой задачи. дальше то что?
в смысле, я человек тупой, не математик, и не имею этот склад ума, я так понял, что индукция способ доказать что замкнутая форма формулы верна - путём поставления её в рекуррентную.

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 <- это

или что под этим ещё понимается?

>>800966
> T(1) = 2

>>792098 (OP)
2 справа бы трахнул нет

Т.е слева -_-

>>800954
Ничего не понял, кинь условие задачи, или что ты там доказываешь.

>>792098 (OP)
>Грэхэм, Кнут, Паташник "Конкретная математика"
Этой книги достаточно, чтобы понимать анализ алгоритмов, всякие асимптоты и прочее из следующей книжки? Или придется до кучи ещё математики наверстать? Мой уровень если что на уровне девятиклассника, лол.

>>801308
Угу. А асимптотика там обсуждается аж в последней главе.
Как я и думал, все эти алгоритмы и интеллектуальные игры с ними для элиты, которую с рождения обучают не тому, что дают в обычной быдло-школе. Пойду дальше в дотку катать.

>>801315
Просто начни с книжек попроще. "программирование: теоремы и задачи" Шеня, а потом вот это http://codeforces.com/blog/entry/12314
Ну и перед этим учебник школьный по математике, если совсем неуч.

>>801396
Спасибо. Я настолько тупой, закончил школу, а не могу решить задачи с acmp.ru которые сложнее 30% по их шкале.

Зарегался на этом вашем кодефорсес. Где там выбирать задачи по уровню сложности и тематике?

Алсо, есть там что-нибудь по преобразованию Фурье?

>>801684
Есть задача "ДНК роботов", поищи по названию.

>>801684

>>801705
https://www.e-olymp.com/ru/problems/1841

>>800887
>Бывает, что ломают решения, которые не валятся на тестах.
Ну вот. Ты меня запутал. Чётно обфусцирую решение на следующем контесте, а нечётно нет.

https://new.vk.com/rommikh?z=video33940993_171563293%2Fc9824696cca687188d%2Fpl_post_-108370559_63

>>803666
После множества таких казусов с недавних пор все успешные похеки добавляются в набор финальных тестов.

>>803678
круто, жаль что я не видел этого в школьном возрасте

Есть ли простой алгоритм быстро возвести матрицу в квадрат?
Вот две произвольные матрицы либо за эн в кубе умножать, либо хитрый алгоритм. А тут может попроще?

>>805600
Нет, нельзя, насколько я знаю. Есть только, как ты сказал, хитрые алгоритмы, либо частные случаи типа метода четырёх русских.

>>805622
Ну у меня вот как раз частный случай, две одинаковые матрицы умножаем.

>>805626
Я понимаю, вот и говорю, что я, по крайней мере, никогда о таком частном случае ничего особенного не слышал. Пиши Штрассена или гугли научные статьи на эту тему.

>>805626
>>805633
Впрочем, можешь ничего не гуглить, вот ответ на твой вопрос http://math.stackexchange.com/questions/20873/whats-the-fastest-way-to-take-powers-of-a-square-matrix

бумп

>>792098 (OP)
Рассказываю, почему я бросил олимпиадное программирование. Когда я начинал, то думал, что там задачи чисто на смекалку, для решения которых не требуется никаких предварительных знаний. Но это оказалось не так. Есть определенное количество узкоспециализированных тем, например, динамическое программирование или древовидные структуры данных, в которых надо быть хорошо прошаренным, чтобы решать олимпиадные задачи. Если кто не понял, что я сказал, приведу такой пример: если вы попытаетесь доказать хотя бы теорему Пифагора, ничего о геометрии не зная вообще, то у вас ничего не выйдет. Так вот я задумался однажды, стоит ли задрачиваться в темах, которые котируются на олимпиадном программировании, если они мне скорее всего не пригодятся в работе. Лучше уж потрачу это время на изучение чего-нибудь более практичного.

>>810133
зря бросил, ящитаю

>>810507
Я бы не бросал, если бы было много свободного времени, но его нет.

>>810133
Ты прав, в принципе, если не считать, что в некоторых местах типа яндекса и вк олимпиадников очень любят. Да и в целом на базовом уровне почти везде спрашивают, но базовый CS и так все должны знать просто по роду профессии.

>>810715
Тут замкнутый круг.
В "базовый CS" входит комбинаторика, теория чисел, графы, динамическое программирование. Это активно используется на олимпиадах и во всяких гуглах. Но никак не изучается глубоко в вузах (кроме парфеновской кафедры и еще схожих) и не применяется в рф-it. Кроме сам знаешь где. Тоесть олимпиадное программирование, или тот же Скиена, это единственный способ рф-студенту окунуться в то "а что же там пишут в гуглах, что у нас нет". Да и без олимпиадной подготовки ты будешь о-о-чень долго вникать во всякие crack the coding interview и elements of programming interview.

Аноны, подскажите алгоритм: дано произвольное количество 2d-вершин, нужно из них сделать многоугольник с непересекающимися гранями.

>>812961
построение выпуклой оболочки

>>813017
Вроде это не совсем то. Все точки должны быть задействованы.
Я написал примитивный алгоритм: проходим по точкам, отсортированным убывающе по y, и соединяем ближайшие по x, но иногда он фейлится.

>>813104
Берёшь самую нижнюю-правую точку, ставишь её как начало координат. Считаешь полярные координаты остальных точек относительно центра. Сортируешь по углу, обходишь в этом порядке.
Дядя Сэджвик с Курсэры так учил

>>813134
Я походу проще вариант нашел: пространство делится на 2 части по x (можно взять тупо width/2), слева и справа строятся ломаные кривые и потом соединяются.

>>813163
>ломаные линии

>>813163
Хотя тупо width/2 будет ошибкой, нужно чтобы хотя бы 2 точки было на одной из сторон.

>>813177
Хотя нет, полностью неправильно, лел.
Ладно, буду думать.

>>792098 (OP)
> эти плечи

>>813163
хуйня решение же очев

>>813287
Теперь докажи корректность.
По-моему у тебя просто жадная эвристика.

>>813300
Я думал о корректности.
Из любого набора разных точек можно сделать ломанную линию с непересекающимися кусками, соединяя точки одна за другой в одном направлении. Пересечений гарантированно не будет, если между точками в этом направлении нет других точек.
Мы получаем две ломанных линии, не пересекающиеся между собой. Вопрос только в том, можем ли мы безопасно соединить их концы. Ответ: да, т.к между концами больше нет других точек, т.к. мы заведомо взяли 2 верхние и 2 нижние точки и от каждой начали строить линию.
И все же это не n, а nlogn, т.к. надо сначала отсортировать точки в одном направлении.

>>813319
Занятно, я всегда пользовался сортировкой по полярному углу. Сложность такая же, но алгоритм ка будто чуть попроще, нет двух частей, тупо сортировкой сразу достигаешь нужный порядок с другой стороны, может быть критична скорость работы с float

Mathematica
(1/Pi) Integrate[((Sin[10x] )/Sin[x])^6, {x, 0, Pi}]
Счастливых билетов: 55252

>>816915
Элегантно, только погрешность численного интегрирования точность подпортила.

>>816923
А интегрирование аналитическое, без погрешностей.
Хотя если оценить вид первообразной и по пределам оборвать, то можно свести все к вычислению 1109369452791600/20078358300

Зо o(n) низя т.к. если можно то можно числа за o(n) сортировать а так низя потому что низя

>>817083
Нет, все верно у меня.
Главное не ошибиться с выбором лево-право у крайних отрезков. Я сначала выбирал тупо - если p1.x < p2.x, то p1 уходит влево, но это не всегда так. Пример на второй пикче.

>>817702
Можно и по убывающей, без разницы, главное чтобы в одном направлении.

>>818434
Допустим, мы проходим против часовой стрелки от нижней точки. Если мы сначала возьмем по убывающей, то получатся вершины 1-3-2, что уже ошибка, я это имел в виду.

Есть правильная скобочная последовательность и внутри неё есть мусорные данные. Для удобства есть ассоциативный массив в котором каждой зная координату одной скобки можно найти координату соответствующей ей скобки. Иногда нужно удалять мусорные данные. И когда это происходит, то размер строки и координаты некоторых скобок меняются, а ассоциативный массив нет. Как максимально быстро вернуть корректные значения в ассоциативный массив?
Пример
s="aa(bbcccb)"
В массиве m лежат 2:7 и 9:-7. Это значит что скобке s[2] соответствует скобка s[2+7], а скобке s[9] скобка s[9-7].
Теперь если удалить все c, то получим s="aa(bbb)" И массив надо будет 2:4 и 6:-4. Скобок может быть больше поэтому на некоторые это удаление влияет, а на некоторые нет.
Формат записи в ассоциативном массиве менять нельзя. т.к. это не совсем ассоциативный массив и в нём ещё хранится инфа по мусорным данным которые не совсем мусорные
Нужно делать это максимально быстро. Память не жалко т.к. размер строки около 10к символов. А вот время нужно экономить т.к. важна каждая миллисекунда.
Как решить?

>>822144
Что за "ассоциативный массив", он совсем медленный, или можно к нему обращаться лишний раз в процессе апдейта?
Пока вижу так: держим массив с координатами всех скобок. Когда надо делать апдейт находим бинарным поиском первую скобку правее места удаления, и начиная с неё до конца массива фиксим каждую скобку.
То есть:
1. Уменьшаем адрес каждой скобки на размер удалённого куска. Скорее всего это подразумевает удаление записи из ассоциативного массива, и добавление новой с другим ключом.
2. Если это закрывающая скобка, а соотв. открывающая левее точки удаления, то обновляем сдвиг в открывающей.
3. Уменьшаем адрес скобки в нашем вспомогательном массиве на размер удалённого куска.

>>822569
>он совсем медленный
Совсем быстрый. За константу обращение.
>бинарным поиском
И как им искать скобки в не отсортированной строке?
И работает это долго и не правильно.
Вот тест ((abc)()) После удаления любой буквы скобки выделенные жирным трогать не надо. Пока думаю делать вспомогательный массив где отсортированы координаты всех закрывающихся скобок.
Вот например тест "((a)b(c)d)" и удаляем b. В вспомогательном массиве будет 3 7 9. С помощью ассоциативного узнаём координату закрывающейся скобки и проверяем есть ли между ними удалёный элемент. Так должно быть быстрее, но после каждого удаления заново по массиву проходить не хочу, а как после всех удалений применить этот метод не знаю т.к. удалять можно несколько элементов подряд и их потом ещё запоминать придётся.

>>822144
Всё зависит от требований: много запросов – меняй за линию, это как угодно можно делать, быстрее за раз всё обновить нельзя, будешь на запросы за 1 отвечать. Много удалений, мало запросов – делай вспомогательный массив "текущей версии" для каждого индекса, и вспомогательное дерево типа дерева отрезков для "обновления" индексов за логарифм и взятия за логарифм (с дальнейшей записью в оригинальный массив и обновлением номера версии, чтобы между вырезаниями только один раз каждый индекс заново считать).

>>822710
А как сделать чтобы пока поступают запросы просто заменяешь символы на пробел, а потом за раз всё удаляешь и скобки корректируешь? Это быстрее всего должно работать. Запросы обычно не большие. Несколько байт. Но может много запросов на небольшой участок строки быть.

>>822616
>И как им искать скобки в не отсортированной строке?
Для "((abc)())" массив индексов скобок будет [0, 1, 5, 6, 7, 8]
как видишь он отсортирован.

>И работает это долго
Удаление символа в середине строки это уже медленно.

>и не правильно
>После удаления любой буквы скобки выделенные жирным трогать не надо.
В ассоциативном массиве были записи 6:1 и 7:-1, а должны стать 5:1 и 6:-1, само по себе оно не обновится.

Анончики, может у кого есть нормально отформатированная Конкретная математика в mobi/epub или прочем ebook формате? Я искал, форматировал и все тщетно. А пдф читать на 6 дюймовом киндле не шибко удобно и приятно. Заранее спасибо за ответ.

>>812961
http://e-maxx.ru/algo/convex_hull_graham

Вчера писал свой первый раунд на Codeforces, почувствовал себя дауном. Первая задача простая, ну действительно, чего ее решать, давайте посмотрим остальные. Вторая про графы, чет как-то слишком длинное условие, сложна. Третья про пифагоровы тройки. И тут я засел. Родил какое-то стремное решение через числа Фибоначчи (спасибо Википедии за это), а оно зависает на всех нечетных, а на четных выдает не всегда верные ответы. В итоге два часа просидел над этой задачей, ничего не решил, а когда открыл разбор - охуел от простоты и изящества. Это лечится или мне навеки оставаться тупым?

>>824692
Поступил на программиста, называется.
Мама, мама, я буду кодить!

>>824692
лечится. одноклассник не умел решать ничего кроме a и иногда b, а через 1.5. года стал призером всероса.

>>824692
А у меня в С неправильное решение принялось. Должен быть TL, а оно принялось. Там я рассматриваю 2 случая:
1) a - катет. Тогда a^2 = (c - b)(c + b). Перебираем все делители числа a^2 (факторизуем a и умножаем все степени на 2; всего делителей будет не больше нескольких тысяч). Для каждого делителя d решаем в натуральных числах систему
{
c + b = d
c - b = a^2/d
}
2) Если a - гипотенуза, то я перебираю b от 1 и до тех пор пока b^2 < a^2, то есть там в цикле может быть 10^9 итераций. Почему у меня нет TL, я не понимаю.

>>824692
>>825960
> а когда открыл разбор - охуел от простоты и изящества.
Какое изящество, тут просто надо знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает, это знают только всякие дрочилы, которые нарешивают олимпиады по математике для школьников.

>>825975
А если какие-нибудь методички, в которых подобные тайные знания раскрываются?

>>826006
Не трать на это время, это полная хуйня. На cf есть нормальные задачи на какие-то определенные темы, решение которых помогает в понимании этих тем. То есть это задачи на какие-то алгоритмы или структуры данных, а не на знание того, что нечетное число можно представить в виде разности квадратов. Просто нужно уметь отличать хуету от нормальных задач.

>>826006
скиена "олимпиадные задачи по программированию"

>>824692
Я как-то хантился в майкрософт, к Дену Расковалову.
https://www.linkedin.com/in/raskovalov/ru
Он говорит, что только масштабы и время. Тоесть кодфорсес к собеседованиям мало отношения имеет. Так что чтобы решать олимпиады нужно быть задротом и дрочить много именно задачки. Там может быть ад на теорию чисел и комбинаторику. Как в прожект ейлера. После 300 задачек начнешь уже решать без задней мысли. А это полгода дрочильни где-то.

>>826059
Спасибо.

>>826059
А что там на собеседованиях спрашивают? Понятно, что разглашать конкретную информацию нельзя, но разгласи неконкретную.

>>826077
http://poincare.matf.bg.ac.rs/~jelenagr/ASP/testHeadHunter.pdf можешь начать тут, а потом careercup.com

>>826087
послал бы нахуй за такие вопросы на собеседовании

>>826087
Говно. Не нашёл вопроса про то, в какую сторону едет автобус.

>>792098 (OP)
Здесь обсуждают олимпиаду для поступления в вузы ?

Начал решать задачи на тимусе для закрепления знаний Си.
Как в Си вычислить корень 876652098643267843 ?
http://ideone.com/XVSbT2

>>827714
long long int a;
самспросилсамответил

>>827714
Пиздец быдлокод.

ХОДИШЬ ТАКОЙ НА ОЛИМПИАДЫ, БЕРЕШЬ ПРИЗОВЫЕ МЕСТА
@
ПРИГЛАШАЮТ РАБОТАТЬ В ЯНДЕКС
@
ПОСЛЕ НАПИСАННОГО ТОБОЙ ОБНОВЛЕНИЯ У ВИНДОВС ПОЛЬЗОВАТЕЛЕЙ СЛЕТАЕТ ВИНДОВС СО ВСЕМ СОДЕРЖИМЫМ ДИСКА Ц
@
С ПОЗОРОМ УВОЛЬНЯЮТ
@
КАРЬЕРА В ИТ ДЛЯ ТЕБЯ ЗАКОНЧЕНА, ПИЗДУЕШЬ РАБОТАТЬ ДВОРНИКОМ

>>827759
ПОСЛЕ ПОДМЕТЕННОГО ТОБОЙ ПОДЪЕЗДА ПОЛОВИНА ЖИТЕЛЕЙ ПОСКАЛЬЗЫВАЮТСЯ И ЛОМАЮТ НОГИ
@
С ПОЗОРОМ УВОЛЬНЯЮТ

>>827819

@
НЕ ОСТАЕТСЯ НИЧЕГО ДРУГОГО, КАК СТАТЬ НАЕМНЫМ УБИЙЦЕЙ ЗА ДОЗУ ГЕРОИНА
@
ЦЕЛЬ ИЗЛЕЧИВАЕТСЯ ОТ БОЛЕЗНЕЙ ПОД ТВОИМИ УДАРАМИ
@
ВЫГОНЯЮТ БЕЗ ПЕНСИИ

>>827727
Рекурсивная функция в две строки, решающая одну из первых задач с тимуса. Что доебался до него?
Разве что while я заменил бы на простой if

На джаве кто-нибудь пишет? Поможете сопитимизировать? У меня TL.
http://codeforces.com/contest/709/problem/E
http://pastebin.com/pW573vzV
Время работы там O(n), в этом точно косяка нет. Я заменил рекурсию на while + stack, потому что до этого был stack overflow. То что инпут с помощью Scanner - это норм, потому что если бы инпут не успевал, у меня бы не доходило до stack overflow в первой версии. От лямбд я уже пробовал избавляться, тоже TL.

>>829298
Хотя сейчас замерил, инпут занимает 2 секунды. Сейчас попробую сканер заменить на что-то побыстрее.

>>813245
Широковаты. Я от своих тоже в бугурт впадаю.

>>829298
Оберни System.in в BufferedReader

>>829344
Сделал. Сначала не сдалось, но потом я еще обернул System.out в BufferedOutputStream и сдалось.

Поясните зашквар или нет вставлять в резюме ссылку на свой профиль на codeforces? Устраиваюсь не в какой-нибудь яндекс, а обычным крудошлепом.

>>829596
Какой рейтинг?

>>829347
Не понял. А почему BufferedReader не помог? Какая выгода от BufferedOutputStream?

>>829616
Помог, где-то на полторы секунды быстрее стало, но этого было недостаточно.
> Какая выгода от BufferedOutputStream?
В этой задаче аутпут 400000 и выводится по 1 символу, а это очень долго. А buffered сначала ниче не выводит, а когда делаешь flush, выводит все сразу.

>>829615
Максимум 1650 было.

>>825975
>знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает
Если ты не знаешь, что комбинаторный интеграл от 2n+1 равен n(n-1)+n, что ты вообще делаешь в этом треде?

>>831614
Хуйня для дрочил или специалистов по комбинаторике. Вот ты сколько статей уже написал?

>>831614
>комбинаторный интеграл
Чоблядь?
Интеграл от 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
Подсказка: интегрирование по частям.

Циановый даун с кодефорсеса цвета морской волны ищет боевого товарища, чтобы в соревновательно-помогательном режиме ботать прогу. По заявкам оставляю фейко-контакты

>>832679
Это сколько, 1200-1400 что ли? Могу просто так тебе помочь если че, спрашивай. Я максимум был синим.

>>832722
1400 - 1600. У меня вопросов особо нет. Надо только надрочиться. А одному это уныленько.

>>832725
Ты хочешь сказать, что у тебя в городе нет ни одного места, куда можно ходить на тренировки по асм?

>>832845
Есть. Но этого разве достаточно?

>>792098 (OP)
Кажется правого кунца я видел в МИРЭА, он там курс по android ведёт.
Так ли это?

>>833204
Нет, я сомневаюсь, что Егор будет вести курс по Android в сраном МИРЭА.

>>832963
> 5 лет назад
Тогда была другая система рейтинга, так что на тот момент он был прав.

Самолет взлетает в X (целое, 0<=X<=23) часов по местному времени в часовом поясе номер M (целое, 0<=M<=23). После полета в течение K (целое, 1<=K<=12) часов он приземляется в часовом поясе номер N (целое, 0<=N<=23). Определите местное время в пункте приземления. Считать, что часовые пояса нумеруются с запада на восток.

Тупая задачка. Почему нельзя просто прибавить ко времени старта врем полета, а потом прибавить разность номеров часовых поясов?

>>834027
Все, разобрался. Идите нахуй

>>834027
А кто тебе сказал, что нельзя? Летал самолет или нет, значения не имеет, от этого разница во времени между часовыми поясами не изменится. Здесь просто спрашивается, какое время будет в другом часовом поясе через n-цать часов. И какое все это имеет отношение к погромированию?

Эй, умники. Есть задачка. У нас имеется n целых неотрицательных чисел, чья сумма не превосходит 10^5. Еще есть некое m до 10^4. Все эти n чисел мы хотим представить в виде целых долей этого числа m, причем нецелые доли мы вольны округлять в любую сторону по желанию левой пятки. Я тут набросал тупой жадник, который, конечно же, доказывать не умею, и он отхватывает wa2. Жадник настолько тупой, что он все округляет вверх, а потом, переокругляет вниз пока не получим нужную сумму, равную m
http://ideone.com/3x53a2

>>835570
Дай ссылку на исходную задачу, потому что ты во-первых написал условие как мудак (блядь, неужели нельзя скриншот запостить хотя бы, и пару примером входа выхода), а во-вторых лучше засабмитить, чем какому-то петуху объяснять.

>>836278
Ну вот так-то лучше. Сам-то чувствуешь, что гораздо понятнее выглядит? Очевидная динамика же.

>>836282
Я, конечно, толком в динамику не умею. Но тут и намеков не вижу. Не просветишь?

>>836283
Хотя тут даже динамика не нужна, жадный алгоритм должен работать. У тебя, наверное, просто не проверяется, что если число нацело делится, то его двигать нельзя уже.

>>836284
Так ceil же не должен целое число округлять. Или там с точностью может быть лажа?

Ну динамика, если интересно, такая: f(arr[i:], amount) - можно ли набрать amount сумму, округляя как-нибудь числа начиная с i-й позиции, как в рюкзаке, и по времени проходит - 50е6. Только, повторяюсь, она тут не нужна.

>>836289
А ты потом даже от целых чисел берёшь и отнимаешь 1 на 25-й строчке.

>>836291
http://ideone.com/0pI4qN
Больше не отнимаю. Но как-то не.

>>836291
Высрал контрпример http://ideone.com/kRzC4I

>>836293
Не канает, см >>836294

>>836295
Да. Я уже вижу. Спасибо, мил человек

Сколько сюда не захожу, так и не пойму, чем вы тут занимаетесь

>>826995
Почему бы и нет.
>>836425
Спортом вестимо.

>>836961
> Спортом вестимо.

Игра в доту — это спорт. Решение олимпиадных задач по программированию — это не спорт. Выводы делай сам.

У всех cf лежит?

>>839646
Нет

>>839721
Пидора ответ.

Как научиться решать CTF?

>>840732
Приходишь на ctf. Дальше все понятно.

Серьезно. Обычно есть отборочные туры, где есть возможность гуглить

>>840861
Ладно. А что там знать и уметь надо?

>>840875
Идешь на отборочный тур и узнаешь. Там бывают разные задания: криптография, сети, крекинг етц

>>843105
Допустим все числа нечетные, тогда просто расположим их так, чтобы их середины находились на оси x и будем зажигать от самого длинного к самому короткому. Допустим, нечетные, тогда то же самое.
Допустим есть четные и нечетные числа. Например, 2 стержня 4 и 5. Тогда придётся все числа той же четности, что и максимальное, зажечь с одного конца, чтобы сделать всех одной четности, а потом применить алгоритм из первого параграфа.

>>843169
С четными и нечетными я хуйню написал.

Короче зажигаешь самый длинный стержень с двух сторон, а дальше изъебывайся как хочешь, но чтоб все в один момент лопнули. Это можно сделать.
В первую секунду зажигаешь самый длинный стержень с двух сторон, а стержни длины на 1 меньше - с одной стороны, во вторую секунду все стержни которые горят с одной стороны поджигаешь со второй, а все стержни на 1 меньше - с одной стороны. И так далее.

>>843304
А, там ещё и определённая точка должна загореться последней, вот я мудак.

>>797533
ты ебанулся? база индукции очевидно верная. переход не верен (при п=2)

Я умею искать гамильтонов путь в неорграфе динамикой по подмножествам, где вершин не больше 20. А вот теперь мне надо проверить наличие гамильтонова пути в ацикличном орграфе с количеством вершин вплоть до 10^5. Вроде простая задача должна быть. Думаю пока в сторону топсорта какого-то

>>846398
Сравни длину длиннейшего пути с количеством вершин + 1.
https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths

>>846398
>>846526
Честно говоря не понимаю зачем пишут топсорт делать. Наверное чтобы достичь O(N) вместо O(N*log(n)).
По идее достаточно для каждой вершины предрасчитать списки входящих соседей (если вершин с пустым списком >1, то гамильтонова пути сразу нет), а потом пока есть нерассмотренные вершины берёшь рандомную считаешь расстояние от истока до этой вершины как максимум среди её входящих соседей+1. Применяешь алгоритм рекурсивно, не забывая про мемоизацию.
Короче как поиск кратчайшего, только длиннейшего.

>>792725
Эх, щас бы в 2016 перебором задачу решать, вместо динамического программирования

>>846526
Да, спасибо. Я пытался делать дфс, который брейкается, когда глубина рекурсии становится равна количеству вершин. Но как-то это получало ва5.
>>846535
Ты же понимаешь, что твои идеи на порядок сложнее и для осознания, и для написания. Топсорт - это одна строчка в дфсе

Окей. Как быстро проверять достижимость каждой вершины из каждой по матрице достижимости? Вершин всего тысяча, но флойд не вариант, потому что там сверху еще будет логн от бинпоиска висеть. Граф плотный, поэтому бфс меня тоже смущает. Или нормально?

>>846939
В матрице достижимости все элементы должны быть равны 1.

>>846963
Действительно. Но это я, наверное, плохо выразился. Я еще подумаю, пожалуй

>>846939
Исходную то задачу расскажи.

>>847025
Вот эта: https://www.e-olymp.com/ru/contests/5045/problems/39900

>>847029
>>846965
Я, кажется, придумал, что хочу по матрице смежности быстро строить матрицу достижимости

>>847052
Подсказка, попробуй отсортировать ребра по весу.

>>847202
Пиздец я проебался, думал граф неориентированный, тогда это просто бинпоиск и SCC

Нужны две функции. Одна принимает английский неправильный глагол, а возвращает его первую форму, а вторая получает рандомное слово и составляет кучу других слов из таких-же букв. Какие есть способы это сделать быстро?

>>846939
BFS/DFS, компоненты связности. Предподсчёт за V^2, дальше ответ за 1.

бумп

>>792098 (OP)
Пререквизиты для Кормена и Кнутопаташика есть ли? Скожите пожалуйста.

Для Кормена только мозг нужен, ну там подумать иногда придётся. Кнутопаташника не читал.

>>856298
У Кормена есть в конце книги поясняется за математику

Парни, есть какой нибудь сайт, где перечислены основные олимпиадные алгоритмы? А то я знаю только викиалгоритмы, а он бесполезен для этого

>>861959
e-maxx

>>861999
огромнейшее спасибо

>>861959
http://algolist.manual.ru/

Что, как поживаете? Я вот тут недавно школьную командную олимпиадку писал. Суть в том, что я-то алгоритмов довольно много знаю, могу написать. Префикс, з функции, декартачи, до, всякие графы, хэши. Но, сука, проблема в том, что в команде я ничего не придумывал. Мне говорили: "пиши топсорт, потом проверяй наличие соседних ребер". Или: "Склей строчки, посчитай префикс функцию, пока суффикс совпадает с префиксом, удаляй их. Я, бля, даже условия оригинального не знаю.
Это все круто, но на личной олимпиаде не проканает. Неумение быстро выдумывать решения - это приговор? Или еще есть шанс до феврали задрочить задачки из первой полутысячи тимуса?

Есть программа с кучей функций. У каждой функции есть название. Известно количество обращений к каждой функции за последнее время.
Надо назначить функциям однобуквенные хоткеи так, чтобы сумма чисел обращений к функциям, которым назначены хоткеи, была максимальна.
Хоткеем функции можно назначить только букву, входяшую в её название.
Знаю про венгерский алгоритм, но у меня вес дуги из функции в каждую из допустимых клавиш одинаков. Есть ли что-то быстрее для такого случая?

>>863521
на то в команде всегда и есть два прогера, один комп, и один математик который придумывает решения, сечешь?

>>864060
Да. Но мне до студенческих командных нужно дописать личные олимпиадки, где один прогер и один математик в моем лице

Вы меня удивляете.
Пишу на крестах и пухтоне.

Последнее время само-собой приходится дрочить адгоритмизацию и математику, причем комбинаторику и статистику (что ненавижу, лучше дифуры).

Я чет не понимаю, как программист может не мочь в такое? Что за бред? Это как себя не уважать.

>>864307
>адгоритмизацию и математику, причем комбинаторику и статистику (что ненавижу, лучше дифуры)
держите матаноблядь!11

>>864307
>адгоритмизацию
А что это за дисциплина?

>>864557
hellburnization is a part of CS

>>864307
не все такие умные и не все так рано начинали, мне вот 30 лет и на тимусе у меня 50 задач, в школе был далек от программистов, даже не знал об этом, но как сейчас выяснилось тогда по матеше я обходил парней ныне уже участников финала мира acm icpc

>>864307
>статистику
А что с ней не так?
Даже гуманитароблядки её усваивают.

>>864900
http://www.math.wm.edu/~leemis/chart/UDR/UDR.html

>>864929
Для программирования пруфы нужны ужО Штоле?

>>864983
Спроси в machine learning треде.

Пишу алгоритм для игры. В ней нужно набрать максимум очков. Их количество не может уменьшаться. Есть фактор случайности. игра похожа на монополию и количество возможных исходов одного хода меньше чем у шахмат При этом игра может закончиться совсем неожиданно если неколько ходов подряд кубик будет плохо падать. Значит обычный minmax не подойдёт т.к. при большой глубине поиска лучший из худших всегда будет проигрыш. И что делать с линией горизонта? Ведь здесь нельзя форсировать поиск при шахе как в махматах. Реквестирую литературу про программирование ии для игр с влиянием рандома.

>>865189
>обычный minmax не подойдёт т.к. при большой глубине поиска лучший из худших всегда будет проигрыш
Не понял проблему. Оцениваешь все исходы броска кубика, и считаешь матожидание оценок. Или не просто матожидание, а матожидание от некоторой функции, учитывающей твоё отношение к риску. Например если надо срочно догонять противника имеет смысл оценивать нулём исходы, которые не дают тебе достаточно очков.

>похожа на монополию
Пиши эвристический алгоритм.
Если хочешь можно ещё сделать обход дерева ограниченной глубины, а по достижении дна считать оценку. Эвристикой опять же. Альтернативно можно использовать метод Монте-Карло. Берёшь начальное положение и много-много раз отыгрываешь его до конца каким-то простым алгоритмом за обоих игроков, а потом по результатам отыгрышей даёшь оценку положению. Но мне кажется эвристика будет точнее.

>Реквестирую литературу
Ты слишком напрягаешься, смотри как люди делают:
https://github.com/intrepidcoder/monopoly/blob/gh-pages/ai.js
https://github.com/DepthDeluxe/Monopoly/blob/master/src/monopoly/AIPlayer.java

>>865292
> обход дерева ограниченной глубины, а по достижении дна считать оценку
Так и хочу. Но уже на небольшой глубине можно получить большую оценку, но это будет проигрыш и конец игры. Если в одну и ту же сторону идти, то скоро проиграешь. А в алгоритме перебираются все возможные направления и все возможные броски кубика. Потом смотриться на конкретную глубину и выбираеться тот ход минималиный профит от которого самый большой. Что делать с этими проигрышными тупиками?
И исходники читать не интересно. Хоть статьи скинь.

>>865330
>получить большую оценку, но это будет проигрыш и конец игры
Оценка не обязательно равна количеству очков. Это может быть и разность очков у тебя и противника, и сложная функция, учитывающая ещё и ситуацию на доске.
Никто не запрещает тебе назначать проигрышам оценку 0.

>>865348
Так может быть так что все ходы проигрышные. Надо что-то выбрать из тех нулей. Может их в 2 очереди проверять? А с горизонтом что делать? Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный. А алгоритм только на 5 вглубь смотрит и войдёт в проинрышную ветку из которой не выйти.

>>864996
Ну, так, ты мне какой-то теорию категорий с универсальной алгеброй тычешь. Статистика тут при чём?

>>865385
>Так может быть так что все ходы проигрышные. Надо что-то выбрать из тех нулей.
Если у всех стратегий одинаковая оценка, то выбираешь рандомно.

>А с горизонтом что делать?
Ну блин, делай как в шахматах делают. По достижении дна оценивай положение на доске эвристикой. В шахматах фигурам назначают цену, цены имеющихся фигур складывают, и ещё как-то расположение учитывают, хз как. Так получают примерную оценку для позиций на дне. Тебе тоже надо придумать эвристику для оценки позиции. Как это сделать я подсказать не могу, тут надо пробовать варианты и проявлять изобретательность.
Попробуй решить https://projecteuler.net/problem=84 может придумаешь как прикрутить себе сети Маркова.

>Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный.
В настолке с кубиком такое нереально. Там слишком много рандома. По этой же причине нет смысла делать сложный алгоритм - разница в уровне игры по сравнению с тривиальным "покупай всё что можешь" будет практически незаметна человеку.

>>865443
Чего? На диаграмме показаны соотношения между распределениями случайных величин.

>>792140
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])

>>865492
Ошибка вышла:
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])

>>867885
Мне это напомнило задачу с прошлогоднего полуфинала или даже финала. Копни в эту сторону Насколько я помню, там отчасти рандомизированный алгоритм. Сперва что-то поспрашивать, а потом решать.

>>867892
Хуя они охуели давать задачи с финала. Уточни, пожалуйста, что за финал?

>>867898
Прости, я тебе наврал. Мне почему-то вспомнилась задача J https://neerc.ifmo.ru/archive/2015/neerc-2015.pdf
Но это совсем из другой оперы

>>867901
Но ты все-равно подумай про рандомизированные алгоритмы

>>867903
http://rce.su/randomizirovannyj-protokol-svyazi-chast-1/
Вот это попробуй почитать.
А откуда задача?

>>867907
Хорошо, спасибо. На паре по дискретной математике задали.:(

>>867903
>>867885
Вы че ебнулись? никак.

>>868178
> никак
А доказать?

>>865492
>>865498
Руки бы тебе блять оторвать за такой код, хуесос

С трудом даются задачи из Конкретной математики. Это нормально? Продолжать задрачивать или прочитать что-нибудь полегче сначала?

>>870866
А куда легче? Учебник за 5 класс?

>>870911
Да, спасибо, подходит

анон, в какой порядке решать задачи на codeforces? самые популярные, новые, только A, B..., только div 2 или без разницы?

>>873630
Отсортируй по количеству решивших. Начинай решать. Если чуешь, что очень легко идет, листай на следующую страницу

>>873631
спасибо, так и сделаю

>>867885
Если ещё не поздно, вот тебе подсказка: почитай как устроен raid5.

>>875022
http://ideone.com/iTglQT

>>875130
Ты внимательно прочитал условие?
Особенно про то, что размеры строк r^2, а памяти - r, и что она неперезаписываемая?

>>875163
Да, задачка решается для строк размера r^2 , r бит неперзаписываемой памяти и r+1 запросе. Я думал, это очевидно.

Стандартная задачка егэ:
Из ряда натуральных чисел выбрать произвольное количество чисел так, чтобы их сумма не делилась на 6. При этом сумму надо максимизировать. На выход количество выбранных чисел и их сумму. Я не совсем ньюфаг в олимпиадном программировании, но тут встал в тупик. А егэ сдавать надо

>>875307
Динамическое программирование: f(i, c) = максимальная сумма подпоследовательности arr[:i], делящаяся на c.

>>875316
s/делящаяся на c/дающая c в остатке при делении на 6/

>>875307
Как насчёт взять все, а потом при необходимости выбросить наименьшее, не делящееся на 6?

>>875240
Ну не томи тогда, рассказывай.

>>875366
Я бы на твоём месте ещё подумал, задача-то простая. Но если совсем зашёл в тупик, то вот
http://lpaste.net/339079

>>875163
> http://ideone.com/iTglQT

Грови? Это что вообще, лол?)
Ввожу число, имя не выводит, переделывай

>>875413
Ввёл тебе за щёку.

>>875369
Я понял задачу так, что обязательно использовать ровно r+1 запрос.
В таком случае возникает проблема, что на каком-то шаге мы можем обнаружить расхождение, но мы обязаны сделать остальные шаги, и непонятно как передать на эти шаги информацию о том, что различия уже найдены.

>>875448
Нет, ты неправильно понял задачу. Обычно такие странные условия обговариваются. Например, было бы написано "сделав ровно r+1 запрос"

Может тут есть кто-нибудь, кто тоже участвует во всероссийской олимпиаде для 11 классов? Сейчас пробный тур проходит как раз.
И еще может кто-нибуд в технокубке участвовал? Какого уровня там задачи? Там вообще ебанутые какие-то правила с этими взломами, не знаю осилю ли я там хороший результат показать.

>>875793
Ну, участвовал в твоем технокубке. Из-за того, что не в том порядке стал решать задачи, занял не 70-какое-то, а 150 с хуем место. Не понравилось

>>877609
Хули тут думать-то, жадный алгоритм же.
Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i.

>>792725
пиздец, деление и остаток от деления двумя операциями... Охуеть просто.

>>877722
Ну а что ты хотел, я тогда только начал вкатываться в си и программирование вообще

>>877675
>среди работ с дедлайном >= i.
А если таких нет, то ничего не назначать, а потом делать дополнительный проход, заполняя дни без назначений?
И как находить такие дни - поддерживать отсортированную по штрафу коллекцию, и в неё докидывать работы из заранее подготовленного списка работ, сгруппированных по дедлайну?

Мне кажется проще назначать день работе с наибольшим штрафом. Если есть свободные дни до дедлайна, то забираем последний. Иначе забираем последний из дней после дедлайна.

Какую теорию погуглить для олимпиадного программирования? Я просто совсем неадвно вкатился и пока что просто на логике всё делаю. Жадные алгоритмы, динамическое алгоритмы, что ещё?

>>877910
Способы представления графов в памяти, DFS/BFS, алгоритм Дейкстры, комбинаторика на уровне итерации по всем перестановкам и сочетаниям, бинарный поиск, алгоритм Эвклида, решето Эратосфена, генерация пифагоровых троек, метод ветвей и границ.
На самом деле сам поймёшь что нужно когда будешь натыкатьсся на трудные задачи.

Как научиьься реализовывать алгоритмы? Смотрю в интернете всякие видео уроки по популярным алгоритмам, типа quicksort, но реализовать на языке который изучаю не могу. Сто делать?

>>877991
Как научиьься выступать в суде защитником в деле об ебле козы бабы Нюры? Смотрю в интернете всякие видео уроки по выступлениям-заседаниям, типа quicksort, но выступить в суде в котором выступаю не могу. Сто делать?

>>877991
Находишь в интернете реализацию ксорта на твоем языке. Понимаешь. Потом переписываешь, можно подглядывать. Как переписал, закрываешь. На следующий день без подглядывания пиши.

>>877923
Спасибо.

>>877991
Задвай себе вопрос "а что надо делать" и делай. Потом "а что теперь?" и так далее. После каждого такого шага чекай всё ли правильно работает.

>>878003
>>878012
Спасибо, няши

>>877722
а как можно лучше?

>>878123
divmod
>>877811
тысячи способов, пиши какой удобнее.

>>877675
> Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i.
И какая у этого алгоритмическая сложность? По-моему, не меньше O(N^2). Многовато.

>>879289
Про кучу не слышал?

Продублирую тут, пожалуй.

Сап. Есть в треде алгоритмодрочеры?

Есть таблица связей в бд (postgres): юзер id - группа id.
Нужно выделить несколько секций юзеров (нужно, чтобы было максимум N юзеров в каждой такой секции), которые входят в группы "эксклюзивно".
Другими словами. Допустим N=1000. В секции #1 будет 10 групп, в которые входят только юзеры из этой секции, всего 980 юзеров в секции #1. В секции #2 будет 14 групп, в которые входят только юзеры из секции #2, всего 900 юзеров в этой секции. Всех остальных относим в последнюю секцию. Нужно найти такие вот секции, приблизительно.

Какой тут алгоритм применять?
Главное чтобы быстрее работало, какая-то точность разбития на секции (типа, чтобы максимально скомпоновать юзеров по N=1000 в секции) не нужна.
Пока вижу просто тупо ходить в цикле по группам (в порядке возрастания популярности групп, навеhное), собирать юзеров, пока не наберется 1000, после чего собирать следующую.

>>881288
Трудно что-то сказать не зная как распределены пользователи по группам и что значит "приблизительно" и "эксклюзивно".

Выбирай очередную группу рандомом пока не наберёшь достаточно, делай несколько подходов, выбирай лучший результат.

>>881503
>не зная как распределены пользователи по группам
Как угодно, считай, это группы в вк.
>"приблизительно"
Я имел, ввиду, что не хочу найти лучшее решение из возможных (где секции максимально укомплектованы - по 999, 998 юзеров, например, в каждой), а более быстрое (то есть, пусть там в каждой секции будет по 900-1000 юзеров, это ок).
>"эксклюзивно"
Это я просто так назвал, не знаю как правильно. Смысл - в каждой секции должны быть группы, в которые входят только юзеры из этой секции, не пересекаясь с другими секциями.

Как я уже написал, группы - это как группы в вк. То есть, например, соберу секцию #1, где будет группа любителей хентая 500чел + группа любителей гуро 400чел (из них 100, например, входят в группу хентая) + группа любителей golang 10чел. В других секциях любителей хентая, гуро и golang быть не должно.
И т.д. Большие группы, типа мдк, где >1000чел, не входят в секции. Но их подписчики могут быть любителями хентая, гуро, golang.

>>881518
>В других секциях любителей хентая, гуро и golang быть не должно.
Это строго обязательно? Это условие сильно усложняет задачу.

Сап. Я школьник, 10 класс. Алгоритмы знаю на уровне "quick sort, binary search, bfs, dfs, dijkstra". Такой вопрос - можно ли за год вкатиться в олимпиады так, чтобы получить хоть какие-то бонусы для поступления? И на что следует обратить внимание? Готов сидеть у книжек часами каждый день. Если что, пишу на плюсах.

>>792098 (OP)
>codeforces.com
>acm.timus.ru
>informatics.mccme.ru
>acmp.ru
>TopCoder.com
>etc
Скажите, а есть возможность на каком-нибудь из этих ресурсах сдавать задания на питоне?

>>881549
Думаю можно. Выясни какие олимпиады тебе подходят, посмотри задачи прошлых лет. Нарешивай подобные задачи и читай теорию.

>>881574
Да

>>881549
Есть знакомые, которые из твоего положения и хуже брали себе потом диплом всероса, так что дрочи задачки. Посмотри на иоип, например

>>881581
А подскажи, пожалуйста, на каком из них конкретно можно, если знаешь.

>>881616
На топкодере вроде нельзя. Но вообще не надо писать олимпиады на питоне
Ты сам не можешь посмотреть?

>>881616
на всех, даже etc

>>881535
>Это строго обязательно? Это условие сильно усложняет задачу.
Да.

как самые популярные темы задач на codeforces? дп, жадные алгоритмы, графы, структуры данных...
что задрачивать, чтобы стать хотя бы синим?

>>881665
На синего хватит простых графов, бинпоиска, качественного конструктива. Сложные алгоритмы начинаются после Ddiv2

>>881668
спасибо

>>881654
>Не надо писать на питоне
Почему?

>>792140
>(c for c in str(x))
Достаточно просто str(x)

>>881654
Спасибо

это >>882111 сюда >>792567