Двач.hk не отвечает.
Вы видите копию треда, сохраненную 23 мая 2017 года.

Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее

Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
58 Кб, 640x427
ОЛИМПИАДНОГО ПРОГРАММИРОВАНИЯ ТРЕД НАМБА 3 # OP #792098 В конец треда | Веб
Настало время перекатить и такой тред.

Основные ресурсы с задачками:
codeforces.com - Клевый проект, чуть ли не еженедельные контесты. Система писькомерства рейтинга уровня ELO с Короткевичем 4к+. Задачки своеобразные, пилятся комьюнити, мало общего с задачками стандартного ACM, что продиктовано форматом соревнований. Так же codeforces выбирают площадкой для множества престижных соревнований уровня VK Cup, в тренировки заливаются все крупные контесты оффлайн.
acm.timus.ru - великолепный архив. Решишь 500 задач на тимусе - будешь гарантированно красным на кфе
informatics.mccme.ru - хорош для новичков
Дальше идут ресурсы, которые оп не юзал особенно по своему скудоумию:
acmp.ru - ничего сказать пока не могу
TopCoder.com - пендосский codeforces, регулярные контесты, открытые турниры и тому подобное
e-olymp.com - не знаю

FAQ
Что почитать?
Грэхэм, Кнут, Паташник "Конкретная математика"
Кормен "Алгоритмы. Построение и анализ"

Как вкатиться?
Читай книжки сверху, и решай как можно больше
____________________

Предыдущий тред тонет тут >>706304 (OP)

Шапка за пять минут, надеюсь треду жить, принимаются предложения по оформлению
#2 #792138
>>792098 (OP)
Решать на тимусе задачи по сложности от самых легких до сложных?
#3 #792140
Все знают, что такое счастливый билетик.

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

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

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

Выиграет самый красивый код.
#4 #792287
print(50412)
Шах и мат
#5 #792304
>>792282
знатное говноедство, даже я уважаю
# OP #7 #792567
>>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
882115
#8 #792666
>>792140
http://ideone.com/SaQEJX
жаль, что не от 000000, так бы было сильно красивее
35 Кб, 614x698
#9 #792725
Cамый годный вариант на чистом си
846674877722
#10 #792733
>>792731
Так ты на код смотри, а не на расширения файла
Просто CLion все проекты считает как C++
792956
#11 #792738
>>792098 (OP)

>codeforces.com


вроде отослал один, а он сыпится. нихуя не понимаю, где фак? ввод бинарный чтоль?
792739
#12 #792739
>>792738
нет, все там в порядке
кидай свой код, может ты просто не умеешь в считывание значений
792745
#13 #792745
>>792739
да вижу тут есть запускалка, потыкался, я так понял он в sdin пихает, а не в стартовые ключи - как я думал. хотя вроде логично, ведъ программа после ввода должна умереть?
792818
#14 #792780
вот ещё момент не вкурил: есть ли гарантия что 1 read вернёт мне весь ввод или нужно ещё дрочить всё ли ввелось? видимо да чёт приуныл
#15 #792801
>>792098 (OP)
А смысл какой их решать?
792818792832
#16 #792818
>>792745
В стартовые ключи это как. Там есть задачи с мегабайтами инпута, ключами не обойдёшься.
Твоя задача вывести правильный output и вернуть EXIT_SUCCESS.
>>792801
Для интереса, это в основном хобби. Есть побочные профиты типа "в яндексе любят олимпиадников". Для школьников также помогает попасть на всякие бюджеты, ещё проводятся соревнования с неплохими призами, но это надо сильно угореть по теме.
792838792866
#17 #792832
>>792801
я вот просто хочу подрочить байтики. на время - не интересно.
#18 #792838
>>792818

>Там есть задачи с мегабайтами инпута, ключами не обойдёшься.


ну наверно тоже верно, но можно было файлами заделать - а то ведь скорость будет сильно зависеть от того как реализован инпут в языке - а оно очень разнородно.
792879
#19 #792866
>>792818

>хобби


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

Студентам активно задрачивать смысла нет, если не целиться на финал АСМ. Но таки полезные эффекты в виде "быстро решать задачки на собеседовании в Yandex/Google" возникают.
Ну еще, если не совсем донный, да и универ не совсем парашный, можно нахаляву за счет универа то есть ездить по всяким соревнованиям как и в пределах рашки, так и заграницу.
792879
#20 #792879
>>792838
Раньше делали с файлами, но постепенно от этой практики отказались, может быть чтобы полностью избавиться от еботни с правами доступа. Кроме того, тебе же удобнее, сколько WA было получено на неверном названии файла… Причём в некоторых случаях это оказывалось решающим фактором.

>>792866
СЪЕЗДИЛ НАХАЛЯВУ
@
В ПЕТРОЗАДРОТСК
792919792922
#21 #792919
>>792879
Ну да, это само собой. А еще Москву, Париж, Будапешт, Белград и Катовице (Польша). И везде билеты + проживание - за счет универа
792969
#22 #792922
>>792879
А сейчас люди получают WA на том, что ОЙ А ТУТ ФАЙЛЫ НУЖНЫ. Или ОЙ Я ФАЙЛЫ НЕ ЗАКОММЕНТИЛ (хотя нормальные пацаны юзают препроцессор для этого).
Хотя без файлов таки удобнее, да, жаль, что не везде так сейчас
792952
#23 #792938
Добавьте в шапку http://dl.gsu.by/
Сайт крут тем что там дохуй задач и он показывает количество пройденых тестов. Даже на сами тесты можно посмотреть.
#24 #792952
>>792922
но вооще, где-нибудь в лине можно было бы перехватывать пару функций в libc и на любое имя файла давать один путь. наверняка и в винде такое можно провернуть.
#25 #792953
Самый опущенный тип айтишников это олимпиадники.
792968
#26 #792956
>>792733

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


> чистый Си

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

>>792953
Толсто.
#28 #792969
>>792919
В Москву эту куда, на МФТИшные сборы да на четверть, если рядом живёшь?
792981
#29 #792981
>>792969
Да, МФТИшные сборы, они самые. Сам из Питера, поэтому четверть пишу у себя
#30 #793026
сап, вопрос такой
вот на соревах стоят ограничения по памяти
но
в jvm языках же сама jvm автоматом отжирает до пизды памяти
получается jvm-блядки априори сразу сосут?
793033
#31 #793033
>>793026
Да. Алсо, ты ещё забыл про инициализацию машины, тоже время отжирает. Выбор языка в любом случае за тобой + ситуации, когда задача решается на С и не решается джавой, крайне редки.
793042
#32 #793038
олсо я совсем зеленый не понимаю пока как вкатиться
видел советуют книгу Шеня, она ок?
793047
#33 #793042
>>793033
Это в случае, если ТЛ для Джавы стоит раза в 2 больше, что некоторые Online Judges делают по дефолту. А вообще зависит еще и от автора. Если он напишет какое-то заоптимизированное решение на плюсах и поставит жесткие ТЛи чтобы отсечь другое решение с чуть большей асимптотикой, то Джавакодеры соснут
793047
#34 #793047
>>793038
Иди сразу на кодфорсы, читай параллельно емакс, дорешивай задачи и читай разборы. Для начала сойдёт, когда дело дойдёт до уровня суфавтоматов, уже сам разберёшься, что делать.

>>793042
СОКОБАН)))0)
793056
#35 #793052
Зачем нужно олимпиадное программирование, если все держится на библиотеках и фреймворках? Оно же абсолютно не нужно в реальном мире. Лучше потратить время не на подготовку и дрочку алгоритмов, а на прикладную разработку и на свой гитхаб.
793060793063
#36 #793053
>>792098 (OP)
В спортзал и к стилистам всех четверых. Футболки блядь на халка, пошить соразмерные. Крайнему слева в жопе похудеть, перестать жрать говно, перейти на салатики и мясо. Бородачу как минимум выровнять бороду.
793060
#37 #793056
>>793047
друг, где читать разборы? я заходил на рашен кап чето там, но там объяснение мне показалось уже для чуваков которые прорешали пару десятков контестов
793060
#38 #793060
>>793056
На кодфорсах почти к каждому контесту пилят разбор авторы. Кроме этого, не стесняйся в случае чего спрашивать в комментах: пост вынесет на первое место в секции комменты, его увидят и ответят с вероятностью 99%.

>>793052

>абсолютно


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

>>793053
Котёнка лучше не трогать, где ещё такое встретишь, при том что он относительно молод.
793065800596
#39 #793063
>>793052
Писали же кучу раз
Школьникам есть однозначные профиты которые не очень сложно получить, да и олимпиадки на таком уровне таки сильно влияют на прогерские навыки
Студентам - хобби, помощь на собеседованиях.
Да и полезно таки некоторые алгоритмы писать самому, чтобы понять как работает что-то. Опять же, навыки писать оптимальный код на плюсах
#40 #793065
>>793060
Я не говорю про алгоритмы, они то очень нужны, я говорю про олимпиадную дрочку, которая вырабатывает плохой стиль кода (попробуй попиши читаемый код на время) и бесполезна в реальном мире.
793073
#41 #793073
>>793065
А, ну в этом плане может быть.

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

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

>как, например, std::ios::sync_with_stdio


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

Вот про питон можно долго говорить, там абсолютно неочевидные вещи происходят.
#44 #793658
Ребят, а я вот наоборот олимпиадник, а в промышленном полный ноль :с
793729793817
#45 #793729
>>793658
Че ты врешь?
#46 #793817
>>793658
Ну ты же наверняка понимаешь почему так, или есть хотя бы предположения.
Просто не нравится?
Вполне вероятно, что ты просто мало промышленно кодил, тогда это нормально. В олимпиадках ты ж тоже не сразу начал норм участвовать наприер
#47 #795326
>>792098 (OP)

>Конкретная математика


первая же задачка - мой пердак в небесах, ответ на неё - подлетаю к юпитеру. это просто пиздец какой-то.
796208
#48 #795372
Не смог решить вторую по сложности с начала задачу на тимусе.
Задавайте свои ответы
795402796211
#49 #795402
>>795372
обратный корень?
она сложная так-то, там на пушбэк поп
795406795516
#50 #795406
>>795402
что такое пушбэк поп?
я на си пытался решить
795516
#51 #795516
>>795402
Блять, ты тролль или ты серьезно?
Пиздец просто, >на пушбэк поп
Техника имени Семена, блять. Это как про любую задачу сказать "это задача на инт мейн", поеботень полная

>>795406
Тебе надо знать, что такое массивы, как считывать-выводить вещественные числа, и как извлекать корень.
Первое - это лучше погугли и почитай в нормальном месте туториалы по языку, если таких основ не знаешь
Второе - считывать так:
double a;
scanf("%lf", &a);
и писать
printf("%f", a)
На самом деле, это верно для 11+ стандартов, в старых стандартах и читать и выводить с помощью %lf вроде
Третье это
#include <math.h>
...
a = sqrt(23.9);
796271
#52 #796208
>>795326
кинь задачу
797322
#53 #796211
>>795372
Я максимум решал 1010+ сложности на тимусе. Я успешнее
25 Кб, 441x373
#54 #796271
#55 #796352
Как найти кратчайший маршрут между двумя вершинами в бинарном дереве?
796398796935
#56 #796398
>>796352
Что такое бинарное дерево?
Я не понимаю зачем обсираться в присядку, одновременно обмазываясь говном и дрочить на коколимпидаки и нахуй не нужные алгоритмы
796832
#57 #796832
>>796398

>Что такое бинарное дерево?


На пике.

>>796427

>единственный маршрут


Из 9 в 2 можно идти пом пути 9 4 2 1 2.

>Находишь всех предков обоих вершин.


Не эффективно. Должен быть способ быстрее.
796833
2 Кб, 580x338
#58 #796833
>>796832
пик забыл
#59 #796909
>>796903
А нет его в памяти. Даже размер не известен. но в long long влазит. Выглядит как на той картинке. Наверно просто максимальный надо делить на 2 пока они не сравняются.
#60 #796917
>>796914
Числа между которыми маршрут прокладывать. Вывести нужно сам маршрут.
#61 #796921
>>796920

>Похоже, что это задача на пушбэк.


Скорей всего на int main() и return.
796926
39 Кб, 421x480
#62 #796926
>>796920
Ага. И я уже понял как решать. Поэтому спасибо и пока.

>>796921
Ну это же не вся задача.

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

>>795392
просто это математика, мне сложно, нужно по другому мыслить, немного перестроить голову.
797533
#65 #797533
>>797322
Это же очевидно, неверная база индукции. Самый первый переход для n=2 не работает, базой должен быть именно этот случай, что невозможно.
800954845016
#66 #797534
>>796935
Тарьян offline, лучше всё-таки на sparse table делать.
#67 #797948
Сап, посоны, пишу алгоритм Дейкстры. Что я делаю не так? Должно выводить 24 3 15, а выводит 24 32 20. Нумерация вершин с единицы.

https://ideone.com/eGhmMK
797964
#68 #797964
>>797948
Граф ориентированный или нет? У тебя в коде он ориентированный, а в задаче как? Видимо, в ней он неориентированный, тогда надо делать
adj_list[begin].push_back (make_pair(end, weigth));
adj_list[end].push_back (make_pair(begin, weigth));
У тебя нет второй строчки
797969
#69 #797969
>>797964
Неориентированный, и еще допустимы мультирёбра, но в тестовых данных для примера мультирёбер нет. Какие изменения в алгоритме надо сделать, чтобы обрабатывать мультиграфы?
797975
#70 #797975
>>797969
Эм. Никаких (зачем?). А вот тот фикс, что я предложил, сделать таки надо.
797980
#71 #797980
>>797975
Да, этот фикс помог. Матрица неорграфа симметричная, и списки тоже делаются симметрично.

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

https://ideone.com/pJfxfM
797984
#74 #797984
>>797982
А, скорее всего, я вывожу INF там, где по условию надо выводить -1. Сейчас проверю, должно помочь.

И все-таки странно, что авторы обращают внимание на то, что могут попадаться мультиграфы.
798007
#75 #798007
>>797984
Ну например это может быть важно в случае, если человек юзает матрицу смежности вместо списка смежности хотя тогда бы по TL бы не прошло скорее всего. И, как правило, в задачах по умолчанию граф простой, поэтому выделение того, что есть кратные ребра, является некоторым правилом хорошего тона, можно сказать.
#76 #798379
Посоны, смотрите.
На двумерной плоскости имеем набор многоугольников с float координатами. Как определить, находится ли точка внутри какого-либо многоугольника?
798380798618800887
13 Кб, 798x535
#77 #798380
>>798379
Отклеилось.
14 Кб, 798x535
#78 #798438
>>798398
Да, вспоминаю про трассировку луча. Но тогда ведь нужно проверять каждую грань каждого многоугольника?
Хотя можно применить небольшую оптимизацию и проверять только те многоугольники, с проекциями которых есть пересечения. Или еще лучше, с проекциями сторон которых есть пересечения.
В общем, спасибо, навел на мысли.
798441
14 Кб, 798x535
#79 #798441
>>798438
Точнее мы тут можем даже до одного сократить.
#80 #798618
>>798379
Если они выпуклые, то для каждого многоугольника можно делать проверку за log(число вершин)
#81 #800440
Если задачу на кодфорсе взломали, то это хорошо т.к. она бы завалилась на основных тестах, а так есть возможность узнать об ошибке и доделать её?
800520800887
#82 #800520
>>800440
Именно так, если ты ее не заблокировал, конечно
#83 #800574
Когда разбор сегодняшнего кодфорса запилят (див2)? Где его смотреть?
800579800887
#84 #800579
>>800574
Там разборы бывают? А див1 есть?
800596
#85 #800596
>>800579
Вот тут сказали, что бывают: >>793060
Я хз, сегодня впервые написал.
#86 #800605
Чо, обидно, со второй задачей вышло?)))
#87 #800887
>>798398
Проще, но на этот способ любят делать контртесты. Надёжнее пускать в рандомном направлении.
>>798379
Я всегда использовал сумму полярных углов. Тема такая, для каждой грани ты считаешь, под каким ориентированным углом она видна из точки. Дальше считаешь сумму, если получилось 0, то ты снаружи, если 360 градусов – внутри. Случай на грани рассматривается отдельно.
>>800440
Бывает, что ломают решения, которые не валятся на тестах.
>>800574
Разбор появляется от сразу до нескольких дней, пали комменты к посту о контесте, там обычно спрашивают такие вещи.
803666
#88 #800954
>>797533
мне сложно, а вот если есть задача - я могу её решить, как там написано, и так же индукцией доказать - не проблема. но когда меня спрашивают, например докажите что в задаче на столбы, используются все возможные комбинации - вообще не ебу как. да, для меня очевидно, что вот число и его бит может иметь 3 значения, тогда число с n бит имеет 3^n-1 возможных комбинации - даже не представляю как это доказывают.
801184
#89 #800963
>>800960

> Почему 3, а не 2?


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

> Откуда -1?


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

> А ты попробуй индукцией


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

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


класть на меньший.)

> 3 Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения нам встретятся все допустимые варианты размещения n дисков на трех колышках.

800966
#90 #800966
>>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 <- это

или что под этим ещё понимается?
800967
#91 #800967
>>800966

> T(1) = 2

#92 #800977
>>792098 (OP)
2 справа бы трахнул нет
#93 #800978
Т.е слева -_-
#94 #801184
>>800954
Ничего не понял, кинь условие задачи, или что ты там доказываешь.
#95 #801272
>>792098 (OP)

>Грэхэм, Кнут, Паташник "Конкретная математика"


Этой книги достаточно, чтобы понимать анализ алгоритмов, всякие асимптоты и прочее из следующей книжки? Или придется до кучи ещё математики наверстать? Мой уровень если что на уровне девятиклассника, лол.
#96 #801315
>>801308
Угу. А асимптотика там обсуждается аж в последней главе.
Как я и думал, все эти алгоритмы и интеллектуальные игры с ними для элиты, которую с рождения обучают не тому, что дают в обычной быдло-школе. Пойду дальше в дотку катать.
801396
#97 #801396
>>801315
Просто начни с книжек попроще. "программирование: теоремы и задачи" Шеня, а потом вот это http://codeforces.com/blog/entry/12314
Ну и перед этим учебник школьный по математике, если совсем неуч.
801628
#98 #801628
>>801396
Спасибо. Я настолько тупой, закончил школу, а не могу решить задачи с acmp.ru которые сложнее 30% по их шкале.
#99 #801684
Зарегался на этом вашем кодефорсес. Где там выбирать задачи по уровню сложности и тематике?

Алсо, есть там что-нибудь по преобразованию Фурье?
801705801721
#100 #801705
>>801684
Есть задача "ДНК роботов", поищи по названию.
801721
#102 #803666
>>800887

>Бывает, что ломают решения, которые не валятся на тестах.


Ну вот. Ты меня запутал. Чётно обфусцирую решение на следующем контесте, а нечётно нет.
803822
#104 #803822
>>803666
После множества таких казусов с недавних пор все успешные похеки добавляются в набор финальных тестов.
#105 #804385
>>803678
круто, жаль что я не видел этого в школьном возрасте
#106 #805600
Есть ли простой алгоритм быстро возвести матрицу в квадрат?
Вот две произвольные матрицы либо за эн в кубе умножать, либо хитрый алгоритм. А тут может попроще?
805622
#107 #805622
>>805600
Нет, нельзя, насколько я знаю. Есть только, как ты сказал, хитрые алгоритмы, либо частные случаи типа метода четырёх русских.
805626
#108 #805626
>>805622
Ну у меня вот как раз частный случай, две одинаковые матрицы умножаем.
805633805635
#109 #805633
>>805626
Я понимаю, вот и говорю, что я, по крайней мере, никогда о таком частном случае ничего особенного не слышал. Пиши Штрассена или гугли научные статьи на эту тему.
805635
#110 #805635
>>805626
>>805633
Впрочем, можешь ничего не гуглить, вот ответ на твой вопрос http://math.stackexchange.com/questions/20873/whats-the-fastest-way-to-take-powers-of-a-square-matrix
#111 #807910
бумп
#112 #810133
>>792098 (OP)
Рассказываю, почему я бросил олимпиадное программирование. Когда я начинал, то думал, что там задачи чисто на смекалку, для решения которых не требуется никаких предварительных знаний. Но это оказалось не так. Есть определенное количество узкоспециализированных тем, например, динамическое программирование или древовидные структуры данных, в которых надо быть хорошо прошаренным, чтобы решать олимпиадные задачи. Если кто не понял, что я сказал, приведу такой пример: если вы попытаетесь доказать хотя бы теорему Пифагора, ничего о геометрии не зная вообще, то у вас ничего не выйдет. Так вот я задумался однажды, стоит ли задрачиваться в темах, которые котируются на олимпиадном программировании, если они мне скорее всего не пригодятся в работе. Лучше уж потрачу это время на изучение чего-нибудь более практичного.
810507810715
#113 #810507
>>810133
зря бросил, ящитаю
810676
#114 #810676
>>810507
Я бы не бросал, если бы было много свободного времени, но его нет.
#115 #810715
>>810133
Ты прав, в принципе, если не считать, что в некоторых местах типа яндекса и вк олимпиадников очень любят. Да и в целом на базовом уровне почти везде спрашивают, но базовый CS и так все должны знать просто по роду профессии.
812714
#116 #812714
>>810715
Тут замкнутый круг.
В "базовый CS" входит комбинаторика, теория чисел, графы, динамическое программирование. Это активно используется на олимпиадах и во всяких гуглах. Но никак не изучается глубоко в вузах (кроме парфеновской кафедры и еще схожих) и не применяется в рф-it. Кроме сам знаешь где. Тоесть олимпиадное программирование, или тот же Скиена, это единственный способ рф-студенту окунуться в то "а что же там пишут в гуглах, что у нас нет". Да и без олимпиадной подготовки ты будешь о-о-чень долго вникать во всякие crack the coding interview и elements of programming interview.
#117 #812961
Аноны, подскажите алгоритм: дано произвольное количество 2d-вершин, нужно из них сделать многоугольник с непересекающимися гранями.
813017824539
#118 #813017
>>812961
построение выпуклой оболочки
813104
11 Кб, 652x512
9 Кб, 652x514
#119 #813104
>>813017
Вроде это не совсем то. Все точки должны быть задействованы.
Я написал примитивный алгоритм: проходим по точкам, отсортированным убывающе по y, и соединяем ближайшие по x, но иногда он фейлится.
813134
#120 #813134
>>813104
Берёшь самую нижнюю-правую точку, ставишь её как начало координат. Считаешь полярные координаты остальных точек относительно центра. Сортируешь по углу, обходишь в этом порядке.
Дядя Сэджвик с Курсэры так учил
813163
#121 #813163
>>813134
Я походу проще вариант нашел: пространство делится на 2 части по x (можно взять тупо width/2), слева и справа строятся ломаные кривые и потом соединяются.
813164813177813255
#122 #813164
>>813163

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

#123 #813177
>>813163
Хотя тупо width/2 будет ошибкой, нужно чтобы хотя бы 2 точки было на одной из сторон.
813183
#124 #813183
>>813177
Хотя нет, полностью неправильно, лел.
Ладно, буду думать.
#125 #813245
>>792098 (OP)

> эти плечи

813260829342
#126 #813255
>>813163
хуйня решение же очев
813287
156 Кб, 650x445
#127 #813260
>>813245
матрас из денег всё справит
20 Кб, 651x514
#128 #813287
>>813255
Все нормас, быстрейшее из всех, O(n).
Проблема была только в разделении. Надо делить линией, которая проходит через самую верхнюю грань и через самую нижнюю. Теперь все без ошибок.
813300817083
#129 #813300
>>813287
Теперь докажи корректность.
По-моему у тебя просто жадная эвристика.
813319
#130 #813319
>>813300
Я думал о корректности.
Из любого набора разных точек можно сделать ломанную линию с непересекающимися кусками, соединяя точки одна за другой в одном направлении. Пересечений гарантированно не будет, если между точками в этом направлении нет других точек.
Мы получаем две ломанных линии, не пересекающиеся между собой. Вопрос только в том, можем ли мы безопасно соединить их концы. Ответ: да, т.к между концами больше нет других точек, т.к. мы заведомо взяли 2 верхние и 2 нижние точки и от каждой начали строить линию.
И все же это не n, а nlogn, т.к. надо сначала отсортировать точки в одном направлении.
815449
#131 #815449
>>813319
Занятно, я всегда пользовался сортировкой по полярному углу. Сложность такая же, но алгоритм ка будто чуть попроще, нет двух частей, тупо сортировкой сразу достигаешь нужный порядок с другой стороны, может быть критична скорость работы с float
817702
#132 #816915
Mathematica
(1/Pi) Integrate[((Sin[10x] )/Sin[x])^6, {x, 0, Pi}]
Счастливых билетов: 55252
816923
#133 #816923
>>816915
Элегантно, только погрешность численного интегрирования точность подпортила.
817310
6 Кб, 539x416
#134 #817083
>>813287
А вот в таком случае ты что делаешь? Чёрное - как получается по твоему описанию, зелёное - как должно быть.
817667
#135 #817310
>>816923
А интегрирование аналитическое, без погрешностей.
Хотя если оценить вид первообразной и по пределам оборвать, то можно свести все к вычислению 1109369452791600/20078358300
#136 #817555
Зо o(n) низя т.к. если можно то можно числа за o(n) сортировать а так низя потому что низя
5 Кб, 971x362
6 Кб, 794x310
#137 #817667
>>817083
Нет, все верно у меня.
Главное не ошибиться с выбором лево-право у крайних отрезков. Я сначала выбирал тупо - если p1.x < p2.x, то p1 уходит влево, но это не всегда так. Пример на второй пикче.
0 Кб, 112x102
#138 #817702
>>815449
Понял твое решение, скорее всего, оно лучше.
Хотел придумать корнер-кейс, но сам же на него ответил. При равенстве угла, если он [0; 90], то сортируем по Y возрастающе, если же больше, то убывающе.
818434
#139 #818434
>>817702
Можно и по убывающей, без разницы, главное чтобы в одном направлении.
818436
#140 #818436
>>818434
Допустим, мы проходим против часовой стрелки от нижней точки. Если мы сначала возьмем по убывающей, то получатся вершины 1-3-2, что уже ошибка, я это имел в виду.
#141 #822144
Есть правильная скобочная последовательность и внутри неё есть мусорные данные. Для удобства есть ассоциативный массив в котором каждой зная координату одной скобки можно найти координату соответствующей ей скобки. Иногда нужно удалять мусорные данные. И когда это происходит, то размер строки и координаты некоторых скобок меняются, а ассоциативный массив нет. Как максимально быстро вернуть корректные значения в ассоциативный массив?
Пример
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к символов. А вот время нужно экономить т.к. важна каждая миллисекунда.
Как решить?
822569822710
#142 #822569
>>822144
Что за "ассоциативный массив", он совсем медленный, или можно к нему обращаться лишний раз в процессе апдейта?
Пока вижу так: держим массив с координатами всех скобок. Когда надо делать апдейт находим бинарным поиском первую скобку правее места удаления, и начиная с неё до конца массива фиксим каждую скобку.
То есть:
1. Уменьшаем адрес каждой скобки на размер удалённого куска. Скорее всего это подразумевает удаление записи из ассоциативного массива, и добавление новой с другим ключом.
2. Если это закрывающая скобка, а соотв. открывающая левее точки удаления, то обновляем сдвиг в открывающей.
3. Уменьшаем адрес скобки в нашем вспомогательном массиве на размер удалённого куска.
822616
#143 #822616
>>822569

>он совсем медленный


Совсем быстрый. За константу обращение.

>бинарным поиском


И как им искать скобки в не отсортированной строке?
И работает это долго и не правильно.
Вот тест ((abc)()) После удаления любой буквы скобки выделенные жирным трогать не надо. Пока думаю делать вспомогательный массив где отсортированы координаты всех закрывающихся скобок.
Вот например тест "((a)b(c)d)" и удаляем b. В вспомогательном массиве будет 3 7 9. С помощью ассоциативного узнаём координату закрывающейся скобки и проверяем есть ли между ними удалёный элемент. Так должно быть быстрее, но после каждого удаления заново по массиву проходить не хочу, а как после всех удалений применить этот метод не знаю т.к. удалять можно несколько элементов подряд и их потом ещё запоминать придётся.
822719
#144 #822710
>>822144
Всё зависит от требований: много запросов – меняй за линию, это как угодно можно делать, быстрее за раз всё обновить нельзя, будешь на запросы за 1 отвечать. Много удалений, мало запросов – делай вспомогательный массив "текущей версии" для каждого индекса, и вспомогательное дерево типа дерева отрезков для "обновления" индексов за логарифм и взятия за логарифм (с дальнейшей записью в оригинальный массив и обновлением номера версии, чтобы между вырезаниями только один раз каждый индекс заново считать).
822716
#145 #822716
>>822710
А как сделать чтобы пока поступают запросы просто заменяешь символы на пробел, а потом за раз всё удаляешь и скобки корректируешь? Это быстрее всего должно работать. Запросы обычно не большие. Несколько байт. Но может много запросов на небольшой участок строки быть.
#146 #822719
>>822616

>И как им искать скобки в не отсортированной строке?


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

>И работает это долго


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

>и не правильно


>После удаления любой буквы скобки выделенные жирным трогать не надо.


В ассоциативном массиве были записи 6:1 и 7:-1, а должны стать 5:1 и 6:-1, само по себе оно не обновится.
#147 #822781
Анончики, может у кого есть нормально отформатированная Конкретная математика в mobi/epub или прочем ebook формате? Я искал, форматировал и все тщетно. А пдф читать на 6 дюймовом киндле не шибко удобно и приятно. Заранее спасибо за ответ.
#149 #824692
Вчера писал свой первый раунд на Codeforces, почувствовал себя дауном. Первая задача простая, ну действительно, чего ее решать, давайте посмотрим остальные. Вторая про графы, чет как-то слишком длинное условие, сложна. Третья про пифагоровы тройки. И тут я засел. Родил какое-то стремное решение через числа Фибоначчи (спасибо Википедии за это), а оно зависает на всех нечетных, а на четных выдает не всегда верные ответы. В итоге два часа просидел над этой задачей, ничего не решил, а когда открыл разбор - охуел от простоты и изящества. Это лечится или мне навеки оставаться тупым?
#150 #824693
>>824692
Поступил на программиста, называется.
Мама, мама, я буду кодить!
#151 #825552
>>824692
лечится. одноклассник не умел решать ничего кроме a и иногда b, а через 1.5. года стал призером всероса.
#152 #825960
>>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, я не понимаю.
825975
#153 #825975
>>824692
>>825960

> а когда открыл разбор - охуел от простоты и изящества.


Какое изящество, тут просто надо знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает, это знают только всякие дрочилы, которые нарешивают олимпиады по математике для школьников.
826006831614
#154 #826006
>>825975
А если какие-нибудь методички, в которых подобные тайные знания раскрываются?
826056826059
#155 #826056
>>826006
Не трать на это время, это полная хуйня. На cf есть нормальные задачи на какие-то определенные темы, решение которых помогает в понимании этих тем. То есть это задачи на какие-то алгоритмы или структуры данных, а не на знание того, что нечетное число можно представить в виде разности квадратов. Просто нужно уметь отличать хуету от нормальных задач.
#156 #826059
>>826006
скиена "олимпиадные задачи по программированию"

>>824692
Я как-то хантился в майкрософт, к Дену Расковалову.
https://www.linkedin.com/in/raskovalov/ru
Он говорит, что только масштабы и время. Тоесть кодфорсес к собеседованиям мало отношения имеет. Так что чтобы решать олимпиады нужно быть задротом и дрочить много именно задачки. Там может быть ад на теорию чисел и комбинаторику. Как в прожект ейлера. После 300 задачек начнешь уже решать без задней мысли. А это полгода дрочильни где-то.
826076826077
#157 #826076
>>826059
Спасибо.
#158 #826077
>>826059
А что там на собеседованиях спрашивают? Понятно, что разглашать конкретную информацию нельзя, но разгласи неконкретную.
826087
#159 #826087
>>826077
http://poincare.matf.bg.ac.rs/~jelenagr/ASP/testHeadHunter.pdf можешь начать тут, а потом careercup.com
826116826898
#160 #826116
>>826087
послал бы нахуй за такие вопросы на собеседовании
#161 #826898
>>826087
Говно. Не нашёл вопроса про то, в какую сторону едет автобус.
#162 #826995
>>792098 (OP)
Здесь обсуждают олимпиаду для поступления в вузы ?
836961
#163 #827714
Начал решать задачи на тимусе для закрепления знаний Си.
Как в Си вычислить корень 876652098643267843 ?
http://ideone.com/XVSbT2
827719827727
#164 #827719
>>827714
long long int a;
самспросилсамответил
#165 #827727
>>827714
Пиздец быдлокод.
828637
#166 #827759

ХОДИШЬ ТАКОЙ НА ОЛИМПИАДЫ, БЕРЕШЬ ПРИЗОВЫЕ МЕСТА
@
ПРИГЛАШАЮТ РАБОТАТЬ В ЯНДЕКС
@
ПОСЛЕ НАПИСАННОГО ТОБОЙ ОБНОВЛЕНИЯ У ВИНДОВС ПОЛЬЗОВАТЕЛЕЙ СЛЕТАЕТ ВИНДОВС СО ВСЕМ СОДЕРЖИМЫМ ДИСКА Ц
@
С ПОЗОРОМ УВОЛЬНЯЮТ
@
КАРЬЕРА В ИТ ДЛЯ ТЕБЯ ЗАКОНЧЕНА, ПИЗДУЕШЬ РАБОТАТЬ ДВОРНИКОМ
827819
#167 #827819
>>827759
ПОСЛЕ ПОДМЕТЕННОГО ТОБОЙ ПОДЪЕЗДА ПОЛОВИНА ЖИТЕЛЕЙ ПОСКАЛЬЗЫВАЮТСЯ И ЛОМАЮТ НОГИ
@
С ПОЗОРОМ УВОЛЬНЯЮТ
827826
#168 #827826
>>827819

@
НЕ ОСТАЕТСЯ НИЧЕГО ДРУГОГО, КАК СТАТЬ НАЕМНЫМ УБИЙЦЕЙ ЗА ДОЗУ ГЕРОИНА
@
ЦЕЛЬ ИЗЛЕЧИВАЕТСЯ ОТ БОЛЕЗНЕЙ ПОД ТВОИМИ УДАРАМИ
@
ВЫГОНЯЮТ БЕЗ ПЕНСИИ
#169 #828637
>>827727
Рекурсивная функция в две строки, решающая одну из первых задач с тимуса. Что доебался до него?
Разве что while я заменил бы на простой if
#170 #829298
На джаве кто-нибудь пишет? Поможете сопитимизировать? У меня TL.
http://codeforces.com/contest/709/problem/E
http://pastebin.com/pW573vzV
Время работы там O(n), в этом точно косяка нет. Я заменил рекурсию на while + stack, потому что до этого был stack overflow. То что инпут с помощью Scanner - это норм, потому что если бы инпут не успевал, у меня бы не доходило до stack overflow в первой версии. От лямбд я уже пробовал избавляться, тоже TL.
829301829344
#171 #829301
>>829298
Хотя сейчас замерил, инпут занимает 2 секунды. Сейчас попробую сканер заменить на что-то побыстрее.
#172 #829342
>>813245
Широковаты. Я от своих тоже в бугурт впадаю.
#173 #829344
>>829298
Оберни System.in в BufferedReader
829347
#174 #829347
>>829344
Сделал. Сначала не сдалось, но потом я еще обернул System.out в BufferedOutputStream и сдалось.
829616
#175 #829596
Поясните зашквар или нет вставлять в резюме ссылку на свой профиль на codeforces? Устраиваюсь не в какой-нибудь яндекс, а обычным крудошлепом.
829615
#176 #829615
>>829596
Какой рейтинг?
830000
#177 #829616
>>829347
Не понял. А почему BufferedReader не помог? Какая выгода от BufferedOutputStream?
829999
#178 #829999
>>829616
Помог, где-то на полторы секунды быстрее стало, но этого было недостаточно.

> Какая выгода от BufferedOutputStream?


В этой задаче аутпут 400000 и выводится по 1 символу, а это очень долго. А buffered сначала ниче не выводит, а когда делаешь flush, выводит все сразу.
#179 #830000
>>829615
Максимум 1650 было.
#180 #831614
>>825975

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


Если ты не знаешь, что комбинаторный интеграл от 2n+1 равен n(n-1)+n, что ты вообще делаешь в этом треде?
831764832261
#181 #831764
>>831614
Хуйня для дрочил или специалистов по комбинаторике. Вот ты сколько статей уже написал?
#182 #832261
>>831614

>комбинаторный интеграл


Чоблядь?
Интеграл от 2n+1 равен n^2+n+C, чо ты мне загоняешь? и что за хуйню ты написал, n(n-1)+n = n^2
#183 #832469
Это шутка была (про то, что все знают, что такое комбинаторный интеграл). Но то, что (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
Подсказка: интегрирование по частям.
#183 #832469
Это шутка была (про то, что все знают, что такое комбинаторный интеграл). Но то, что (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
Подсказка: интегрирование по частям.
#184 #832679
Циановый даун с кодефорсеса цвета морской волны ищет боевого товарища, чтобы в соревновательно-помогательном режиме ботать прогу. По заявкам оставляю фейко-контакты
832722
Аноним #185 #832722
>>832679
Это сколько, 1200-1400 что ли? Могу просто так тебе помочь если че, спрашивай. Я максимум был синим.
832725
#186 #832725
>>832722
1400 - 1600. У меня вопросов особо нет. Надо только надрочиться. А одному это уныленько.
832845
#187 #832845
>>832725
Ты хочешь сказать, что у тебя в городе нет ни одного места, куда можно ходить на тренировки по асм?
833063
79 Кб, 963x329
#188 #832963
833376
#189 #833063
>>832845
Есть. Но этого разве достаточно?
#190 #833204
>>792098 (OP)
Кажется правого кунца я видел в МИРЭА, он там курс по android ведёт.
Так ли это?
833281
#191 #833281
>>833204
Нет, я сомневаюсь, что Егор будет вести курс по Android в сраном МИРЭА.
#192 #833376
>>832963

> 5 лет назад


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

Тупая задачка. Почему нельзя просто прибавить ко времени старта врем полета, а потом прибавить разность номеров часовых поясов?
834035834036
#194 #834035
>>834027
Все, разобрался. Идите нахуй
#195 #834036
>>834027
А кто тебе сказал, что нельзя? Летал самолет или нет, значения не имеет, от этого разница во времени между часовыми поясами не изменится. Здесь просто спрашивается, какое время будет в другом часовом поясе через n-цать часов. И какое все это имеет отношение к погромированию?
#196 #835570
Эй, умники. Есть задачка. У нас имеется n целых неотрицательных чисел, чья сумма не превосходит 10^5. Еще есть некое m до 10^4. Все эти n чисел мы хотим представить в виде целых долей этого числа m, причем нецелые доли мы вольны округлять в любую сторону по желанию левой пятки. Я тут набросал тупой жадник, который, конечно же, доказывать не умею, и он отхватывает wa2. Жадник настолько тупой, что он все округляет вверх, а потом, переокругляет вниз пока не получим нужную сумму, равную m
http://ideone.com/3x53a2
836275
#197 #836275
>>835570
Дай ссылку на исходную задачу, потому что ты во-первых написал условие как мудак (блядь, неужели нельзя скриншот запостить хотя бы, и пару примером входа выхода), а во-вторых лучше засабмитить, чем какому-то петуху объяснять.
836278
175 Кб, 1366x768
#198 #836278
>>836275
Ну, вот тебе скриншот. А самой задачи на публичных тестилках я не видел. Свой жадник пока что я опровергнуть так и не смог
836282
#199 #836282
>>836278
Ну вот так-то лучше. Сам-то чувствуешь, что гораздо понятнее выглядит? Очевидная динамика же.
836283
#200 #836283
>>836282
Я, конечно, толком в динамику не умею. Но тут и намеков не вижу. Не просветишь?
836284
#201 #836284
>>836283
Хотя тут даже динамика не нужна, жадный алгоритм должен работать. У тебя, наверное, просто не проверяется, что если число нацело делится, то его двигать нельзя уже.
836287
#202 #836287
>>836284
Так ceil же не должен целое число округлять. Или там с точностью может быть лажа?
#203 #836289
Ну динамика, если интересно, такая: f(arr[i:], amount) - можно ли набрать amount сумму, округляя как-нибудь числа начиная с i-й позиции, как в рюкзаке, и по времени проходит - 50е6. Только, повторяюсь, она тут не нужна.
836291
#204 #836291
>>836289
А ты потом даже от целых чисел берёшь и отнимаешь 1 на 25-й строчке.
836293836294
#205 #836293
>>836291
http://ideone.com/0pI4qN
Больше не отнимаю. Но как-то не.
836295
#206 #836294
>>836291
Высрал контрпример http://ideone.com/kRzC4I
836295
#207 #836295
>>836293
Не канает, см >>836294
836302
#208 #836302
>>836295
Да. Я уже вижу. Спасибо, мил человек
#209 #836425
Сколько сюда не захожу, так и не пойму, чем вы тут занимаетесь
836961
#210 #836961
>>826995
Почему бы и нет.
>>836425
Спортом вестимо.
836973
#211 #836973
>>836961

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



Игра в доту — это спорт. Решение олимпиадных задач по программированию — это не спорт. Выводы делай сам.
#212 #839646
У всех cf лежит?
839721
#213 #839721
>>839646
Нет
840310
#214 #840310
>>839721
Пидора ответ.
#215 #840732
Как научиться решать CTF?
840861
#216 #840861
>>840732
Приходишь на ctf. Дальше все понятно.

Серьезно. Обычно есть отборочные туры, где есть возможность гуглить
840875
#217 #840875
>>840861
Ладно. А что там знать и уметь надо?
840879
#218 #840879
>>840875
Идешь на отборочный тур и узнаешь. Там бывают разные задания: криптография, сети, крекинг етц
284 Кб, 1366x768
#219 #843105
Олимпач, я тебе задачу подвез. Пока из идей посортить стержни по максимальному расстоянию от конца до точки d, а потом как-то хитро посчитать. Хитро что-то не выдумывается
843169
#220 #843169
>>843105
Допустим все числа нечетные, тогда просто расположим их так, чтобы их середины находились на оси x и будем зажигать от самого длинного к самому короткому. Допустим, нечетные, тогда то же самое.
Допустим есть четные и нечетные числа. Например, 2 стержня 4 и 5. Тогда придётся все числа той же четности, что и максимальное, зажечь с одного конца, чтобы сделать всех одной четности, а потом применить алгоритм из первого параграфа.
843189
#221 #843189
>>843169
С четными и нечетными я хуйню написал.

Короче зажигаешь самый длинный стержень с двух сторон, а дальше изъебывайся как хочешь, но чтоб все в один момент лопнули. Это можно сделать.
В первую секунду зажигаешь самый длинный стержень с двух сторон, а стержни длины на 1 меньше - с одной стороны, во вторую секунду все стержни которые горят с одной стороны поджигаешь со второй, а все стержни на 1 меньше - с одной стороны. И так далее.
843304
125 Кб, 1366x768
#222 #843304
>>843189
Вот это вот, судя по всему, верное решениие
843355
#223 #843355
>>843304
А, там ещё и определённая точка должна загореться последней, вот я мудак.
sage #224 #845016
>>797533
ты ебанулся? база индукции очевидно верная. переход не верен (при п=2)
#225 #846398
Я умею искать гамильтонов путь в неорграфе динамикой по подмножествам, где вершин не больше 20. А вот теперь мне надо проверить наличие гамильтонова пути в ацикличном орграфе с количеством вершин вплоть до 10^5. Вроде простая задача должна быть. Думаю пока в сторону топсорта какого-то
846526846535
#226 #846526
>>846398
Сравни длину длиннейшего пути с количеством вершин + 1.
https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths
846535846934
#227 #846535
>>846398
>>846526
Честно говоря не понимаю зачем пишут топсорт делать. Наверное чтобы достичь O(N) вместо O(N*log(n)).
По идее достаточно для каждой вершины предрасчитать списки входящих соседей (если вершин с пустым списком >1, то гамильтонова пути сразу нет), а потом пока есть нерассмотренные вершины берёшь рандомную считаешь расстояние от истока до этой вершины как максимум среди её входящих соседей+1. Применяешь алгоритм рекурсивно, не забывая про мемоизацию.
Короче как поиск кратчайшего, только длиннейшего.
846934
#228 #846674
>>792725
Эх, щас бы в 2016 перебором задачу решать, вместо динамического программирования
#229 #846934
>>846526
Да, спасибо. Я пытался делать дфс, который брейкается, когда глубина рекурсии становится равна количеству вершин. Но как-то это получало ва5.
>>846535
Ты же понимаешь, что твои идеи на порядок сложнее и для осознания, и для написания. Топсорт - это одна строчка в дфсе
#230 #846939
Окей. Как быстро проверять достижимость каждой вершины из каждой по матрице достижимости? Вершин всего тысяча, но флойд не вариант, потому что там сверху еще будет логн от бинпоиска висеть. Граф плотный, поэтому бфс меня тоже смущает. Или нормально?
846963847025847601
#231 #846963
>>846939
В матрице достижимости все элементы должны быть равны 1.
846965
#232 #846965
>>846963
Действительно. Но это я, наверное, плохо выразился. Я еще подумаю, пожалуй
847052
#233 #847025
>>846939
Исходную то задачу расскажи.
847029
#235 #847052
>>847029
>>846965
Я, кажется, придумал, что хочу по матрице смежности быстро строить матрицу достижимости
847202
#236 #847202
>>847052
Подсказка, попробуй отсортировать ребра по весу.
847245
#237 #847245
>>847202
Пиздец я проебался, думал граф неориентированный, тогда это просто бинпоиск и SCC
#238 #847254
Нужны две функции. Одна принимает английский неправильный глагол, а возвращает его первую форму, а вторая получает рандомное слово и составляет кучу других слов из таких-же букв. Какие есть способы это сделать быстро?
#239 #847601
>>846939
BFS/DFS, компоненты связности. Предподсчёт за V^2, дальше ответ за 1.
#240 #856297
бумп
#241 #856298
>>792098 (OP)
Пререквизиты для Кормена и Кнутопаташика есть ли? Скожите пожалуйста.
861784
#242 #861728
Для Кормена только мозг нужен, ну там подумать иногда придётся. Кнутопаташника не читал.
#243 #861784
>>856298
У Кормена есть в конце книги поясняется за математику
#244 #861959
Парни, есть какой нибудь сайт, где перечислены основные олимпиадные алгоритмы? А то я знаю только викиалгоритмы, а он бесполезен для этого
861999862286
#245 #861999
>>861959
e-maxx
862023
#246 #862023
>>861999
огромнейшее спасибо
#248 #863521
Что, как поживаете? Я вот тут недавно школьную командную олимпиадку писал. Суть в том, что я-то алгоритмов довольно много знаю, могу написать. Префикс, з функции, декартачи, до, всякие графы, хэши. Но, сука, проблема в том, что в команде я ничего не придумывал. Мне говорили: "пиши топсорт, потом проверяй наличие соседних ребер". Или: "Склей строчки, посчитай префикс функцию, пока суффикс совпадает с префиксом, удаляй их. Я, бля, даже условия оригинального не знаю.
Это все круто, но на личной олимпиаде не проканает. Неумение быстро выдумывать решения - это приговор? Или еще есть шанс до феврали задрочить задачки из первой полутысячи тимуса?
864060
#249 #864053
Есть программа с кучей функций. У каждой функции есть название. Известно количество обращений к каждой функции за последнее время.
Надо назначить функциям однобуквенные хоткеи так, чтобы сумма чисел обращений к функциям, которым назначены хоткеи, была максимальна.
Хоткеем функции можно назначить только букву, входяшую в её название.
Знаю про венгерский алгоритм, но у меня вес дуги из функции в каждую из допустимых клавиш одинаков. Есть ли что-то быстрее для такого случая?
#250 #864060
>>863521
на то в команде всегда и есть два прогера, один комп, и один математик который придумывает решения, сечешь?
864257
#251 #864257
>>864060
Да. Но мне до студенческих командных нужно дописать личные олимпиадки, где один прогер и один математик в моем лице
#252 #864307
Вы меня удивляете.
Пишу на крестах и пухтоне.

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

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

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


держите матаноблядь!11
#254 #864557
>>864307

>адгоритмизацию


А что это за дисциплина?
864888
#255 #864888
>>864557
hellburnization is a part of CS
#256 #864889
>>864307
не все такие умные и не все так рано начинали, мне вот 30 лет и на тимусе у меня 50 задач, в школе был далек от программистов, даже не знал об этом, но как сейчас выяснилось тогда по матеше я обходил парней ныне уже участников финала мира acm icpc
#257 #864900
>>864307

>статистику


А что с ней не так?
Даже гуманитароблядки её усваивают.
864929
#259 #864983
>>864929
Для программирования пруфы нужны ужО Штоле?
864996
#260 #864996
>>864983
Спроси в machine learning треде.
865443
#261 #865189
Пишу алгоритм для игры. В ней нужно набрать максимум очков. Их количество не может уменьшаться. Есть фактор случайности. игра похожа на монополию и количество возможных исходов одного хода меньше чем у шахмат При этом игра может закончиться совсем неожиданно если неколько ходов подряд кубик будет плохо падать. Значит обычный minmax не подойдёт т.к. при большой глубине поиска лучший из худших всегда будет проигрыш. И что делать с линией горизонта? Ведь здесь нельзя форсировать поиск при шахе как в махматах. Реквестирую литературу про программирование ии для игр с влиянием рандома.
865292
#262 #865292
>>865189

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


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

>похожа на монополию


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

>Реквестирую литературу


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

> обход дерева ограниченной глубины, а по достижении дна считать оценку


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

>получить большую оценку, но это будет проигрыш и конец игры


Оценка не обязательно равна количеству очков. Это может быть и разность очков у тебя и противника, и сложная функция, учитывающая ещё и ситуацию на доске.
Никто не запрещает тебе назначать проигрышам оценку 0.
865385
#265 #865385
>>865348
Так может быть так что все ходы проигрышные. Надо что-то выбрать из тех нулей. Может их в 2 очереди проверять? А с горизонтом что делать? Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный. А алгоритм только на 5 вглубь смотрит и войдёт в проинрышную ветку из которой не выйти.
865446
#266 #865443
>>864996
Ну, так, ты мне какой-то теорию категорий с универсальной алгеброй тычешь. Статистика тут при чём?
865490
#267 #865446
>>865385

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


Если у всех стратегий одинаковая оценка, то выбираешь рандомно.

>А с горизонтом что делать?


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

>Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный.


В настолке с кубиком такое нереально. Там слишком много рандома. По этой же причине нет смысла делать сложный алгоритм - разница в уровне игры по сравнению с тривиальным "покупай всё что можешь" будет практически незаметна человеку.
#268 #865490
>>865443
Чего? На диаграмме показаны соотношения между распределениями случайных величин.
#269 #865492
>>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])
865498868659
#270 #865498
>>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])
868659
72 Кб, 590x278
#271 #867885
Хоть кто нибудь, хелп ми
867892868178875130
#272 #867892
>>867885
Мне это напомнило задачу с прошлогоднего полуфинала или даже финала. Копни в эту сторону Насколько я помню, там отчасти рандомизированный алгоритм. Сперва что-то поспрашивать, а потом решать.
867898
#273 #867898
>>867892
Хуя они охуели давать задачи с финала. Уточни, пожалуйста, что за финал?
867901
#274 #867901
>>867898
Прости, я тебе наврал. Мне почему-то вспомнилась задача J https://neerc.ifmo.ru/archive/2015/neerc-2015.pdf
Но это совсем из другой оперы
867903
#275 #867903
>>867901
Но ты все-равно подумай про рандомизированные алгоритмы
867907868178
#276 #867907
>>867903
http://rce.su/randomizirovannyj-protokol-svyazi-chast-1/
Вот это попробуй почитать.
А откуда задача?
867918
#277 #867918
>>867907
Хорошо, спасибо. На паре по дискретной математике задали.:(
#278 #868178
>>867903
>>867885
Вы че ебнулись? никак.
868312
#279 #868312
>>868178

> никак


А доказать?
#280 #868659
>>865492
>>865498
Руки бы тебе блять оторвать за такой код, хуесос
#281 #870866
С трудом даются задачи из Конкретной математики. Это нормально? Продолжать задрачивать или прочитать что-нибудь полегче сначала?
870911
#282 #870911
>>870866
А куда легче? Учебник за 5 класс?
871291
#283 #871291
>>870911
Да, спасибо, подходит
#284 #873630
анон, в какой порядке решать задачи на codeforces? самые популярные, новые, только A, B..., только div 2 или без разницы?
873631
#285 #873631
>>873630
Отсортируй по количеству решивших. Начинай решать. Если чуешь, что очень легко идет, листай на следующую страницу
873646
#286 #873646
>>873631
спасибо, так и сделаю
353 Кб, 1080x1920
#287 #875022
Ну че молчим, епта, давайте задачи решать
875163
#288 #875130
>>867885
Если ещё не поздно, вот тебе подсказка: почитай как устроен raid5.
875163
#289 #875163
>>875022
http://ideone.com/iTglQT

>>875130
Ты внимательно прочитал условие?
Особенно про то, что размеры строк r^2, а памяти - r, и что она неперезаписываемая?
875240875413
#290 #875240
>>875163
Да, задачка решается для строк размера r^2 , r бит неперзаписываемой памяти и r+1 запросе. Я думал, это очевидно.
875366
#291 #875307
Стандартная задачка егэ:
Из ряда натуральных чисел выбрать произвольное количество чисел так, чтобы их сумма не делилась на 6. При этом сумму надо максимизировать. На выход количество выбранных чисел и их сумму. Я не совсем ньюфаг в олимпиадном программировании, но тут встал в тупик. А егэ сдавать надо
875316875365
#292 #875316
>>875307
Динамическое программирование: f(i, c) = максимальная сумма подпоследовательности arr[:i], делящаяся на c.
875318
#293 #875318
>>875316
s/делящаяся на c/дающая c в остатке при делении на 6/
#294 #875365
>>875307
Как насчёт взять все, а потом при необходимости выбросить наименьшее, не делящееся на 6?
#295 #875366
>>875240
Ну не томи тогда, рассказывай.
875369
#296 #875369
>>875366
Я бы на твоём месте ещё подумал, задача-то простая. Но если совсем зашёл в тупик, то вот
http://lpaste.net/339079
875448
#297 #875413
>>875163

> http://ideone.com/iTglQT



Грови? Это что вообще, лол?)
Ввожу число, имя не выводит, переделывай
875423
#298 #875423
>>875413
Ввёл тебе за щёку.
#299 #875448
>>875369
Я понял задачу так, что обязательно использовать ровно r+1 запрос.
В таком случае возникает проблема, что на каком-то шаге мы можем обнаружить расхождение, но мы обязаны сделать остальные шаги, и непонятно как передать на эти шаги информацию о том, что различия уже найдены.
875451
#300 #875451
>>875448
Нет, ты неправильно понял задачу. Обычно такие странные условия обговариваются. Например, было бы написано "сделав ровно r+1 запрос"
875633
193 Кб, 1280x1707
#301 #875633
>>875451
Думаю ты прав, держи няшку.
#302 #875793
Может тут есть кто-нибудь, кто тоже участвует во всероссийской олимпиаде для 11 классов? Сейчас пробный тур проходит как раз.
И еще может кто-нибуд в технокубке участвовал? Какого уровня там задачи? Там вообще ебанутые какие-то правила с этими взломами, не знаю осилю ли я там хороший результат показать.
876086
#303 #876086
>>875793
Ну, участвовал в твоем технокубке. Из-за того, что не в том порядке стал решать задачи, занял не 70-какое-то, а 150 с хуем место. Не понравилось
147 Кб, 917x750
#304 #877609
Ебать, как такое делать? Пока что думаю запилить граф и перебирать по нему все варианты, но это же наверняка будет слишком медленно.
877675
#305 #877675
>>877609
Хули тут думать-то, жадный алгоритм же.
Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i.
877811879289
#306 #877722
>>792725
пиздец, деление и остаток от деления двумя операциями... Охуеть просто.
877805878123
#307 #877805
>>877722
Ну а что ты хотел, я тогда только начал вкатываться в си и программирование вообще
#308 #877811
>>877675

>среди работ с дедлайном >= i.


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

Мне кажется проще назначать день работе с наибольшим штрафом. Если есть свободные дни до дедлайна, то забираем последний. Иначе забираем последний из дней после дедлайна.
878128
#309 #877910
Какую теорию погуглить для олимпиадного программирования? Я просто совсем неадвно вкатился и пока что просто на логике всё делаю. Жадные алгоритмы, динамическое алгоритмы, что ещё?
877923
#310 #877923
>>877910
Способы представления графов в памяти, DFS/BFS, алгоритм Дейкстры, комбинаторика на уровне итерации по всем перестановкам и сочетаниям, бинарный поиск, алгоритм Эвклида, решето Эратосфена, генерация пифагоровых троек, метод ветвей и границ.
На самом деле сам поймёшь что нужно когда будешь натыкатьсся на трудные задачи.
878010
#311 #877991
Как научиьься реализовывать алгоритмы? Смотрю в интернете всякие видео уроки по популярным алгоритмам, типа quicksort, но реализовать на языке который изучаю не могу. Сто делать?
877999878003878012
#312 #877999
>>877991
Как научиьься выступать в суде защитником в деле об ебле козы бабы Нюры? Смотрю в интернете всякие видео уроки по выступлениям-заседаниям, типа quicksort, но выступить в суде в котором выступаю не могу. Сто делать?
#313 #878003
>>877991
Находишь в интернете реализацию ксорта на твоем языке. Понимаешь. Потом переписываешь, можно подглядывать. Как переписал, закрываешь. На следующий день без подглядывания пиши.
878045
#314 #878010
>>877923
Спасибо.
#315 #878012
>>877991
Задвай себе вопрос "а что надо делать" и делай. Потом "а что теперь?" и так далее. После каждого такого шага чекай всё ли правильно работает.
878045
#316 #878045
>>878003
>>878012
Спасибо, няши
#317 #878123
>>877722
а как можно лучше?
878128
#318 #878128
>>878123
divmod
>>877811
тысячи способов, пиши какой удобнее.
#319 #879289
>>877675

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


И какая у этого алгоритмическая сложность? По-моему, не меньше O(N^2). Многовато.
880775
#320 #880775
>>879289
Про кучу не слышал?
#321 #881288
Продублирую тут, пожалуй.

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

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

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

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

>не зная как распределены пользователи по группам


Как угодно, считай, это группы в вк.

>"приблизительно"


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

>"эксклюзивно"


Это я просто так назвал, не знаю как правильно. Смысл - в каждой секции должны быть группы, в которые входят только юзеры из этой секции, не пересекаясь с другими секциями.

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

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


Это строго обязательно? Это условие сильно усложняет задачу.
881663
#325 #881549
Сап. Я школьник, 10 класс. Алгоритмы знаю на уровне "quick sort, binary search, bfs, dfs, dijkstra". Такой вопрос - можно ли за год вкатиться в олимпиады так, чтобы получить хоть какие-то бонусы для поступления? И на что следует обратить внимание? Готов сидеть у книжек часами каждый день. Если что, пишу на плюсах.
881575881581886324
#326 #881574
>>792098 (OP)

>codeforces.com


>acm.timus.ru


>informatics.mccme.ru


>acmp.ru


>TopCoder.com


>etc


Скажите, а есть возможность на каком-нибудь из этих ресурсах сдавать задания на питоне?
881581
#327 #881575
>>881549
Думаю можно. Выясни какие олимпиады тебе подходят, посмотри задачи прошлых лет. Нарешивай подобные задачи и читай теорию.
#328 #881581
>>881574
Да

>>881549
Есть знакомые, которые из твоего положения и хуже брали себе потом диплом всероса, так что дрочи задачки. Посмотри на иоип, например
881616
#329 #881616
>>881581
А подскажи, пожалуйста, на каком из них конкретно можно, если знаешь.
881654881656
#330 #881654
>>881616
На топкодере вроде нельзя. Но вообще не надо писать олимпиады на питоне
Ты сам не можешь посмотреть?
881768882113
#331 #881656
>>881616
на всех, даже etc
#332 #881663
>>881535

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


Да.
#333 #881665
как самые популярные темы задач на codeforces? дп, жадные алгоритмы, графы, структуры данных...
что задрачивать, чтобы стать хотя бы синим?
881668
#334 #881668
>>881665
На синего хватит простых графов, бинпоиска, качественного конструктива. Сложные алгоритмы начинаются после Ddiv2
881671
#335 #881671
>>881668
спасибо
#336 #881768
>>881654

>Не надо писать на питоне


Почему?
882155
#337 #882111
>>792140

>(c for c in str(x))


Достаточно просто str(x)
882115
#338 #882113
>>881654
Спасибо
#339 #882115
это >>882111 сюда >>792567
#340 #882155
>>881768
Потому что рано или поздно ты столкнешься с тл. Мало где на олимпиадах гарантируют решабельность на питоне
#341 #882755
>>881518

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


> И т.д. Большие группы, типа мдк, где >1000чел, не входят в секции. Но их подписчики могут быть любителями хентая, гуро, golang.



Ну что же вы, бэтманы?
Я думал, в треде есть бородатые гики, что пояснят по хардкору, какой мне алгоритм нужен.
882783
#342 #882783
>>882755
Сколько групп всего?
Если не больше нескольких тысяч, то можно представить их в виде графа, в котором две вершины соединены если в соотв. группах нет общих членов. Перебираешь в нём клики Броном-Кербошем, и когда находишь подходящую удаляешь её из графа. В принципе может и не обязательно хранить граф в явном виде, в конце концов проверить наличие дуги между группами можно глянув на пользователей.

Но лучше делай как я уже написал >>881503

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


Можешь ещё отранжировать группы по аутичности, то есть отношению количества пользователей группы к количеству других групп в которых они состоят (или суммарному количеству пользователей в которых они состоят). Начинать наполнение секции лучше с аутистов.

Вангую что результаты тебя огорчат из-за того что есть боты, вступающие в дохуярд групп.
#343 #886324
>>881549
Я вот вообще не пробовал олимпиадное программирование раньше, но опыта в пограммировании каких-то практических вещей и всякой хуйни у меня куча. И вот в этом году я неплохо так начал в него вкатываться. 11-класс
#344 #887594
Кто-то сказал Данилюку, что это не кодфорс, чтобы решать с конца?
#345 #895409
Анончики, не нашел ваш тред на нулевой и поднимаю этот, вроде бы актуальный.
Интересует решение задания "743D - Хлоя и приятные подарки" на codefoces
Разбор здесь http://codeforces.com/blog/entry/49049 , но я в упор не понимаю, как его реализовать.
Кому не лень и кто шарит, можете разжевать идиоту.
895464895494
#346 #895464
>>895409
бамп посту
sage #347 #895491
Бампать последний пост, каеф
sage #348 #895494
>>895409

>я в упор не понимаю, как его реализовать


Там же решение на С++. Да и рекурсивное решение тупое как с перестановками:
Вывести все перестановки N чисел.
Перестановка N чисел - это перестановка первого числа и последовательности N-1. И так повторять пока N не будет равно 2, а два элемента переставить может даже школьник.
895517
#349 #895517
>>895494

>решение тупое


>Вывести все перестановки N чисел.


На минуточку N до 2*10^5.
Вот если ты вообще не в теме, но нахуя лезть в каждую бочку затычкой?
897955
6 Кб, 510x335
#350 #896982
896984
5 Кб, 453x287
#351 #896984
>>896982
фикс
897185
#352 #897185
>>792140
>>896984
ну рейт же, по-моему красиво.
897189929248
32 Кб, 813x415
#353 #897189
>>897185

>по-моему красиво

899874
#354 #897861
Как лучше себя прокачивать? Мотивации изучать что то новое совсем нету. На codeforces голубенький.
897930
sage #355 #897930
>>897861
Ну и все, нахуй тебе еще что-то? Или ты хочешь стать олимпипдником?
897953
#356 #897953
>>897930
Да, я же школьник
898015
sage #357 #897955
>>895517
На минуточку ты долбаеб, а первоначальная задача легко решается рекуррентно за n операций. Я же привел задачу намного сложнее, которая тоже легко решается похожим образом.
Толку в этих задачах все равно 0, а автора кода надо бить палкой по голове за такой код
905560
#358 #898015
>>897953
Тогда у тебя дохуя мотивации. От халявного поступления в вуз и повышенной стипухи, до чемпионата мира в пендосии. Открыл книгу и начал читать, нахуй
#359 #898360
анон, помоги решить задачу. https://puu.sh/sWIUR/cf666599d0.png
898775
#360 #898775
>>898360
ну тут сразу понятно что вершины надо не удалять, а добавлять в обратном порядке.
дальше очевидный флойд уоршел
получается 500^3, норм тебе?
только смотри не объебись - в двух внутренних циклах надо итерироваться по всем вершинам, а не только по добавленным.
899601
#361 #899601
>>898775

>получается 500^3, норм тебе?


>только смотри не объебись - в двух внутренних циклах надо итерироваться по всем вершинам, а не только по добавленным.


>>898775
Спасибо большое.
#362 #899874
>>897189

>Sleep(1000)


Проиграл. Нахуя?
#363 #903068
не умирай
903374
#364 #903374
>>903068
Какая сложность у алгоритма Евклида для нахождения gcd?
903487903505
#365 #903487
>>903374
O(\log \min(a,b))
903514
#366 #903505
903514
#367 #903514
>>903505
>>903487
Доказательство?
903655
#368 #903655
>>903514
Зуб даю.
903687
#369 #903687
>>903655
На что мне твой зуб?
#370 #903807
В чем секрет чуваков, которые на codeforces делают все задачи раунда за 2 ебаных часа? А?А?
903883903894904538
#371 #903883
>>903807
То есть секрет чуваков, которые делают это за час тебя не интересует?
#372 #903894
>>903807
Буду краток. знаешь, буквально на днях я был в Российской Академии
Наук, провёл беседу со многими учёными, в том числе молодыми, кстати,
очень грамотные ребята. Так вот мы обсудили, в частности и данную
проблему, поговорили о текущей экономической обстановке в стране; они
так же рассказали о своих планах на будущее.
Вкратце, ответ на твой вопрос такой: эти ребята довольно быстро решают задачи, что позволяет им придумать алгоритм и написать код для задач всего раунда всего за два часа.
#373 #904151

> Покажите, что алгоритм, который содержит не больше некоторого по-


> постоянного количества вызовов процедуры с полиномиальным временем


> работы, сам работает полиномиальное время. Если же алгоритм делает


> полиномиальное число вызовов такой процедуры, то общее время работы


> может быть экспоненциальным.



Посоны, откуда здесь экспоненциальное время выполнения?
#374 #904528
>>904151
Выглядит странно. Очевидно, что суперпозиция полиномов есть полином. Может, там процедура может сама себя дёргать или алгоритм?
#375 #904538
>>903807
Секрет в том, что родились с более подходящей для решения подобных задач генетикой
904546
#376 #904546
>>904538
У тебя мифологическое мышление
904548904909
#377 #904548
>>904546
ага, иди поспорь с нейробиологическими исследованиями.
904555904909
#378 #904555
>>904548
Уровня фантазий третьеклассника
904558904909
#379 #904558
>>904555
можешь жить своими маняфантазями дальше
904909
#380 #904909
>>904546
>>904548
>>904555
>>904558
Пиздец, вот вам спорить нехуй делать. Лучше бы над >>904151 подумали.
#381 #905503
>>904151
Задача из Кормена. Из раздела NP.
905524
#382 #905524
>>905503
У меня вот прямо щас лежит открытая в туалете глава про NP, но ничего наводящего на мысль не нахожу. Подскажешь конкретнее?
905527
#383 #905527
>>905524
NP полнота>>>Полиномиальное время>>>>Упражнения
905537
#384 #905537
>>905527
Спасибо. Только легче не стало.
Может я неправильно понимаю эту задачу? Ну подставили мы в x^10 значение x=n^20, получили n^200, экспонента никак не получается.
#385 #905560
>>897955
Тут шизофазия, смотрите
#386 #905579
#387 #906373
>>792098 (OP)
Бля у третьего дедка волосы как солнце хех
906450
#388 #906450
>>906373
Вообще-то там один дед, где ты увидел третьего?
907421
54 Кб, 1148x836
Ебался с этой хуйнёй полночи, в итоге только 6/11 тестов проходит :^( #389 #906492
Сам код (естественно, Паскаль):
http://rgho.st/6smPy2ygw
#390 #906504
>>906492
Задача Эйлера в классическом виде же?
#391 #906505
>>906492
Блджад, выложи на идеоне/гисте, чо как маленький.
906528
#393 #906532
>>906492
#3296 Поход (6-9)
Темы: [Динамическое программирование: два параметра]
Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2011, Задача D ]
#394 #906536
>>906528
>>906492
Граф нарисовал? Задача на алгоритм Дейкстры (а не задача Эйлера, проебался)
906581
#395 #906581
>>906536
Погуглил. Без подбора по всем возможным путям задачу возможно решить?
906612
#396 #906612
>>906581
Тут не нужны никакие графы и поиски кратчайших путей.
Это задача для 6ого класса. Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу. Код на богоподобной Яве по ссылке.
http://ideone.com/34HGKf
906628906661
#397 #906628
>>906612

>Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу


Частный случай поиска кратчайшего пути, вариант реализации с бинарным графом.
906643
#398 #906643
>>906628
Так то да, но тут время О(n) и памяти O(1), а у Дейкстры? Впрочем можешь не отвечать. Просто покажи реализацию, лучше всего на фибоначчевой куче, тебе явно это раз плюнуть, делов на 5 минут. А мне интересно.
906857
#399 #906661
>>906612

>Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу


Так мой код тоже самое и делает, нет? Конечно, там есть дохуя костылей, но всё же.
906673
#400 #906673
>>906661
Прости, но твой код написан так, что его даже читать не хочется. В нем нем ясной выраженной мысли. Зачем ты проверяешь следующий символ в строке? Зачем тебе переменная up? И где у тебя хранится минимум переправ до текущей точки (и правого и левого) берега реки?
906683
#401 #906683
>>906673

>Зачем ты проверяешь следующий символ в строке?


Для логичности, если сверху слева, конечно, но по картинке как будто сверху(т.е переменная up=1, а если снизу справа, ага, то соответственно up=0) идут два подряд (этот символ и следующий -- LL) притока, то выгоднее будет переправиться вниз, где таких притоков нет. Если сверху идёт лишь один приток, а второй снизу (LR), то выгоднее будет переправиться дальше вправо, чем переправиться вниз, а потом снова вверх.

>И где у тебя хранится минимум переправ до текущей точки (и правого и левого) берега реки?


Собственно, в переменной p, которая и выводится в конце. Правда, там по-другому описано, и нет отдельно левого и правого берега.

Я неофит просто, в этом году едва в регионалку по всеросу не попал.
906702
#402 #906702
>>906683
Кажется, нашел в твоем решении ошибку.
Проверь вход LLRB
906723
#403 #906723
>>906702
Действительно, у меня при притоках по всем сторонам (B) он поворачивает, хотя это совсем не обязательно.
Спасибо, спустя ещё несколько костылей будут все сто баллов, а так пока что 60.
906758
#404 #906758
>>906723
Анончик, не делай так. Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед. Посмотри выше решение готовое. И просто разберись почему оно работает. В нем мы идем, как будто по обеим сторонам реки одновременно.
906805
#405 #906805
>>906758

>Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед


Но почему? Извини, понять не могу.

>И просто разберись почему оно работает.


Хотелось бы всё же допилить своё решение, а если совсем не выйдет -- разобраться в чужих.
#406 #906857
>>906643
Ну не на пять минут, но мне тоже интересно. Мои соображения:
- в каждой точке графа у нас есть два возможных пути
- выбирая каждый раз пусть с меньшим весом, вы в итоге получим кратчайший (в волновом алгоритме всегда обсчитываем только одну ветку)
- переход протоки на стороне, где сейчас игрок, стоит 1
- переход на другую сторону учитывается вместе с переходом протоки на другой стороне (то есть результирующий вес на этом шаге либо 0, либо 2)
Память не нужна, сложность O(n).
#407 #906858
>>906857
Хотя да, заняло минут 7-10.
#408 #906859
>>906857
Тут есть маленький нюанс, но пусть спрашивающий сам догадается. Я могу дать подсказку.
#409 #906860
>>906857
опечатка: 1 либо 2*
#410 #906880
>>906857
Считать надо 2 шага, этот и следующий (как сумму), а при прочих равных выбирать правый берег.
#411 #906895
>>906857
Код покажи.
#412 #907421
>>906450
Я про третьего чувака, он дед.
907423
#413 #907423
>>907421
Сам ты dead, ёпта.
907427
#414 #907427
>>907423
Лул
#415 #907945
Сап, анончики, какой набор скиллов нужно выучить/повторить для предстоящей областной?
мимо-школьник
908019
#416 #907948
Хуй знает, где такое спрашивать, так что спрошу тут пожалуй, это лучше, чем ньюфаг-тред. Есть алгоритм Кнута-Морриса-Пратта. Можно ли им сделать поиск подстроки, если в заданной для поиска подстроке допустим символ, который бы допускал, что на его месте может быть любая другая подстрока?
908016
#417 #908016
>>907948
Задача о ноп?
#418 #908019
>>907945
Есть раздел на acmp.ru с областными олимпиадами, там можно задачки порешать.
908108
#419 #908037
Что почитать школьнику нужно больше примеров, чтобы научиться решать задачи на динамическое программирование? А как решать задачи на графы, про всякие j-е дороги между i-ми городами. Я учусь в 10 классе и недавно заинтересовался программированием, пытаюсь в задачи на Codeforces, но получается только А.
Может, уже поздно вкатываться, но хотелось бы уметь это для себя.
908049
#420 #908049
>>908037
Вкатываться не поздно, читай Шеня, Окулова и архивы олимпиад (mccme.ru и прочее, что есть в шапке)
#421 #908108
>>908019
Добра тебе
#422 #909245
Для всех, кто вкатывается в ОП на курсере очередной тысячный раз стартует курс по алгоритмам Седжвика.
https://www.coursera.org/learn/algorithms-part1
https://www.coursera.org/learn/java-data-structures-algorithms-2

Быстро проходишь оба курса.
Перестаешь быть зеленым на форсах.
914987
179 Кб, 1024x683
#423 #912094
913248
#424 #912857
Наконец то апнулся на форсах
913244
#425 #913244
>>912857
молоток, какой теперь? как к этому шел?
sage #426 #913248
>>912094
красавцы
913263
#427 #913263
>>913248
да они офигенные, это 2011 год в Орландо
208 Кб, 1280x960
#428 #913319
#429 #914987
915073915488
2362 Кб, 1920x1080
#430 #914992
ОЛИМПИАДНОЕ ПРОГРАММИРОВАНИЕ
#431 #915073
>>914987
Для форсов и ОП итмошный куср лучше, причем сильно лучше. Но у него выше уровень входа. В нем мало теории и много отличных задач.
#432 #915189
Объясните как ваша параша помогает вам в реальном программировании?
915192915399
#433 #915192
>>915189
Никак. Но те кто в 11 классе могут назадротить олимпиаду и пройти в топ вуз.
915206
#434 #915206
>>915192

> постсовок


> топ вуз


топ кек
#435 #915399
>>915189
Сайты верстать не поможет. Так что можешь не париться.
#436 #915488
>>914987
Как просмотреть материалы курса, если он кончился?
915654918735
#437 #915654
>>915488
Кстати, если не был зарегистрирован, то никак.
Есть список презентаций из учебных видео.
https://courses.edx.org/courses/course-v1:ITMOx+I2CPx+3T2016/bf78f3a948074b16ba7146b1be3b4850/

Список задач с разборами добрые люди дожны были выложить на гитхаб.
918735
99 Кб, 930x748
13 Кб, 871x257
69 Кб, 869x668
40 Кб, 837x420
#438 #915679
Помогите, я нихуя не понимаю. 1 пик условия, остальные объяснение.
на 3 пике:

>Сложим все пары (ki, li)длин таких блоков в массив.


Что это значит? То есть есть строка aabbbaaaaabbaa то в этот массив поместят(2,3) и (5,2)?
И дальше - почему надо найти такое чтобы это выполнялось?
915707915712
#439 #915707
>>915679

>Что это значит? То есть есть строка aabbbaaaaabbaa то в этот массив поместят(2,3) и (5,2)?


Сначала для пары (a,b) в массив поместят (2,5)(3,2).
Затем для пары (b,a) -> (3,2)(5,2)
915708915712
#440 #915708
>>915707
А не, ты прав (2,3)(5,2) и (3,5)(2,2)
915712
#441 #915712
>>915679
>>915707
>>915708
Как это работает:
Пусть у нас есть строка abbbaabbaaab, рассмотрим для начала только пару (a,b)
Тогда странностью такой строки будет количество не повторяющихся странных подстрок вида {a}{b}. Для abbb - это 3. Для aabb - 4, для aaab - 3. Но при этом мы несколько раз посчитали одни и теже подстроки.
Вопрос, как посчитать только различные варианты?
Для этого представим ось координат с абсциссой колво 'a' и ординатой колво 'b'. И расположем на этой плоскости прямоугольники с одним углом в начале координат и вторым в нашем случае (3,1)(2,2)(1,3) почитаем площадь фигуры. Это и будет ответ без повторений. Теперь повторим все для пары ('b','a').

У тебя на третьей пикче алгоритм нахождения такой площади.
915893
#442 #915893
>>915712
Дошло, спасибо.
#443 #915940
Как лучше считать хэш? По модулю 2^64 - 1 или 10^9 + 1?
Первый больше, но зато второй простой.
И как лучше хэшировать множество (то есть порядок не важен)?
917407
#444 #916483
Если имеются средние знания алгоритмов, на каком ресурсе советуете решать подряд задачи?
916547
#445 #916542
Ох ебать я набухался, чувствую себя быдлом, ааааа, мимо готовлюсь к области, ахахахаха
916568
#446 #916543
Пиздец
#447 #916547
>>916483
Решай на ацмп
#448 #916568
>>916542
какой на форсах, сколько на тимусе?
#449 #916610
Посоветуйте, как вкатиться в алгоритмы и структуры данных с нуля школьнику?
916859
726 Кб, 1200x3160
#450 #916859
917028
79 Кб, 450x338
#451 #916863
#452 #917028
>>916859
Так я не для олимпиад хочу вкатиться, а просто, чтобы перестать писать велосипеды
#453 #917407
>>915940
1) по модулю 2^32 - 1, это быстрее
2) любой ассоциативной операцией от хешэй элементов (я часто xor использую)
156 Кб, 880x878
Задача Timus 1003. Чётность #454 #917830
Полный текст задачи на пике. Если своими словами, то у нас есть неизвестная последовательность нулей и единиц. И запросы на четность единиц в подпоследовательности с L элемента до R элемента. Вопрос, начиная с какого запроса последовательности удовлетворяющей всем запросам не существует?

Как решить используя DSU?
918001
#455 #918001
>>917830
Попробуй сделать так:
1. сет с родителем 0 для чётных, а с 1 для нечётных.
2. Все цифры тогда придётся увеличивать на 1, т.е. вместо единицы будем использовать 2 и т.д. (так как 0 и 1 заняты)
3. unionSet будем использовать только тогда, когда findSet(x) != 0 && findSet(x) != 1
4. Прочитал 1 3 odd, вызываешь unionSet (1, 2), (1, 3), (1, 3), второй аргумент увеличен на 1, см. пункт 2.
5. Делаешь проверку. Суммируешь findSet от 2, 3, 4(увеличены на 1, input у нас 1, 2, 3)
5. Сумму проверяешь на чётность
918522
55 Кб, 894x455
#456 #918522
>>918001
Пункт 4. Не ясен. Почему для четного отрезка все внутренние точки добавляются в нечетное множество?

Вот на пикче есть объяснение с форсов, но я его тоже не понимаю.

Т.е. вот есть запрос l r odd. Это значит, что либо (1,l-1)=odd и (1,r)=odd либо (1,l-1)=even и (1,r)=even. Но что с этим делать не ясно.
928351
22 Кб, 509x296
#457 #918735
>>915654
>>915488
можно зарегистрироваться и решать в любое время
#458 #920972
Олимпиудники, как вы в файлы ввод/вывод перенаправляете?
#459 #923255
Парни, объясните тупому, что такое взлом задачи во время контеста на cf?
923411
#460 #923411
>>923255
взлом решения мб?
кто-то посмотрел твой код, который прошёл претесты, увидел что он выдаст неправильный ответ на какие-то допустимые входные и типа запустил твоё решение на этих входных
923464
#461 #923464
>>923411

>запустил


ясно, а как можно посмотреть код до окончания контеста?
923568
#462 #923568
>>923464
На главной странице контеста нажимаем замок напротив решенной задачи.
Переходим в раздел "комната", дабл-кликом по кол-ву очков открываем решение для просмотра.
Находим ошибку
Жмем кнопку взломать, пишем тест(грузим генератор)
????
профит
923822
#463 #923822
>>923568
спасибо
#464 #925150
Как CTF начать тащить?
#465 #926582
v
#466 #926797
Поясните за вот эту задачу
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, когда мы решаем линейное диофантово уравнение?
927851
#467 #927755
Блджад. Участовал в контесте на форсах (1400 мусор), решил только А и В. Остальные три были пиздец какой-то. В тренировках такая же хуйня, дальше В никогда не уходил. Причем я не понимаю - вроде основные алгоритмы знаю (да если меня разбудят в 4 утра и насильно посадят за комп, на изи напишу бинпоиск, сортировку за O(n*log(n)), бфс, беллмана-форда, дфс, дейкстру, поиск порядковой статистики, каркас минимальной длины итд). Задачи на динамику тоже решал, получается с шансом 40%, хардово спалить закономерность. Когда читаю разборы последних трех задач, охуеваю - как люди додумываются до ЭТИХ решений. Как вообще люди на олимпиадах побеждают? Я уже с этим тимусом проебался до 100 решенных задач, ацмп решал, читал Шеня.
Короче, как вообще люди умудряются искать правильное решение в задачах, где хуй поймешь, какой алгоритм нужен? Тупо нарешивать овердохуя с архивов? И всё?
#468 #927764
>>927755
Большинство олимпиадников -- олимпиадники по математике тоже (хотя есть исключения), это сильно прокачивает смекалочку, то есть умение понять, как же найти ключ к этой задаче.
927794
#469 #927794
>>927764
Никогда не увлекался олимпами по матану. Значит, нужно забить болт на форсы, ибо без скиллов с математических олимпиад никак не апнуться?
927823
#470 #927823
>>927794
Нет, не обязательно. Просто они прокачивают скилл, которого тебе не хватает.
Попробуй решать много-много простых задач -- на бинпоиск, поиск в глубину и простенькую динамику (в первых трёх задача на этом вашем КФ только это и нужно). Меньшикова на информатикс, региональные этапы, задачки по темам разным.
#471 #927851
>>926797
бамп
927853
#472 #927853
>>927851
Мда, ты что, не быдлокодер?
Написал на питоне, получил ОК и нормас.
927866
#473 #927866
>>927853

> писать олимпиады на питоне


как там на 1400 птс?))0
927881
#474 #927872
>>927755

> Я уже с этим тимусом проебался до 100 решенных задач


Очень мало. Это сколько в сумме ты потратил на решение - 50 часов? Хз почему ты не побеждаешь на олимпиадах, когда целых 50 часов потратил. В доте-то, наверное, 1050 часов.
927879
#475 #927879
>>927872
100500 часов в дотке и все равно в брозе, потому что тима не тянет =)
#476 #927881
>>927866
Ну так если длинная арифметика нужна.
#477 #927976
>>927755
Лол, что за хуйня, если меня ночью разбудить, я нихуя не напишу. Мимо-2000-на-кф
928351
#478 #928062
>>927755

> напишу бинпоиск


До слёз с этого знатока.
#479 #928351
>>927976
Первый див, помоги с >>918522 раз все равно мимо проходил. Пожалуйста.
#480 #928407
>>927755
Нужен опыт именно в олимпиадных задачах, со временем начинаешь узнавать неочевидные использования того или иного алгоритма и решаешь.

В школе ходил на олимпиады по математике, там та же хуйня была, если видел несколько сотен задачек то почти всегда сразу знаешь куда копать.
#481 #929003
Каким образом можно надрочиться за 2 года, чтобы стать победителем на олимпиаде 1 уровня? Знания по математике хуевые, с программированием еще хуже, даже сортировку не могу написать.
929196932575
#482 #929196
>>929003
informatics.mccme.ru
Сидишь и решаешь. Вместо Доты. Тебе должно быть настолько же интересно.
Как прокачаешься, пишешь так же кодфорсы сможешь писать.
#483 #929218
Помогите решить задачу про 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).
Что вообще там может не работать?
#484 #929248
>>897185
За вложенные циклы принято по рукам бить
929255
#485 #929255
>>929248
Как там круды поживают?
#486 #932575
>>929003
Pizda треду
#487 #932655
Как восстановить ответ в задаче о рюкзаке, используя O(N+L) памяти? (N предметов, L вместимость рюкзака)
Знаю аналогичный алгоритм в задаче о расстоянии Ливенштейна, но он какой-то сложный (хотя задача вроде проще).
932762933506
#488 #932762
>>932655
Проиграл со сложного алгоритма о расстоянии Левенштейна.

https://www.cs.colostate.edu/~cs575dl/Sp2015/Lectures/Knapsack.pdf
#489 #933506
>>932655
Забавно, ты назвал Алгоритм Левештейна сложным, хотя это просто разделяй и властвуй. Обычно когда какой-нибудь алгоритм не до конца разбираешь, считаешь его сложным, хотя на самом деле ты просто не понял его идею.
Если бы ты понял как работает Левенштейн, ты бы сразу понял как можно сделать то же самое для рюкзака.
http://ideone.com/abUEBD
934730
#490 #934730
>>933506
Алё.
Линейное количество памяти + восстановление ответа.
934821
#491 #934821
>>934730
Проиграл с петушка, который не умеет по коду определить сложность по памяти.
934825
#492 #934825
>>934821
Технически можно приебаться к копированию items при делении пополам - будет N*log(N) памяти, но так более читаемо. Понятно, что можно не копировать, а хранить [l, r]
#493 #951187
Не тони.
Не поздно ли вкатываться? #494 #956844
В школе прогал с удовольствием и довольно много, но бессистемно и навыков, кроме непосредственного написания кода, не развил. Потому что долбоеб.
Как итог, в 11 классе в олимпиадки не смог, пришлось идти на физику. Сейчас учусь в приличном вузе мфти, но направление скорее связано с математикой и физикой, буду менять.
Так вот, летом у меня будет около двух свободных месяцев на то, что бы достичь в своем развитии в плане проганья хотя бы уровня хорошего школьного олимпиадника, с какого бока за это лучше взяться? Я так понимаю, сначала нужно освоить алгоритмы, был даже сайт где список из 80 штук, этого хватит для начала? Как распределить время между теорией и практикой?
Есть ли где-то видео-курсы? Так-то я могу ботать по 8 часов, но нужна программа, координация, что бы кто-то вел, по книжкам это тяжело. Ангельский intermediate, речь понимаю, но трачу на это слишком много сил, на постоянный просмотр меня не хватит.
956872957744958606
#495 #956872
>>956844
Вебмакак сейчас очень много, поэтому лучше вкатываться в низкоуровневое программирование и embedded.
956893956895
#496 #956893
>>956872
Алло тут тред олимпиадного программирования, я про него и спрашиваю
956896
#497 #956895
>>956872
Embedded-макак сейчас очень много, поэтому лучше вкатываться в высокоуровневое программирование и веб.
#498 #956896
>>956893

>олимпиадное программирование после школы


Зачем?
Вкатиться в алгоритмы и структуры данных необходимо, но олимпиады не нужны.
956911
#499 #956911
>>956896
Нравится формат, короткие вызовы на несколько часов. Хочется научиться быстрее решать задачи.
Если получится, по вузику можно будет ходить как на понтах, с замдекана за руку здороваться
#500 #956917
Котятки, напоминаю что открыта регистрация в код джем.
#501 #957744
>>956844
1) Одному тяжело будет, тренер нужен. Если ты в мфти, с этим 100% проблем не будет.
2) Решай текущие контесты на codeforces + архив на codeforces, там есть разборы задач и можно смотреть чужие решения.
Но вообще, ты какой-то аутист. Олимпиады нужны, чтобы поступить в вуз, а если ты уже поступил, то они нахуй не всрались. В вузе надо либо заниматься наукой (если дохуя умный), либо на работу устраиваться как можно быстрее, чтоб по окончанию вуза уже было много опыта.
958018
#502 #958018
>>957744
1. Искать тренера пока рано, как мне кажется. Никто не будет нянчить дауна без базовых алгоритмических знаний, разве что за большие деньги. Собственно, вопрос был про структурированный курс конкретно по спортивным алгоритмам, что бы направляли и объясняли фишки. В свое время начинал просто решать задачи, но сложилось впечатление что это довольно малоэффективный процесс.

Так со стороны для себя вижу несколько выгод:
1) Идея пачками макачить игрушки для айос на модных фреймворках, пусть даже за большие деньги, меня не очень прельщает.
А вот идея написания высокоэффективного кода кажется гораздо интереснее, поэтому спортивное программирование кажется мне актуальнее для себя, чем тот же технотрек.
2) Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании, поэтому получить этот навык будет так или иначе полезно. При этом лучше сейчас, чем чеез 6 лет, когда придется начинать работать и гнаться за рынком. Тем более, что учить прикладные технологии сейчас не имеет смысла.
959229
#503 #958606
>>956844

>был даже сайт где список из 80 штук


Это который?
#504 #959229
>>958018

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


Блять, что значит нянчить? Ты просто ходишь на тренировки, где ты один или с командой таких же ньюфагов решаешь задачи, а потом идет разбор этих задач. После разбора можешь дорешивать задачи и задавать всякие вопросы. Фишка в том, что если ты решаешь один и не понимаешь, почему у тебя задача не принимается, ты можешь очень долго думать и в итоге все равно не додуматься. Намного лучше у кого-нибудь спросить.

> Идея макачить меня не прельщает.


Ты понимаешь, что все, что не наука - это макакинг? Да, есть более высококвалифицированные макаки. Вот я немного шарю в алгоритмах и математике, но макакой я от этого быть не перестаю, потому что я не могу создать что-то новое, чего не было до меня. Я могу хуйнуть нейросеть и распознавать изображения, но не я же придумал алгоритм backpropagation, это будет просто реализация чужой идеи. Ничуть не лучше, чем сайты на пхп хуярить. Если не хочешь заниматься макакингом - поступай в магистратуру, потом в аспиранутру и т д. Если ты тупой как я и не можешь в науку, лучше сразу задумайся о будущей работе и начинай дрочить все разделы cs, а не только алгоритмы. Прочитай все книги Таненбаума.

> Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании


На большинстве вакансий не спрашивают динамическое программирование, теорию чисел, геометрию, графы и прочую хуету. Из алгоритмов спрашивают что-нибудь "на смекалочку" (типа найти подмассив с максимальной суммой за O(n)) + то, что реально полезно знать в работе: деревья (красно-черные, b-tree и т д), хэши, сортировки и т д. На олимпиадах ты никогда не будешь писать красно-черное дерево / свою сортировку / свою хэш-таблицу.
962769
#505 #961013
Анон, помоги. Что-то не получается решить элементарнейшую задачу на тимусе (сложность 81) http://acm.timus.ru/problem.aspx?space=1&num=1106.
Мой код:
http://acm.timus.ru/forum/thread.aspx?id=36064&upd=636260865438522774
Моё решение заключается в том, чтобы с помощью BFS покрасить все вершины и записать в ответ те, которые имеют одинаковый цвет
#506 #961751
Аноны, есть какие-нибудь методы по решению таких задач, как эта: http://acm.timus.ru/problem.aspx?space=1&num=1502 ?
Я проебал на ней два часа, вывел какую-то ебанутую формулу, которая почему-то работает и получил AC. Вопрос - есть какие-нибудь статьи/книги, где рассказывается, как решать похожие задачи с нахождением формул?
962679962759962772
#507 #962194
Накидайте плз задач на cf или тимусе на префикс- или z-функцию.
962676
#509 #962679
>>961751
Ты че, поехавший?

#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;
}
962772
#511 #962769
>>959229

>то, что реально полезно знать в работе


> (красно-черные, b-tree и т д), хэши, сортировки


Прости, братишка, но по работе скорее всего это не пригодится. Пригодится умение распаковать протобуф, запаковать, написать конфиг, итд. Никогда тебе на работе не придётся задуматься о чём-нибудь реально сложном. Лично я таких работ не встречал.
9 Кб, 886x212
#512 #962772
>>961751
Во-первых,
http://www.wolframalpha.com/input/?i=sum+(sum+(i+++j),+j+=+i+to+n),+i+=+0+to+n
Во-вторых, если ты это делаешь на контесте, когда время ограничено и ты не можешь пользоваться вольфрамом, ты можешь упростить эту сумму, чтобы она считалась за O(n) вместо O(n^2), но не искать конечную формулу (пикрелейтед).
В-третьих, при желании можно продолжить выводить и вывести конечную формулу тупо в лоб, просто нужно терпение и внимательность.
В-четвертых, этот анон >>962679 правильно заметил, решение в лоб проходит, потому что у тебя здесь примерно 5 на 10^7 раз выполняется ans += l + r, а это очень простая операция. Такая простая операция за секунду может успеть выполниться даже 10^9 раз. В среднем за секунду успевает выполниться около 10^8 операций (если это не какие-то сложные операции с дробными числами).
#513 #962900
>>792098 (OP)
Спрошу тут, ибо хуй знает, где еще спрашивать.
Есть массив множеств перестановок A = [a_1, ... a_n]. n Относительно мало, для S_5 (группы перестановок порядка 5) всего 27, для S_6 94.
Нужно для каждой пары (a_i, a_j) \in A проверить, совпадают ли у них подруппы, натянутые на данные множества перестановок.
То есть: пусть a_i = {tau_1, .. tau_m}, a_j = {delta_1, .. delta_m}. Узнать, равны ли <tau_1, .. tau_m> и <delta_1, .. delta_m>.
Можно ли это сделать за вменяемое время? Как вообще натянуть подгруппу на перестановки в комплуктере?
Посоны, если кто-нибудь знает подходящую книжку, или пакет в каком-нибудь эре или петухоне, либо хоть что-нибудь способное помочь, напишите, пожалуйста.
963087
#514 #963087
>>962900

>Спрошу тут, ибо хуй знает, где еще спрашивать.


Маттред в /sci/, dxdy, math.stackexchange.com
Но для начала сформулируй вопрос понятней.
963216
#515 #963216
>>963087

>Но для начала сформулируй вопрос понятней.


Пусть так.
Есть два множества перестановок A = {tau_1, ... tau_m} и B = {delta_1, ... delta_m}.
Узнать, равны ли подгруппы <A> и <B>.
963217
#516 #963217
>>963216
A, B подмножества группы перестановок S_n.
3047 Кб, 3264x1836
#517 #965964
Вот эта хуйня не дает мне покоя, как блять это сука работает?
966444
#518 #966444
33 Кб, 699x416
#519 #970065
памагити
970469
#520 #970469
>>970065
Ты че, ебан? Суфмассив + lcp
970481980789
#521 #970481
>>970469
Ещё суффдерево можно + дфс, но раз ты такое спрашиваешь, вряд ли ты его напишешь с первого раза.
980789
#522 #972129
Можно ли на КФ как-то смотреть тесты, если соревнование уже прошло?
972158
#523 #972158
>>972129
Нет. Если не получается, скидывай сюда, кто-нибудь решит.
972160
#524 #972160
>>972158
Да там классическая задача, я просто баг в реализации не мог найти (уже нашёл).
972166
#525 #972166
>>972160
Лол, вот это я тебя обманул. Извини, плохая память. Так это, после сабмита тебе должно выдать все входы и выходы (если ты не в олимпиадном режиме решаешь)
#526 #980789
>>970469
>>970481
С этого момента поподробнее.
981174
#527 #980790
Как найти совершенное паросочетание минимального веса в двудольном графе?
Между долями есть всё рёбра, если это важно (наверно нет, потому что можно надобавлять ребёр с весом ∞).
http://informatics.mccme.ru/mod/statements/view.php?id=6555#1 - вот эта задача, короче
980814
#529 #981085
>>980814
Спасибо.
#531 #982275
А как делать неасимптотические оптимизации?
Я вот не знаю, разве что очевидные вещи типа:
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) {...};
(в теле цикла, понятно, эти переменные не трогают)
982368982585982598
#532 #982368
>>982275
for (int i = 0, to = m n; i < to; ++i) ...
Вместо new Node использовать deque.push_back() && return &deque.back()
Но обычно этим не заморачиваются и делают такие тест кейсы, чтобы твой перебор не влез даже с байтоебскими оптимизациями (ну это в нормальных контекстах)
983087983300
#533 #982585
>>982275

> Он тут не будет скорее всего умножать m на n много раз, а сделает типа


> int mn = m n;


Да. Эта оптимизация называется hoisting.
#534 #982598
>>982275
В идеале надо читать книги по архитектуре компьютеров и по компиляторам, но на контестах почти всегда можно обойтись без этих знаний. Иногда выстреливает, у меня было несколько примеров.

Например, была задача про дерево с N = 400000. Я подумал, что N какое-то большое и зачем авторы так сделали. Понял, что стэк может переполниться и сделал обход дерева не через рекурсию, а помещая номера вершин в очередь.

В другой раз я решал какую-то задачу через linked list и там были запросы, в результате которых могла создаться новая нода в листе, а могла и не создаться. Запросов там было 100000, но задача не прошла. До сих пор не уверен в чем дело, но видимо в том, что динамическое выделение памяти занимает много времени. Вот если бы компилятор видел, что я подряд в цикле выделяю, он бы соптимизировал и сразу выделил сколько нужно, а там были запросы. Потом я понял, что затупил, и что можно заменить linked list на deque, и задача прошла, потому что deque устроена как массив, который при необходимости увеличивается во сколько-то раз (в 2, кажется), соответственно, делается всего log N запросов на выделение нового участка памяти.

Еще была ситуация, что я решил писать код через лямбды, а компилятор какую-то лямбду скомпилировал во что-то хуевое, задача не проходила. Заменил на императивный вариант и прошла. С тех пор на контестах я все пишу в императивном стиле.
982673982693
#535 #982673
>>982598

>linked list


>Запросов там было 100000, но задача не прошла. До сих пор не уверен в чем дело


Может имел место произвольный доступ к элементам списка?
982798
#536 #982693
>>982598

>компилятор какую-то лямбду скомпилировал во что-то хуевое


Вообще пушка.
Ты сам смотрел на ассемблерный код, или просто так ляпнул что-то от балды? Я думаю, что ты просто не знаешь С++ и пишешь чушь.
982798
#537 #982798
>>982693

> Ты сам смотрел на ассемблерный код


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

>>982673
Нет, там только в начале и в конце добавлялись элементы.
982843
#538 #982843
>>982798

>если я и так знаю


Короче не слушайте этого шизика, он где-то как-то обжёгся на лямбдах (небось не отличает [=] от [&]), а обосновать или привести примеры не может.

Чтобы не стать такими как он всегда докапывайтесь до истины, если видите, что что-то не работает, а не "ща тут cout вставим чтобы глючить перестало"
#539 #983087
>>982368

> &deque.back()


Такие ссылки не инвалидируются при новых пушбэках? Или как-то можно указать, чтобы дэк на основе связного списка генерировался? Но тогда какая это оптимизация, если всё равно при каждом добавлении системный вызов.
983332
#540 #983300
>>982368
Ну не скажи. Разница между O(n) и O(n log n) весьма призрачная, и оптимизированный логарифм может работать быстрее, чем линейное решение, особенно если у него константа пожирнее.
Изредка даже O(n^2) вместо O(n) может зайти, если тесты слабые, либо такое решение, что для него тест непросто придумать, особенно заранее, не зная решение.
Конечно, чаще проще решить по честному, но сдать задачу, не решая, тоже весело.
#541 #983332
>>983087
Ты вообще представляешь что такое deque в С++? Как он внутри устроен? Почитай cppreference прежде чем такие вопросы задавать.
#542 #984536
Эй, отвечающие в тред, расскажите, когда и как вы начинали упарывать олимпиадки, какой лвл, где учились/учитесь/работаете. Что читали с самого начала, на какие курсы ходили?
984956
#543 #984956
>>984536
Ходил на курсы в академю ШАГ, но там скучно был и я вместо занятий ходил к твоей мамке заниматься любовью.
Обновить тред
Двач.hk не отвечает.
Вы видите копию треда, сохраненную 23 мая 2017 года.

Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее

Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
« /pr/В начало тредаВеб-версияНастройки
/a//b//mu//s//vg/Все доски