Этого треда уже нет.
Это копия, сохраненная 23 мая 2017 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Это копия, сохраненная 23 мая 2017 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
58 Кб, 640x427
Настало время перекатить и такой тред.
Основные ресурсы с задачками:
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)
Шапка за пять минут, надеюсь треду жить, принимаются предложения по оформлению
Основные ресурсы с задачками:
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)
Шапка за пять минут, надеюсь треду жить, принимаются предложения по оформлению
>>792098 (OP)
Решать на тимусе задачи по сложности от самых легких до сложных?
Решать на тимусе задачи по сложности от самых легких до сложных?
Все знают, что такое счастливый билетик.
Например:
123456
Сумма первых трех 5, сумма последующих 15. Билет несчастливый.
111003
Сумма первых трех чисел 3. Сумма последующих чисел 3. Билет счастливый.
Задача, посчитать сколько счастливых билетов между 100000 и 999999.
Выиграет самый красивый код.
Например:
123456
Сумма первых трех 5, сумма последующих 15. Билет несчастливый.
111003
Сумма первых трех чисел 3. Сумма последующих чисел 3. Билет счастливый.
Задача, посчитать сколько счастливых билетов между 100000 и 999999.
Выиграет самый красивый код.
print(50412)
Шах и мат
Шах и мат
>>792282
знатное говноедство, даже я уважаю
знатное говноедство, даже я уважаю
>>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
[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
Ответы792956
>>792098 (OP)
вроде отослал один, а он сыпится. нихуя не понимаю, где фак? ввод бинарный чтоль?
>codeforces.com
вроде отослал один, а он сыпится. нихуя не понимаю, где фак? ввод бинарный чтоль?
Ответы792739
Ответы792745
>>792739
да вижу тут есть запускалка, потыкался, я так понял он в sdin пихает, а не в стартовые ключи - как я думал. хотя вроде логично, ведъ программа после ввода должна умереть?
да вижу тут есть запускалка, потыкался, я так понял он в sdin пихает, а не в стартовые ключи - как я думал. хотя вроде логично, ведъ программа после ввода должна умереть?
Ответы792818
вот ещё момент не вкурил: есть ли гарантия что 1 read вернёт мне весь ввод или нужно ещё дрочить всё ли ввелось? видимо да чёт приуныл
>>792098 (OP)
А смысл какой их решать?
А смысл какой их решать?
>>792745
В стартовые ключи это как. Там есть задачи с мегабайтами инпута, ключами не обойдёшься.
Твоя задача вывести правильный output и вернуть EXIT_SUCCESS.
>>792801
Для интереса, это в основном хобби. Есть побочные профиты типа "в яндексе любят олимпиадников". Для школьников также помогает попасть на всякие бюджеты, ещё проводятся соревнования с неплохими призами, но это надо сильно угореть по теме.
В стартовые ключи это как. Там есть задачи с мегабайтами инпута, ключами не обойдёшься.
Твоя задача вывести правильный output и вернуть EXIT_SUCCESS.
>>792801
Для интереса, это в основном хобби. Есть побочные профиты типа "в яндексе любят олимпиадников". Для школьников также помогает попасть на всякие бюджеты, ещё проводятся соревнования с неплохими призами, но это надо сильно угореть по теме.
>>792801
я вот просто хочу подрочить байтики. на время - не интересно.
я вот просто хочу подрочить байтики. на время - не интересно.
>>792818
ну наверно тоже верно, но можно было файлами заделать - а то ведь скорость будет сильно зависеть от того как реализован инпут в языке - а оно очень разнородно.
>Там есть задачи с мегабайтами инпута, ключами не обойдёшься.
ну наверно тоже верно, но можно было файлами заделать - а то ведь скорость будет сильно зависеть от того как реализован инпут в языке - а оно очень разнородно.
Ответы792879
>>792818
Таки да, если не дрочиться по 2-3 5-часовый тренировки в неделю чтобы стать чемпионом мира.
Школьнику однозначно имеет смысл угореть, я сам жалею, что не хватало мотивации/не всегда мог себя заставить ботать в школьном возрасте, победителя всероса а не призера взял бы с легкостью. Все равно это лучше чем проебывать время на каэску какую-нибудь.
Поступление в любой топовый универ халявное, опять же.
Студентам активно задрачивать смысла нет, если не целиться на финал АСМ. Но таки полезные эффекты в виде "быстро решать задачки на собеседовании в Yandex/Google" возникают.
Ну еще, если не совсем донный, да и универ не совсем парашный, можно нахаляву за счет универа то есть ездить по всяким соревнованиям как и в пределах рашки, так и заграницу.
>хобби
Таки да, если не дрочиться по 2-3 5-часовый тренировки в неделю чтобы стать чемпионом мира.
Школьнику однозначно имеет смысл угореть, я сам жалею, что не хватало мотивации/не всегда мог себя заставить ботать в школьном возрасте, победителя всероса а не призера взял бы с легкостью. Все равно это лучше чем проебывать время на каэску какую-нибудь.
Поступление в любой топовый универ халявное, опять же.
Студентам активно задрачивать смысла нет, если не целиться на финал АСМ. Но таки полезные эффекты в виде "быстро решать задачки на собеседовании в Yandex/Google" возникают.
Ну еще, если не совсем донный, да и универ не совсем парашный, можно нахаляву за счет универа то есть ездить по всяким соревнованиям как и в пределах рашки, так и заграницу.
Ответы792879
>>792838
Раньше делали с файлами, но постепенно от этой практики отказались, может быть чтобы полностью избавиться от еботни с правами доступа. Кроме того, тебе же удобнее, сколько WA было получено на неверном названии файла… Причём в некоторых случаях это оказывалось решающим фактором.
>>792866
СЪЕЗДИЛ НАХАЛЯВУ
@
В ПЕТРОЗАДРОТСК
Раньше делали с файлами, но постепенно от этой практики отказались, может быть чтобы полностью избавиться от еботни с правами доступа. Кроме того, тебе же удобнее, сколько WA было получено на неверном названии файла… Причём в некоторых случаях это оказывалось решающим фактором.
>>792866
СЪЕЗДИЛ НАХАЛЯВУ
@
В ПЕТРОЗАДРОТСК
>>792879
Ну да, это само собой. А еще Москву, Париж, Будапешт, Белград и Катовице (Польша). И везде билеты + проживание - за счет универа
Ну да, это само собой. А еще Москву, Париж, Будапешт, Белград и Катовице (Польша). И везде билеты + проживание - за счет универа
Ответы792969
>>792879
А сейчас люди получают WA на том, что ОЙ А ТУТ ФАЙЛЫ НУЖНЫ. Или ОЙ Я ФАЙЛЫ НЕ ЗАКОММЕНТИЛ (хотя нормальные пацаны юзают препроцессор для этого).
Хотя без файлов таки удобнее, да, жаль, что не везде так сейчас
А сейчас люди получают WA на том, что ОЙ А ТУТ ФАЙЛЫ НУЖНЫ. Или ОЙ Я ФАЙЛЫ НЕ ЗАКОММЕНТИЛ (хотя нормальные пацаны юзают препроцессор для этого).
Хотя без файлов таки удобнее, да, жаль, что не везде так сейчас
Ответы792952
Добавьте в шапку http://dl.gsu.by/
Сайт крут тем что там дохуй задач и он показывает количество пройденых тестов. Даже на сами тесты можно посмотреть.
Сайт крут тем что там дохуй задач и он показывает количество пройденых тестов. Даже на сами тесты можно посмотреть.
>>792922
но вооще, где-нибудь в лине можно было бы перехватывать пару функций в libc и на любое имя файла давать один путь. наверняка и в винде такое можно провернуть.
но вооще, где-нибудь в лине можно было бы перехватывать пару функций в libc и на любое имя файла давать один путь. наверняка и в винде такое можно провернуть.
Самый опущенный тип айтишников это олимпиадники.
Ответы792968
>>792969
Да, МФТИшные сборы, они самые. Сам из Питера, поэтому четверть пишу у себя
Да, МФТИшные сборы, они самые. Сам из Питера, поэтому четверть пишу у себя
сап, вопрос такой
вот на соревах стоят ограничения по памяти
но
в jvm языках же сама jvm автоматом отжирает до пизды памяти
получается jvm-блядки априори сразу сосут?
вот на соревах стоят ограничения по памяти
но
в jvm языках же сама jvm автоматом отжирает до пизды памяти
получается jvm-блядки априори сразу сосут?
Ответы793033
>>793026
Да. Алсо, ты ещё забыл про инициализацию машины, тоже время отжирает. Выбор языка в любом случае за тобой + ситуации, когда задача решается на С и не решается джавой, крайне редки.
Да. Алсо, ты ещё забыл про инициализацию машины, тоже время отжирает. Выбор языка в любом случае за тобой + ситуации, когда задача решается на С и не решается джавой, крайне редки.
Ответы793042
олсо я совсем зеленый не понимаю пока как вкатиться
видел советуют книгу Шеня, она ок?
видел советуют книгу Шеня, она ок?
Ответы793047
>>793033
Это в случае, если ТЛ для Джавы стоит раза в 2 больше, что некоторые Online Judges делают по дефолту. А вообще зависит еще и от автора. Если он напишет какое-то заоптимизированное решение на плюсах и поставит жесткие ТЛи чтобы отсечь другое решение с чуть большей асимптотикой, то Джавакодеры соснут
Это в случае, если ТЛ для Джавы стоит раза в 2 больше, что некоторые Online Judges делают по дефолту. А вообще зависит еще и от автора. Если он напишет какое-то заоптимизированное решение на плюсах и поставит жесткие ТЛи чтобы отсечь другое решение с чуть большей асимптотикой, то Джавакодеры соснут
Ответы793047
>>793038
Иди сразу на кодфорсы, читай параллельно емакс, дорешивай задачи и читай разборы. Для начала сойдёт, когда дело дойдёт до уровня суфавтоматов, уже сам разберёшься, что делать.
>>793042
СОКОБАН)))0)
Иди сразу на кодфорсы, читай параллельно емакс, дорешивай задачи и читай разборы. Для начала сойдёт, когда дело дойдёт до уровня суфавтоматов, уже сам разберёшься, что делать.
>>793042
СОКОБАН)))0)
Ответы793056
Зачем нужно олимпиадное программирование, если все держится на библиотеках и фреймворках? Оно же абсолютно не нужно в реальном мире. Лучше потратить время не на подготовку и дрочку алгоритмов, а на прикладную разработку и на свой гитхаб.
>>792098 (OP)
В спортзал и к стилистам всех четверых. Футболки блядь на халка, пошить соразмерные. Крайнему слева в жопе похудеть, перестать жрать говно, перейти на салатики и мясо. Бородачу как минимум выровнять бороду.
В спортзал и к стилистам всех четверых. Футболки блядь на халка, пошить соразмерные. Крайнему слева в жопе похудеть, перестать жрать говно, перейти на салатики и мясо. Бородачу как минимум выровнять бороду.
Ответы793060
>>793047
друг, где читать разборы? я заходил на рашен кап чето там, но там объяснение мне показалось уже для чуваков которые прорешали пару десятков контестов
друг, где читать разборы? я заходил на рашен кап чето там, но там объяснение мне показалось уже для чуваков которые прорешали пару десятков контестов
Ответы793060
>>793056
На кодфорсах почти к каждому контесту пилят разбор авторы. Кроме этого, не стесняйся в случае чего спрашивать в комментах: пост вынесет на первое место в секции комменты, его увидят и ответят с вероятностью 99%.
>>793052
Радикально. В многих областях алгоритмы необходимы, пусть и не всем разработчикам.
>>793053
Котёнка лучше не трогать, где ещё такое встретишь, при том что он относительно молод.
На кодфорсах почти к каждому контесту пилят разбор авторы. Кроме этого, не стесняйся в случае чего спрашивать в комментах: пост вынесет на первое место в секции комменты, его увидят и ответят с вероятностью 99%.
>>793052
>абсолютно
Радикально. В многих областях алгоритмы необходимы, пусть и не всем разработчикам.
>>793053
Котёнка лучше не трогать, где ещё такое встретишь, при том что он относительно молод.
>>793052
Писали же кучу раз
Школьникам есть однозначные профиты которые не очень сложно получить, да и олимпиадки на таком уровне таки сильно влияют на прогерские навыки
Студентам - хобби, помощь на собеседованиях.
Да и полезно таки некоторые алгоритмы писать самому, чтобы понять как работает что-то. Опять же, навыки писать оптимальный код на плюсах
Писали же кучу раз
Школьникам есть однозначные профиты которые не очень сложно получить, да и олимпиадки на таком уровне таки сильно влияют на прогерские навыки
Студентам - хобби, помощь на собеседованиях.
Да и полезно таки некоторые алгоритмы писать самому, чтобы понять как работает что-то. Опять же, навыки писать оптимальный код на плюсах
>>793060
Я не говорю про алгоритмы, они то очень нужны, я говорю про олимпиадную дрочку, которая вырабатывает плохой стиль кода (попробуй попиши читаемый код на время) и бесполезна в реальном мире.
Я не говорю про алгоритмы, они то очень нужны, я говорю про олимпиадную дрочку, которая вырабатывает плохой стиль кода (попробуй попиши читаемый код на время) и бесполезна в реальном мире.
Ответы793073
>>793065
А, ну в этом плане может быть.
Могу поспорить по следующим пунктам:
1. В целом развитие понимания, как всё работает, неасимптотическая оптимизация как, например, std::ios::sync_with_stdio
2. Навык дебага сложных конструкций.
3. Умение писать код быстро и правильно, то есть держать в голове много деталей
Отдельно скажу, что после многих лет олимпиад в проектах всё пишу максимально красиво, по другому уже и не хочется, но тут уже у всех своё. По крайней мере можно сказать, что само понимание красивого кода приходит после взаимодействия, а лучше написания некрасивого.
А, ну в этом плане может быть.
Могу поспорить по следующим пунктам:
1. В целом развитие понимания, как всё работает, неасимптотическая оптимизация как, например, std::ios::sync_with_stdio
2. Навык дебага сложных конструкций.
3. Умение писать код быстро и правильно, то есть держать в голове много деталей
Отдельно скажу, что после многих лет олимпиад в проектах всё пишу максимально красиво, по другому уже и не хочется, но тут уже у всех своё. По крайней мере можно сказать, что само понимание красивого кода приходит после взаимодействия, а лучше написания некрасивого.
Ответы793082
>>793073
Хуевый пример, если честно. В реальной жизни хрен понадобится
>как, например, std::ios::sync_with_stdio
Хуевый пример, если честно. В реальной жизни хрен понадобится
Ответы793210
>>793082
Хуёвый, но про плюсы тут особо ничего и не расскажешь. Хотя в целом вопрос I/O в C/C++ довольно занятный.
Вот про питон можно долго говорить, там абсолютно неочевидные вещи происходят.
Хуёвый, но про плюсы тут особо ничего и не расскажешь. Хотя в целом вопрос I/O в C/C++ довольно занятный.
Вот про питон можно долго говорить, там абсолютно неочевидные вещи происходят.
>>793658
Че ты врешь?
Че ты врешь?
>>793658
Ну ты же наверняка понимаешь почему так, или есть хотя бы предположения.
Просто не нравится?
Вполне вероятно, что ты просто мало промышленно кодил, тогда это нормально. В олимпиадках ты ж тоже не сразу начал норм участвовать наприер
Ну ты же наверняка понимаешь почему так, или есть хотя бы предположения.
Просто не нравится?
Вполне вероятно, что ты просто мало промышленно кодил, тогда это нормально. В олимпиадках ты ж тоже не сразу начал норм участвовать наприер
>>792098 (OP)
первая же задачка - мой пердак в небесах, ответ на неё - подлетаю к юпитеру. это просто пиздец какой-то.
>Конкретная математика
первая же задачка - мой пердак в небесах, ответ на неё - подлетаю к юпитеру. это просто пиздец какой-то.
Ответы796208
Не смог решить вторую по сложности с начала задачу на тимусе.
Задавайте свои ответы
Задавайте свои ответы
>>795402
Блять, ты тролль или ты серьезно?
Пиздец просто, >на пушбэк поп
Техника имени Семена, блять. Это как про любую задачу сказать "это задача на инт мейн", поеботень полная
>>795406
Тебе надо знать, что такое массивы, как считывать-выводить вещественные числа, и как извлекать корень.
Первое - это лучше погугли и почитай в нормальном месте туториалы по языку, если таких основ не знаешь
Второе - считывать так:
double a;
scanf("%lf", &a);
и писать
printf("%f", a)
На самом деле, это верно для 11+ стандартов, в старых стандартах и читать и выводить с помощью %lf вроде
Третье это
#include <math.h>
...
a = sqrt(23.9);
Блять, ты тролль или ты серьезно?
Пиздец просто, >на пушбэк поп
Техника имени Семена, блять. Это как про любую задачу сказать "это задача на инт мейн", поеботень полная
>>795406
Тебе надо знать, что такое массивы, как считывать-выводить вещественные числа, и как извлекать корень.
Первое - это лучше погугли и почитай в нормальном месте туториалы по языку, если таких основ не знаешь
Второе - считывать так:
double a;
scanf("%lf", &a);
и писать
printf("%f", a)
На самом деле, это верно для 11+ стандартов, в старых стандартах и читать и выводить с помощью %lf вроде
Третье это
#include <math.h>
...
a = sqrt(23.9);
Ответы796271
>>795372
Я максимум решал 1010+ сложности на тимусе. Я успешнее
Я максимум решал 1010+ сложности на тимусе. Я успешнее
>>796352
Что такое бинарное дерево?
Я не понимаю зачем обсираться в присядку, одновременно обмазываясь говном и дрочить на коколимпидаки и нахуй не нужные алгоритмы
Что такое бинарное дерево?
Я не понимаю зачем обсираться в присядку, одновременно обмазываясь говном и дрочить на коколимпидаки и нахуй не нужные алгоритмы
Ответы796832
>>796398
На пике.
>>796427
Из 9 в 2 можно идти пом пути 9 4 2 1 2.
Не эффективно. Должен быть способ быстрее.
>Что такое бинарное дерево?
На пике.
>>796427
>единственный маршрут
Из 9 в 2 можно идти пом пути 9 4 2 1 2.
>Находишь всех предков обоих вершин.
Не эффективно. Должен быть способ быстрее.
Ответы796833
2 Кб, 580x338
>>796832
пик забыл
пик забыл
>>796903
А нет его в памяти. Даже размер не известен. но в long long влазит. Выглядит как на той картинке. Наверно просто максимальный надо делить на 2 пока они не сравняются.
А нет его в памяти. Даже размер не известен. но в long long влазит. Выглядит как на той картинке. Наверно просто максимальный надо делить на 2 пока они не сравняются.
>>796914
Числа между которыми маршрут прокладывать. Вывести нужно сам маршрут.
Числа между которыми маршрут прокладывать. Вывести нужно сам маршрут.
>>796352
1. В любом дереве маршрут всегда единственный, иначе бы там были циклы.
2. Задача сводится к нахождению наименьшего общего предка двух вершин, которую можно решить например алгоритмом Тарьяна.
1. В любом дереве маршрут всегда единственный, иначе бы там были циклы.
2. Задача сводится к нахождению наименьшего общего предка двух вершин, которую можно решить например алгоритмом Тарьяна.
Ответы797534
>>796208
То, что все лошади одной масти, можно доказать индукцией
по числу лошадей в определенном табуне. Вот так:
„Если существует только одна лошадь, то она своей масти,
так что база индукции тривиальна. Для индуктивного пере-
перехода предположим, что существует п лошадей (с номерами от
1 до п). По индуктивному предположению лошади с номера-
номерами от 1 до п — 1 одинаковой масти, и, аналогично, лошади с
номерами от 2 до п имеют одинаковую масть. Но лошади по-
посредине с номерами от 2 до п — 1 не могут изменять масть в
зависимости от того, как они сгруппированы,—это лошади, а
не хамелеоны. Поэтому в силу транзитивности лошади с номе-
номерами от 1 до п также должны быть одинаковой масти. Таким
образом, все п лошадей одинаковой масти. чтД*
Есть ли ошибка в приведенном рассуждении и какая имен-
именно?
>>795392
просто это математика, мне сложно, нужно по другому мыслить, немного перестроить голову.
То, что все лошади одной масти, можно доказать индукцией
по числу лошадей в определенном табуне. Вот так:
„Если существует только одна лошадь, то она своей масти,
так что база индукции тривиальна. Для индуктивного пере-
перехода предположим, что существует п лошадей (с номерами от
1 до п). По индуктивному предположению лошади с номера-
номерами от 1 до п — 1 одинаковой масти, и, аналогично, лошади с
номерами от 2 до п имеют одинаковую масть. Но лошади по-
посредине с номерами от 2 до п — 1 не могут изменять масть в
зависимости от того, как они сгруппированы,—это лошади, а
не хамелеоны. Поэтому в силу транзитивности лошади с номе-
номерами от 1 до п также должны быть одинаковой масти. Таким
образом, все п лошадей одинаковой масти. чтД*
Есть ли ошибка в приведенном рассуждении и какая имен-
именно?
>>795392
просто это математика, мне сложно, нужно по другому мыслить, немного перестроить голову.
Ответы797533
>>797322
Это же очевидно, неверная база индукции. Самый первый переход для n=2 не работает, базой должен быть именно этот случай, что невозможно.
Это же очевидно, неверная база индукции. Самый первый переход для n=2 не работает, базой должен быть именно этот случай, что невозможно.
>>796935
Тарьян offline, лучше всё-таки на sparse table делать.
Тарьян offline, лучше всё-таки на sparse table делать.
Сап, посоны, пишу алгоритм Дейкстры. Что я делаю не так? Должно выводить 24 3 15, а выводит 24 32 20. Нумерация вершин с единицы.
https://ideone.com/eGhmMK
https://ideone.com/eGhmMK
Ответы797964
>>797948
Граф ориентированный или нет? У тебя в коде он ориентированный, а в задаче как? Видимо, в ней он неориентированный, тогда надо делать
adj_list[begin].push_back (make_pair(end, weigth));
adj_list[end].push_back (make_pair(begin, weigth));
У тебя нет второй строчки
Граф ориентированный или нет? У тебя в коде он ориентированный, а в задаче как? Видимо, в ней он неориентированный, тогда надо делать
adj_list[begin].push_back (make_pair(end, weigth));
adj_list[end].push_back (make_pair(begin, weigth));
У тебя нет второй строчки
Ответы797969
>>797964
Неориентированный, и еще допустимы мультирёбра, но в тестовых данных для примера мультирёбер нет. Какие изменения в алгоритме надо сделать, чтобы обрабатывать мультиграфы?
Неориентированный, и еще допустимы мультирёбра, но в тестовых данных для примера мультирёбер нет. Какие изменения в алгоритме надо сделать, чтобы обрабатывать мультиграфы?
Ответы797975
>>797975
Да, этот фикс помог. Матрица неорграфа симметричная, и списки тоже делаются симметрично.
Говорят, что мультиграф надо немного иначе обрабатывать.
Да, этот фикс помог. Матрица неорграфа симметричная, и списки тоже делаются симметрично.
Говорят, что мультиграф надо немного иначе обрабатывать.
Ответы797981
>>797980
Нет, не надо. Лишние ребра тебе ничего плохого не делают: ты все равно в итоге выберешь из всех мультиребер ребро с наименьшим весом. В принципе, если их совсем много, то можно когда строишь граф, просто среди всех ребер, соединяющих одинаковые пары вершин, оставить только ребро с минимальным весом, но алгоритм будет работать корректно и без этого
Нет, не надо. Лишние ребра тебе ничего плохого не делают: ты все равно в итоге выберешь из всех мультиребер ребро с наименьшим весом. В принципе, если их совсем много, то можно когда строишь граф, просто среди всех ребер, соединяющих одинаковые пары вершин, оставить только ребро с минимальным весом, но алгоритм будет работать корректно и без этого
Ответы797982
>>797981
Блин, тогда я даже не знаю, почему программа проходит все тесты, кроме двух.
https://ideone.com/pJfxfM
Блин, тогда я даже не знаю, почему программа проходит все тесты, кроме двух.
https://ideone.com/pJfxfM
Ответы797984
>>797982
А, скорее всего, я вывожу INF там, где по условию надо выводить -1. Сейчас проверю, должно помочь.
И все-таки странно, что авторы обращают внимание на то, что могут попадаться мультиграфы.
А, скорее всего, я вывожу INF там, где по условию надо выводить -1. Сейчас проверю, должно помочь.
И все-таки странно, что авторы обращают внимание на то, что могут попадаться мультиграфы.
Ответы798007
>>797984
Ну например это может быть важно в случае, если человек юзает матрицу смежности вместо списка смежности хотя тогда бы по TL бы не прошло скорее всего. И, как правило, в задачах по умолчанию граф простой, поэтому выделение того, что есть кратные ребра, является некоторым правилом хорошего тона, можно сказать.
Ну например это может быть важно в случае, если человек юзает матрицу смежности вместо списка смежности хотя тогда бы по TL бы не прошло скорее всего. И, как правило, в задачах по умолчанию граф простой, поэтому выделение того, что есть кратные ребра, является некоторым правилом хорошего тона, можно сказать.
Посоны, смотрите.
На двумерной плоскости имеем набор многоугольников с float координатами. Как определить, находится ли точка внутри какого-либо многоугольника?
На двумерной плоскости имеем набор многоугольников с float координатами. Как определить, находится ли точка внутри какого-либо многоугольника?
13 Кб, 798x535
>>798379
Отклеилось.
Отклеилось.
14 Кб, 798x535
>>798398
Да, вспоминаю про трассировку луча. Но тогда ведь нужно проверять каждую грань каждого многоугольника?
Хотя можно применить небольшую оптимизацию и проверять только те многоугольники, с проекциями которых есть пересечения. Или еще лучше, с проекциями сторон которых есть пересечения.
В общем, спасибо, навел на мысли.
Да, вспоминаю про трассировку луча. Но тогда ведь нужно проверять каждую грань каждого многоугольника?
Хотя можно применить небольшую оптимизацию и проверять только те многоугольники, с проекциями которых есть пересечения. Или еще лучше, с проекциями сторон которых есть пересечения.
В общем, спасибо, навел на мысли.
Ответы798441
14 Кб, 798x535
>>798438
Точнее мы тут можем даже до одного сократить.
Точнее мы тут можем даже до одного сократить.
>>798379
Если они выпуклые, то для каждого многоугольника можно делать проверку за log(число вершин)
Если они выпуклые, то для каждого многоугольника можно делать проверку за log(число вершин)
Если задачу на кодфорсе взломали, то это хорошо т.к. она бы завалилась на основных тестах, а так есть возможность узнать об ошибке и доделать её?
>>800440
Именно так, если ты ее не заблокировал, конечно
Именно так, если ты ее не заблокировал, конечно
Чо, обидно, со второй задачей вышло?)))
>>798398
Проще, но на этот способ любят делать контртесты. Надёжнее пускать в рандомном направлении.
>>798379
Я всегда использовал сумму полярных углов. Тема такая, для каждой грани ты считаешь, под каким ориентированным углом она видна из точки. Дальше считаешь сумму, если получилось 0, то ты снаружи, если 360 градусов – внутри. Случай на грани рассматривается отдельно.
>>800440
Бывает, что ломают решения, которые не валятся на тестах.
>>800574
Разбор появляется от сразу до нескольких дней, пали комменты к посту о контесте, там обычно спрашивают такие вещи.
Проще, но на этот способ любят делать контртесты. Надёжнее пускать в рандомном направлении.
>>798379
Я всегда использовал сумму полярных углов. Тема такая, для каждой грани ты считаешь, под каким ориентированным углом она видна из точки. Дальше считаешь сумму, если получилось 0, то ты снаружи, если 360 градусов – внутри. Случай на грани рассматривается отдельно.
>>800440
Бывает, что ломают решения, которые не валятся на тестах.
>>800574
Разбор появляется от сразу до нескольких дней, пали комменты к посту о контесте, там обычно спрашивают такие вещи.
Ответы803666
>>797533
мне сложно, а вот если есть задача - я могу её решить, как там написано, и так же индукцией доказать - не проблема. но когда меня спрашивают, например докажите что в задаче на столбы, используются все возможные комбинации - вообще не ебу как. да, для меня очевидно, что вот число и его бит может иметь 3 значения, тогда число с n бит имеет 3^n-1 возможных комбинации - даже не представляю как это доказывают.
мне сложно, а вот если есть задача - я могу её решить, как там написано, и так же индукцией доказать - не проблема. но когда меня спрашивают, например докажите что в задаче на столбы, используются все возможные комбинации - вообще не ебу как. да, для меня очевидно, что вот число и его бит может иметь 3 значения, тогда число с n бит имеет 3^n-1 возможных комбинации - даже не представляю как это доказывают.
Ответы801184
>>800960
потому что это из усложненной задачи 2. но я не проверял в ответах заебало чувствовать себя говном
потому что ноль не учитываем - там задача сформулирована так, вродъ.
как? замкнутая форму уже есть, я её вывел из рекуррентной, опять же, из прошлой задачи. дальше то что?
класть на меньший.)
> Почему 3, а не 2?
потому что это из усложненной задачи 2. но я не проверял в ответах заебало чувствовать себя говном
> Откуда -1?
потому что ноль не учитываем - там задача сформулирована так, вродъ.
> А ты попробуй индукцией
как? замкнутая форму уже есть, я её вывел из рекуррентной, опять же, из прошлой задачи. дальше то что?
> 2 Найдите кратчайшую последовательность перекладываний, перемещающих башню из n дисков с левого колышка А на правый колышек В, если прямой обмен дисками между А и В запрещен. (Каждое перекладывание должно производиться через средний колышек. Как обычно, больший диск нельзя
класть на меньший.)
> 3 Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения нам встретятся все допустимые варианты размещения n дисков на трех колышках.
Ответы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 <- это
или что под этим ещё понимается?
>как? замкнутая форму уже есть, я её вывел из рекуррентной, опять же, из прошлой задачи. дальше то что?
в смысле, я человек тупой, не математик, и не имею этот склад ума, я так понял, что индукция способ доказать что замкнутая форма формулы верна - путём поставления её в рекуррентную.
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
Т.е слева -_-
>>800954
Ничего не понял, кинь условие задачи, или что ты там доказываешь.
Ничего не понял, кинь условие задачи, или что ты там доказываешь.
>>792098 (OP)
Этой книги достаточно, чтобы понимать анализ алгоритмов, всякие асимптоты и прочее из следующей книжки? Или придется до кучи ещё математики наверстать? Мой уровень если что на уровне девятиклассника, лол.
>Грэхэм, Кнут, Паташник "Конкретная математика"
Этой книги достаточно, чтобы понимать анализ алгоритмов, всякие асимптоты и прочее из следующей книжки? Или придется до кучи ещё математики наверстать? Мой уровень если что на уровне девятиклассника, лол.
>>801308
Угу. А асимптотика там обсуждается аж в последней главе.
Как я и думал, все эти алгоритмы и интеллектуальные игры с ними для элиты, которую с рождения обучают не тому, что дают в обычной быдло-школе. Пойду дальше в дотку катать.
Угу. А асимптотика там обсуждается аж в последней главе.
Как я и думал, все эти алгоритмы и интеллектуальные игры с ними для элиты, которую с рождения обучают не тому, что дают в обычной быдло-школе. Пойду дальше в дотку катать.
Ответы801396
>>801315
Просто начни с книжек попроще. "программирование: теоремы и задачи" Шеня, а потом вот это http://codeforces.com/blog/entry/12314
Ну и перед этим учебник школьный по математике, если совсем неуч.
Просто начни с книжек попроще. "программирование: теоремы и задачи" Шеня, а потом вот это http://codeforces.com/blog/entry/12314
Ну и перед этим учебник школьный по математике, если совсем неуч.
Ответы801628
>>801396
Спасибо. Я настолько тупой, закончил школу, а не могу решить задачи с acmp.ru которые сложнее 30% по их шкале.
Спасибо. Я настолько тупой, закончил школу, а не могу решить задачи с acmp.ru которые сложнее 30% по их шкале.
Зарегался на этом вашем кодефорсес. Где там выбирать задачи по уровню сложности и тематике?
Алсо, есть там что-нибудь по преобразованию Фурье?
Алсо, есть там что-нибудь по преобразованию Фурье?
>>800887
Ну вот. Ты меня запутал. Чётно обфусцирую решение на следующем контесте, а нечётно нет.
>Бывает, что ломают решения, которые не валятся на тестах.
Ну вот. Ты меня запутал. Чётно обфусцирую решение на следующем контесте, а нечётно нет.
Ответы803822
Ответы804385
>>803666
После множества таких казусов с недавних пор все успешные похеки добавляются в набор финальных тестов.
После множества таких казусов с недавних пор все успешные похеки добавляются в набор финальных тестов.
>>803678
круто, жаль что я не видел этого в школьном возрасте
круто, жаль что я не видел этого в школьном возрасте
Есть ли простой алгоритм быстро возвести матрицу в квадрат?
Вот две произвольные матрицы либо за эн в кубе умножать, либо хитрый алгоритм. А тут может попроще?
Вот две произвольные матрицы либо за эн в кубе умножать, либо хитрый алгоритм. А тут может попроще?
Ответы805622
>>805600
Нет, нельзя, насколько я знаю. Есть только, как ты сказал, хитрые алгоритмы, либо частные случаи типа метода четырёх русских.
Нет, нельзя, насколько я знаю. Есть только, как ты сказал, хитрые алгоритмы, либо частные случаи типа метода четырёх русских.
Ответы805626
>>805626
Я понимаю, вот и говорю, что я, по крайней мере, никогда о таком частном случае ничего особенного не слышал. Пиши Штрассена или гугли научные статьи на эту тему.
Я понимаю, вот и говорю, что я, по крайней мере, никогда о таком частном случае ничего особенного не слышал. Пиши Штрассена или гугли научные статьи на эту тему.
Ответы805635
>>805626
>>805633
Впрочем, можешь ничего не гуглить, вот ответ на твой вопрос http://math.stackexchange.com/questions/20873/whats-the-fastest-way-to-take-powers-of-a-square-matrix
>>805633
Впрочем, можешь ничего не гуглить, вот ответ на твой вопрос http://math.stackexchange.com/questions/20873/whats-the-fastest-way-to-take-powers-of-a-square-matrix
бумп
>>792098 (OP)
Рассказываю, почему я бросил олимпиадное программирование. Когда я начинал, то думал, что там задачи чисто на смекалку, для решения которых не требуется никаких предварительных знаний. Но это оказалось не так. Есть определенное количество узкоспециализированных тем, например, динамическое программирование или древовидные структуры данных, в которых надо быть хорошо прошаренным, чтобы решать олимпиадные задачи. Если кто не понял, что я сказал, приведу такой пример: если вы попытаетесь доказать хотя бы теорему Пифагора, ничего о геометрии не зная вообще, то у вас ничего не выйдет. Так вот я задумался однажды, стоит ли задрачиваться в темах, которые котируются на олимпиадном программировании, если они мне скорее всего не пригодятся в работе. Лучше уж потрачу это время на изучение чего-нибудь более практичного.
Рассказываю, почему я бросил олимпиадное программирование. Когда я начинал, то думал, что там задачи чисто на смекалку, для решения которых не требуется никаких предварительных знаний. Но это оказалось не так. Есть определенное количество узкоспециализированных тем, например, динамическое программирование или древовидные структуры данных, в которых надо быть хорошо прошаренным, чтобы решать олимпиадные задачи. Если кто не понял, что я сказал, приведу такой пример: если вы попытаетесь доказать хотя бы теорему Пифагора, ничего о геометрии не зная вообще, то у вас ничего не выйдет. Так вот я задумался однажды, стоит ли задрачиваться в темах, которые котируются на олимпиадном программировании, если они мне скорее всего не пригодятся в работе. Лучше уж потрачу это время на изучение чего-нибудь более практичного.
>>810507
Я бы не бросал, если бы было много свободного времени, но его нет.
Я бы не бросал, если бы было много свободного времени, но его нет.
>>810133
Ты прав, в принципе, если не считать, что в некоторых местах типа яндекса и вк олимпиадников очень любят. Да и в целом на базовом уровне почти везде спрашивают, но базовый CS и так все должны знать просто по роду профессии.
Ты прав, в принципе, если не считать, что в некоторых местах типа яндекса и вк олимпиадников очень любят. Да и в целом на базовом уровне почти везде спрашивают, но базовый CS и так все должны знать просто по роду профессии.
Ответы812714
>>810715
Тут замкнутый круг.
В "базовый CS" входит комбинаторика, теория чисел, графы, динамическое программирование. Это активно используется на олимпиадах и во всяких гуглах. Но никак не изучается глубоко в вузах (кроме парфеновской кафедры и еще схожих) и не применяется в рф-it. Кроме сам знаешь где. Тоесть олимпиадное программирование, или тот же Скиена, это единственный способ рф-студенту окунуться в то "а что же там пишут в гуглах, что у нас нет". Да и без олимпиадной подготовки ты будешь о-о-чень долго вникать во всякие crack the coding interview и elements of programming interview.
Тут замкнутый круг.
В "базовый CS" входит комбинаторика, теория чисел, графы, динамическое программирование. Это активно используется на олимпиадах и во всяких гуглах. Но никак не изучается глубоко в вузах (кроме парфеновской кафедры и еще схожих) и не применяется в рф-it. Кроме сам знаешь где. Тоесть олимпиадное программирование, или тот же Скиена, это единственный способ рф-студенту окунуться в то "а что же там пишут в гуглах, что у нас нет". Да и без олимпиадной подготовки ты будешь о-о-чень долго вникать во всякие crack the coding interview и elements of programming interview.
Аноны, подскажите алгоритм: дано произвольное количество 2d-вершин, нужно из них сделать многоугольник с непересекающимися гранями.
11 Кб, 652x512
9 Кб, 652x514
>>813017
Вроде это не совсем то. Все точки должны быть задействованы.
Я написал примитивный алгоритм: проходим по точкам, отсортированным убывающе по y, и соединяем ближайшие по x, но иногда он фейлится.
Вроде это не совсем то. Все точки должны быть задействованы.
Я написал примитивный алгоритм: проходим по точкам, отсортированным убывающе по y, и соединяем ближайшие по x, но иногда он фейлится.
Ответы813134
>>813104
Берёшь самую нижнюю-правую точку, ставишь её как начало координат. Считаешь полярные координаты остальных точек относительно центра. Сортируешь по углу, обходишь в этом порядке.
Дядя Сэджвик с Курсэры так учил
Берёшь самую нижнюю-правую точку, ставишь её как начало координат. Считаешь полярные координаты остальных точек относительно центра. Сортируешь по углу, обходишь в этом порядке.
Дядя Сэджвик с Курсэры так учил
Ответы813163
>>813134
Я походу проще вариант нашел: пространство делится на 2 части по x (можно взять тупо width/2), слева и справа строятся ломаные кривые и потом соединяются.
Я походу проще вариант нашел: пространство делится на 2 части по x (можно взять тупо width/2), слева и справа строятся ломаные кривые и потом соединяются.
>>813163
Хотя тупо width/2 будет ошибкой, нужно чтобы хотя бы 2 точки было на одной из сторон.
Хотя тупо width/2 будет ошибкой, нужно чтобы хотя бы 2 точки было на одной из сторон.
Ответы813183
156 Кб, 650x445
>>813245
матрас из денег всё справит
матрас из денег всё справит
20 Кб, 651x514
>>813255
Все нормас, быстрейшее из всех, O(n).
Проблема была только в разделении. Надо делить линией, которая проходит через самую верхнюю грань и через самую нижнюю. Теперь все без ошибок.
Все нормас, быстрейшее из всех, O(n).
Проблема была только в разделении. Надо делить линией, которая проходит через самую верхнюю грань и через самую нижнюю. Теперь все без ошибок.
>>813300
Я думал о корректности.
Из любого набора разных точек можно сделать ломанную линию с непересекающимися кусками, соединяя точки одна за другой в одном направлении. Пересечений гарантированно не будет, если между точками в этом направлении нет других точек.
Мы получаем две ломанных линии, не пересекающиеся между собой. Вопрос только в том, можем ли мы безопасно соединить их концы. Ответ: да, т.к между концами больше нет других точек, т.к. мы заведомо взяли 2 верхние и 2 нижние точки и от каждой начали строить линию.
И все же это не n, а nlogn, т.к. надо сначала отсортировать точки в одном направлении.
Я думал о корректности.
Из любого набора разных точек можно сделать ломанную линию с непересекающимися кусками, соединяя точки одна за другой в одном направлении. Пересечений гарантированно не будет, если между точками в этом направлении нет других точек.
Мы получаем две ломанных линии, не пересекающиеся между собой. Вопрос только в том, можем ли мы безопасно соединить их концы. Ответ: да, т.к между концами больше нет других точек, т.к. мы заведомо взяли 2 верхние и 2 нижние точки и от каждой начали строить линию.
И все же это не n, а nlogn, т.к. надо сначала отсортировать точки в одном направлении.
Ответы815449
>>813319
Занятно, я всегда пользовался сортировкой по полярному углу. Сложность такая же, но алгоритм ка будто чуть попроще, нет двух частей, тупо сортировкой сразу достигаешь нужный порядок с другой стороны, может быть критична скорость работы с float
Занятно, я всегда пользовался сортировкой по полярному углу. Сложность такая же, но алгоритм ка будто чуть попроще, нет двух частей, тупо сортировкой сразу достигаешь нужный порядок с другой стороны, может быть критична скорость работы с float
Ответы817702
Mathematica
(1/Pi) Integrate[((Sin[10x] )/Sin[x])^6, {x, 0, Pi}]
Счастливых билетов: 55252
(1/Pi) Integrate[((Sin[10x] )/Sin[x])^6, {x, 0, Pi}]
Счастливых билетов: 55252
Ответы816923
6 Кб, 539x416
>>813287
А вот в таком случае ты что делаешь? Чёрное - как получается по твоему описанию, зелёное - как должно быть.
А вот в таком случае ты что делаешь? Чёрное - как получается по твоему описанию, зелёное - как должно быть.
Ответы817667
>>816923
А интегрирование аналитическое, без погрешностей.
Хотя если оценить вид первообразной и по пределам оборвать, то можно свести все к вычислению 1109369452791600/20078358300
А интегрирование аналитическое, без погрешностей.
Хотя если оценить вид первообразной и по пределам оборвать, то можно свести все к вычислению 1109369452791600/20078358300
Зо o(n) низя т.к. если можно то можно числа за o(n) сортировать а так низя потому что низя
5 Кб, 971x362
6 Кб, 794x310
>>817083
Нет, все верно у меня.
Главное не ошибиться с выбором лево-право у крайних отрезков. Я сначала выбирал тупо - если p1.x < p2.x, то p1 уходит влево, но это не всегда так. Пример на второй пикче.
Нет, все верно у меня.
Главное не ошибиться с выбором лево-право у крайних отрезков. Я сначала выбирал тупо - если p1.x < p2.x, то p1 уходит влево, но это не всегда так. Пример на второй пикче.
0 Кб, 112x102
>>815449
Понял твое решение, скорее всего, оно лучше.
Хотел придумать корнер-кейс, но сам же на него ответил. При равенстве угла, если он [0; 90], то сортируем по Y возрастающе, если же больше, то убывающе.
Понял твое решение, скорее всего, оно лучше.
Хотел придумать корнер-кейс, но сам же на него ответил. При равенстве угла, если он [0; 90], то сортируем по Y возрастающе, если же больше, то убывающе.
Ответы818434
>>818434
Допустим, мы проходим против часовой стрелки от нижней точки. Если мы сначала возьмем по убывающей, то получатся вершины 1-3-2, что уже ошибка, я это имел в виду.
Допустим, мы проходим против часовой стрелки от нижней точки. Если мы сначала возьмем по убывающей, то получатся вершины 1-3-2, что уже ошибка, я это имел в виду.
Есть правильная скобочная последовательность и внутри неё есть мусорные данные. Для удобства есть ассоциативный массив в котором каждой зная координату одной скобки можно найти координату соответствующей ей скобки. Иногда нужно удалять мусорные данные. И когда это происходит, то размер строки и координаты некоторых скобок меняются, а ассоциативный массив нет. Как максимально быстро вернуть корректные значения в ассоциативный массив?
Пример
s="aa(bbcccb)"
В массиве m лежат 2:7 и 9:-7. Это значит что скобке s[2] соответствует скобка s[2+7], а скобке s[9] скобка s[9-7].
Теперь если удалить все c, то получим s="aa(bbb)" И массив надо будет 2:4 и 6:-4. Скобок может быть больше поэтому на некоторые это удаление влияет, а на некоторые нет.
Формат записи в ассоциативном массиве менять нельзя. т.к. это не совсем ассоциативный массив и в нём ещё хранится инфа по мусорным данным которые не совсем мусорные
Нужно делать это максимально быстро. Память не жалко т.к. размер строки около 10к символов. А вот время нужно экономить т.к. важна каждая миллисекунда.
Как решить?
Пример
s="aa(bbcccb)"
В массиве m лежат 2:7 и 9:-7. Это значит что скобке s[2] соответствует скобка s[2+7], а скобке s[9] скобка s[9-7].
Теперь если удалить все c, то получим s="aa(bbb)" И массив надо будет 2:4 и 6:-4. Скобок может быть больше поэтому на некоторые это удаление влияет, а на некоторые нет.
Формат записи в ассоциативном массиве менять нельзя. т.к. это не совсем ассоциативный массив и в нём ещё хранится инфа по мусорным данным которые не совсем мусорные
Нужно делать это максимально быстро. Память не жалко т.к. размер строки около 10к символов. А вот время нужно экономить т.к. важна каждая миллисекунда.
Как решить?
>>822144
Что за "ассоциативный массив", он совсем медленный, или можно к нему обращаться лишний раз в процессе апдейта?
Пока вижу так: держим массив с координатами всех скобок. Когда надо делать апдейт находим бинарным поиском первую скобку правее места удаления, и начиная с неё до конца массива фиксим каждую скобку.
То есть:
1. Уменьшаем адрес каждой скобки на размер удалённого куска. Скорее всего это подразумевает удаление записи из ассоциативного массива, и добавление новой с другим ключом.
2. Если это закрывающая скобка, а соотв. открывающая левее точки удаления, то обновляем сдвиг в открывающей.
3. Уменьшаем адрес скобки в нашем вспомогательном массиве на размер удалённого куска.
Что за "ассоциативный массив", он совсем медленный, или можно к нему обращаться лишний раз в процессе апдейта?
Пока вижу так: держим массив с координатами всех скобок. Когда надо делать апдейт находим бинарным поиском первую скобку правее места удаления, и начиная с неё до конца массива фиксим каждую скобку.
То есть:
1. Уменьшаем адрес каждой скобки на размер удалённого куска. Скорее всего это подразумевает удаление записи из ассоциативного массива, и добавление новой с другим ключом.
2. Если это закрывающая скобка, а соотв. открывающая левее точки удаления, то обновляем сдвиг в открывающей.
3. Уменьшаем адрес скобки в нашем вспомогательном массиве на размер удалённого куска.
Ответы822616
>>822569
Совсем быстрый. За константу обращение.
И как им искать скобки в не отсортированной строке?
И работает это долго и не правильно.
Вот тест ((abc)()) После удаления любой буквы скобки выделенные жирным трогать не надо. Пока думаю делать вспомогательный массив где отсортированы координаты всех закрывающихся скобок.
Вот например тест "((a)b(c)d)" и удаляем b. В вспомогательном массиве будет 3 7 9. С помощью ассоциативного узнаём координату закрывающейся скобки и проверяем есть ли между ними удалёный элемент. Так должно быть быстрее, но после каждого удаления заново по массиву проходить не хочу, а как после всех удалений применить этот метод не знаю т.к. удалять можно несколько элементов подряд и их потом ещё запоминать придётся.
>он совсем медленный
Совсем быстрый. За константу обращение.
>бинарным поиском
И как им искать скобки в не отсортированной строке?
И работает это долго и не правильно.
Вот тест ((abc)()) После удаления любой буквы скобки выделенные жирным трогать не надо. Пока думаю делать вспомогательный массив где отсортированы координаты всех закрывающихся скобок.
Вот например тест "((a)b(c)d)" и удаляем b. В вспомогательном массиве будет 3 7 9. С помощью ассоциативного узнаём координату закрывающейся скобки и проверяем есть ли между ними удалёный элемент. Так должно быть быстрее, но после каждого удаления заново по массиву проходить не хочу, а как после всех удалений применить этот метод не знаю т.к. удалять можно несколько элементов подряд и их потом ещё запоминать придётся.
Ответы822719
>>822144
Всё зависит от требований: много запросов – меняй за линию, это как угодно можно делать, быстрее за раз всё обновить нельзя, будешь на запросы за 1 отвечать. Много удалений, мало запросов – делай вспомогательный массив "текущей версии" для каждого индекса, и вспомогательное дерево типа дерева отрезков для "обновления" индексов за логарифм и взятия за логарифм (с дальнейшей записью в оригинальный массив и обновлением номера версии, чтобы между вырезаниями только один раз каждый индекс заново считать).
Всё зависит от требований: много запросов – меняй за линию, это как угодно можно делать, быстрее за раз всё обновить нельзя, будешь на запросы за 1 отвечать. Много удалений, мало запросов – делай вспомогательный массив "текущей версии" для каждого индекса, и вспомогательное дерево типа дерева отрезков для "обновления" индексов за логарифм и взятия за логарифм (с дальнейшей записью в оригинальный массив и обновлением номера версии, чтобы между вырезаниями только один раз каждый индекс заново считать).
Ответы822716
>>822710
А как сделать чтобы пока поступают запросы просто заменяешь символы на пробел, а потом за раз всё удаляешь и скобки корректируешь? Это быстрее всего должно работать. Запросы обычно не большие. Несколько байт. Но может много запросов на небольшой участок строки быть.
А как сделать чтобы пока поступают запросы просто заменяешь символы на пробел, а потом за раз всё удаляешь и скобки корректируешь? Это быстрее всего должно работать. Запросы обычно не большие. Несколько байт. Но может много запросов на небольшой участок строки быть.
>>822616
Для "((abc)())" массив индексов скобок будет [0, 1, 5, 6, 7, 8]
как видишь он отсортирован.
Удаление символа в середине строки это уже медленно.
В ассоциативном массиве были записи 6:1 и 7:-1, а должны стать 5:1 и 6:-1, само по себе оно не обновится.
>И как им искать скобки в не отсортированной строке?
Для "((abc)())" массив индексов скобок будет [0, 1, 5, 6, 7, 8]
как видишь он отсортирован.
>И работает это долго
Удаление символа в середине строки это уже медленно.
>и не правильно
>После удаления любой буквы скобки выделенные жирным трогать не надо.
В ассоциативном массиве были записи 6:1 и 7:-1, а должны стать 5:1 и 6:-1, само по себе оно не обновится.
Анончики, может у кого есть нормально отформатированная Конкретная математика в mobi/epub или прочем ebook формате? Я искал, форматировал и все тщетно. А пдф читать на 6 дюймовом киндле не шибко удобно и приятно. Заранее спасибо за ответ.
Вчера писал свой первый раунд на Codeforces, почувствовал себя дауном. Первая задача простая, ну действительно, чего ее решать, давайте посмотрим остальные. Вторая про графы, чет как-то слишком длинное условие, сложна. Третья про пифагоровы тройки. И тут я засел. Родил какое-то стремное решение через числа Фибоначчи (спасибо Википедии за это), а оно зависает на всех нечетных, а на четных выдает не всегда верные ответы. В итоге два часа просидел над этой задачей, ничего не решил, а когда открыл разбор - охуел от простоты и изящества. Это лечится или мне навеки оставаться тупым?
>>824692
лечится. одноклассник не умел решать ничего кроме a и иногда b, а через 1.5. года стал призером всероса.
лечится. одноклассник не умел решать ничего кроме a и иногда b, а через 1.5. года стал призером всероса.
>>824692
А у меня в С неправильное решение принялось. Должен быть TL, а оно принялось. Там я рассматриваю 2 случая:
1) a - катет. Тогда a^2 = (c - b)(c + b). Перебираем все делители числа a^2 (факторизуем a и умножаем все степени на 2; всего делителей будет не больше нескольких тысяч). Для каждого делителя d решаем в натуральных числах систему
{
c + b = d
c - b = a^2/d
}
2) Если a - гипотенуза, то я перебираю b от 1 и до тех пор пока b^2 < a^2, то есть там в цикле может быть 10^9 итераций. Почему у меня нет TL, я не понимаю.
А у меня в С неправильное решение принялось. Должен быть 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
>>824692
>>825960
Какое изящество, тут просто надо знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает, это знают только всякие дрочилы, которые нарешивают олимпиады по математике для школьников.
>>825960
> а когда открыл разбор - охуел от простоты и изящества.
Какое изящество, тут просто надо знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает, это знают только всякие дрочилы, которые нарешивают олимпиады по математике для школьников.
>>825975
А если какие-нибудь методички, в которых подобные тайные знания раскрываются?
А если какие-нибудь методички, в которых подобные тайные знания раскрываются?
>>826006
Не трать на это время, это полная хуйня. На cf есть нормальные задачи на какие-то определенные темы, решение которых помогает в понимании этих тем. То есть это задачи на какие-то алгоритмы или структуры данных, а не на знание того, что нечетное число можно представить в виде разности квадратов. Просто нужно уметь отличать хуету от нормальных задач.
Не трать на это время, это полная хуйня. На cf есть нормальные задачи на какие-то определенные темы, решение которых помогает в понимании этих тем. То есть это задачи на какие-то алгоритмы или структуры данных, а не на знание того, что нечетное число можно представить в виде разности квадратов. Просто нужно уметь отличать хуету от нормальных задач.
>>826006
скиена "олимпиадные задачи по программированию"
>>824692
Я как-то хантился в майкрософт, к Дену Расковалову.
https://www.linkedin.com/in/raskovalov/ru
Он говорит, что только масштабы и время. Тоесть кодфорсес к собеседованиям мало отношения имеет. Так что чтобы решать олимпиады нужно быть задротом и дрочить много именно задачки. Там может быть ад на теорию чисел и комбинаторику. Как в прожект ейлера. После 300 задачек начнешь уже решать без задней мысли. А это полгода дрочильни где-то.
скиена "олимпиадные задачи по программированию"
>>824692
Я как-то хантился в майкрософт, к Дену Расковалову.
https://www.linkedin.com/in/raskovalov/ru
Он говорит, что только масштабы и время. Тоесть кодфорсес к собеседованиям мало отношения имеет. Так что чтобы решать олимпиады нужно быть задротом и дрочить много именно задачки. Там может быть ад на теорию чисел и комбинаторику. Как в прожект ейлера. После 300 задачек начнешь уже решать без задней мысли. А это полгода дрочильни где-то.
>>826059
Спасибо.
Спасибо.
>>826059
А что там на собеседованиях спрашивают? Понятно, что разглашать конкретную информацию нельзя, но разгласи неконкретную.
А что там на собеседованиях спрашивают? Понятно, что разглашать конкретную информацию нельзя, но разгласи неконкретную.
Ответы826087
>>826077
http://poincare.matf.bg.ac.rs/~jelenagr/ASP/testHeadHunter.pdf можешь начать тут, а потом careercup.com
http://poincare.matf.bg.ac.rs/~jelenagr/ASP/testHeadHunter.pdf можешь начать тут, а потом careercup.com
>>826087
послал бы нахуй за такие вопросы на собеседовании
послал бы нахуй за такие вопросы на собеседовании
>>826087
Говно. Не нашёл вопроса про то, в какую сторону едет автобус.
Говно. Не нашёл вопроса про то, в какую сторону едет автобус.
>>792098 (OP)
Здесь обсуждают олимпиаду для поступления в вузы ?
Здесь обсуждают олимпиаду для поступления в вузы ?
Ответы836961
Начал решать задачи на тимусе для закрепления знаний Си.
Как в Си вычислить корень 876652098643267843 ?
http://ideone.com/XVSbT2
Как в Си вычислить корень 876652098643267843 ?
http://ideone.com/XVSbT2
ХОДИШЬ ТАКОЙ НА ОЛИМПИАДЫ, БЕРЕШЬ ПРИЗОВЫЕ МЕСТА
@
ПРИГЛАШАЮТ РАБОТАТЬ В ЯНДЕКС
@
ПОСЛЕ НАПИСАННОГО ТОБОЙ ОБНОВЛЕНИЯ У ВИНДОВС ПОЛЬЗОВАТЕЛЕЙ СЛЕТАЕТ ВИНДОВС СО ВСЕМ СОДЕРЖИМЫМ ДИСКА Ц
@
С ПОЗОРОМ УВОЛЬНЯЮТ
@
КАРЬЕРА В ИТ ДЛЯ ТЕБЯ ЗАКОНЧЕНА, ПИЗДУЕШЬ РАБОТАТЬ ДВОРНИКОМ
Ответы827819
>>827759
ПОСЛЕ ПОДМЕТЕННОГО ТОБОЙ ПОДЪЕЗДА ПОЛОВИНА ЖИТЕЛЕЙ ПОСКАЛЬЗЫВАЮТСЯ И ЛОМАЮТ НОГИ
@
С ПОЗОРОМ УВОЛЬНЯЮТ
ПОСЛЕ ПОДМЕТЕННОГО ТОБОЙ ПОДЪЕЗДА ПОЛОВИНА ЖИТЕЛЕЙ ПОСКАЛЬЗЫВАЮТСЯ И ЛОМАЮТ НОГИ
@
С ПОЗОРОМ УВОЛЬНЯЮТ
Ответы827826
>>827819
@
НЕ ОСТАЕТСЯ НИЧЕГО ДРУГОГО, КАК СТАТЬ НАЕМНЫМ УБИЙЦЕЙ ЗА ДОЗУ ГЕРОИНА
@
ЦЕЛЬ ИЗЛЕЧИВАЕТСЯ ОТ БОЛЕЗНЕЙ ПОД ТВОИМИ УДАРАМИ
@
ВЫГОНЯЮТ БЕЗ ПЕНСИИ
@
НЕ ОСТАЕТСЯ НИЧЕГО ДРУГОГО, КАК СТАТЬ НАЕМНЫМ УБИЙЦЕЙ ЗА ДОЗУ ГЕРОИНА
@
ЦЕЛЬ ИЗЛЕЧИВАЕТСЯ ОТ БОЛЕЗНЕЙ ПОД ТВОИМИ УДАРАМИ
@
ВЫГОНЯЮТ БЕЗ ПЕНСИИ
>>827727
Рекурсивная функция в две строки, решающая одну из первых задач с тимуса. Что доебался до него?
Разве что while я заменил бы на простой if
Рекурсивная функция в две строки, решающая одну из первых задач с тимуса. Что доебался до него?
Разве что while я заменил бы на простой if
На джаве кто-нибудь пишет? Поможете сопитимизировать? У меня TL.
http://codeforces.com/contest/709/problem/E
http://pastebin.com/pW573vzV
Время работы там O(n), в этом точно косяка нет. Я заменил рекурсию на while + stack, потому что до этого был stack overflow. То что инпут с помощью Scanner - это норм, потому что если бы инпут не успевал, у меня бы не доходило до stack overflow в первой версии. От лямбд я уже пробовал избавляться, тоже TL.
http://codeforces.com/contest/709/problem/E
http://pastebin.com/pW573vzV
Время работы там O(n), в этом точно косяка нет. Я заменил рекурсию на while + stack, потому что до этого был stack overflow. То что инпут с помощью Scanner - это норм, потому что если бы инпут не успевал, у меня бы не доходило до stack overflow в первой версии. От лямбд я уже пробовал избавляться, тоже TL.
>>829298
Хотя сейчас замерил, инпут занимает 2 секунды. Сейчас попробую сканер заменить на что-то побыстрее.
Хотя сейчас замерил, инпут занимает 2 секунды. Сейчас попробую сканер заменить на что-то побыстрее.
>>813245
Широковаты. Я от своих тоже в бугурт впадаю.
Широковаты. Я от своих тоже в бугурт впадаю.
>>829344
Сделал. Сначала не сдалось, но потом я еще обернул System.out в BufferedOutputStream и сдалось.
Сделал. Сначала не сдалось, но потом я еще обернул System.out в BufferedOutputStream и сдалось.
Ответы829616
Поясните зашквар или нет вставлять в резюме ссылку на свой профиль на codeforces? Устраиваюсь не в какой-нибудь яндекс, а обычным крудошлепом.
Ответы829615
>>829347
Не понял. А почему BufferedReader не помог? Какая выгода от BufferedOutputStream?
Не понял. А почему BufferedReader не помог? Какая выгода от BufferedOutputStream?
Ответы829999
>>829616
Помог, где-то на полторы секунды быстрее стало, но этого было недостаточно.
В этой задаче аутпут 400000 и выводится по 1 символу, а это очень долго. А buffered сначала ниче не выводит, а когда делаешь flush, выводит все сразу.
Помог, где-то на полторы секунды быстрее стало, но этого было недостаточно.
> Какая выгода от BufferedOutputStream?
В этой задаче аутпут 400000 и выводится по 1 символу, а это очень долго. А buffered сначала ниче не выводит, а когда делаешь flush, выводит все сразу.
>>829615
Максимум 1650 было.
Максимум 1650 было.
>>825975
Если ты не знаешь, что комбинаторный интеграл от 2n+1 равен n(n-1)+n, что ты вообще делаешь в этом треде?
>знать, что любое нечетное число можно представить в виде разности двух квадратов. Нормальный человек этого не знает
Если ты не знаешь, что комбинаторный интеграл от 2n+1 равен n(n-1)+n, что ты вообще делаешь в этом треде?
>>831614
Хуйня для дрочил или специалистов по комбинаторике. Вот ты сколько статей уже написал?
Хуйня для дрочил или специалистов по комбинаторике. Вот ты сколько статей уже написал?
>>831614
Чоблядь?
Интеграл от 2n+1 равен n^2+n+C, чо ты мне загоняешь? и что за хуйню ты написал, n(n-1)+n = n^2
>комбинаторный интеграл
Чоблядь?
Интеграл от 2n+1 равен n^2+n+C, чо ты мне загоняешь? и что за хуйню ты написал, n(n-1)+n = n^2
Это шутка была (про то, что все знают, что такое комбинаторный интеграл). Но то, что (n+1)^2 = n^2 + (2n+1) знают все, а если человек так давно раскрывал такие скобки, то хули он делает в олимпиадном программировании.
А комбинаторный интеграл это понятие тесно связанное с комбинаторной производной.
Комбинаторная производная определяется так: d(F(n)) = F(n+1) - F(n)
Видим, например, что к.п. от 2^n равна 2^(n+1)-2^n = 2^n, то есть 2^n выступает здесь в роли e^x.
Похожие правила работают и для полиномов.
d(n^2) = (n+1)^2 - n^2 = 2n+1, не очень приятное выражение получается.
Но если вместо обычных полиномов использовать полиномы вида n^(k_) = n(n-1)(n-2)(n-3)...(n - k + 1)
то к.п. берётся проще: d(n^(k_)) = k n^((k-1)_)
Например: d(n(n-1)) = (n+1)n - n(n-1) = 2n
Тут есть ещё много разных вариаций, которые можно вывести, например, d(f(n) g(n)) = f(n) d(g(n)) +d(f(n)) g(n + 1) = f(n+1) d(g(n)) + d(f(n)) g(n)
выглядит почти как правило умножения для производных.
Польза от такой производной в том, что можно взять от неё комбинаторный интеграл. То есть по функции f(n) найти функцию F(n), такую, что F(n+1) - F(n) = f(n)
Зачем нужна эта штука? Допустим, мы хотим найти сумму
f(1) + f(2) + ... + f(k), для этого можно переписать эту сумму как (F(2) - F(1)) + (F(3) - F(2) + ... + (F(k + 1) - F(k)) = F(k+1) - F(1)
Магия - мы научились сворачивать ряды в closed-form формулу.
Пример: найти сумму 1 + 2 + 3 + ... + n
К.и. от n равняется n(n-1) / 2, значит ответ - (n+1)*n / 2 - 0 = (n+1)n/2
Пример 2: найти сумму 1^2 + 2^2 + 3^2 + ... + n^2
Чтобы проинтегрировать n^2 нужно сначала представить его в базисе n^(k_), а именно: n^2 = n^2_ + n, легко проверить: n^2 = n(n-1) + n = n^2
Берём интеграл от n^2_ + n, он равен n^3_ / 3 + n^2_ / 2
Раскрываем скобки: n(n-1)( (n - 2) / 3 + 1/2 ) = n(n-1)(2n - 1)/6
Подставляем границы, ответ равен (n+1)n(2n+1)/6 - 0
Подставляя n=2 и n=3 убеждаемся, что мы нигде не ошиблись.
Если интересно, можете таким способом найти сумму
k 2^k для k=1...n
Подсказка: интегрирование по частям.
А комбинаторный интеграл это понятие тесно связанное с комбинаторной производной.
Комбинаторная производная определяется так: d(F(n)) = F(n+1) - F(n)
Видим, например, что к.п. от 2^n равна 2^(n+1)-2^n = 2^n, то есть 2^n выступает здесь в роли e^x.
Похожие правила работают и для полиномов.
d(n^2) = (n+1)^2 - n^2 = 2n+1, не очень приятное выражение получается.
Но если вместо обычных полиномов использовать полиномы вида n^(k_) = n(n-1)(n-2)(n-3)...(n - k + 1)
то к.п. берётся проще: d(n^(k_)) = k n^((k-1)_)
Например: d(n(n-1)) = (n+1)n - n(n-1) = 2n
Тут есть ещё много разных вариаций, которые можно вывести, например, d(f(n) g(n)) = f(n) d(g(n)) +d(f(n)) g(n + 1) = f(n+1) d(g(n)) + d(f(n)) g(n)
выглядит почти как правило умножения для производных.
Польза от такой производной в том, что можно взять от неё комбинаторный интеграл. То есть по функции f(n) найти функцию F(n), такую, что F(n+1) - F(n) = f(n)
Зачем нужна эта штука? Допустим, мы хотим найти сумму
f(1) + f(2) + ... + f(k), для этого можно переписать эту сумму как (F(2) - F(1)) + (F(3) - F(2) + ... + (F(k + 1) - F(k)) = F(k+1) - F(1)
Магия - мы научились сворачивать ряды в closed-form формулу.
Пример: найти сумму 1 + 2 + 3 + ... + n
К.и. от n равняется n(n-1) / 2, значит ответ - (n+1)*n / 2 - 0 = (n+1)n/2
Пример 2: найти сумму 1^2 + 2^2 + 3^2 + ... + n^2
Чтобы проинтегрировать n^2 нужно сначала представить его в базисе n^(k_), а именно: n^2 = n^2_ + n, легко проверить: n^2 = n(n-1) + n = n^2
Берём интеграл от n^2_ + n, он равен n^3_ / 3 + n^2_ / 2
Раскрываем скобки: n(n-1)( (n - 2) / 3 + 1/2 ) = n(n-1)(2n - 1)/6
Подставляем границы, ответ равен (n+1)n(2n+1)/6 - 0
Подставляя n=2 и n=3 убеждаемся, что мы нигде не ошиблись.
Если интересно, можете таким способом найти сумму
k 2^k для k=1...n
Подсказка: интегрирование по частям.
Это шутка была (про то, что все знают, что такое комбинаторный интеграл). Но то, что (n+1)^2 = n^2 + (2n+1) знают все, а если человек так давно раскрывал такие скобки, то хули он делает в олимпиадном программировании.
А комбинаторный интеграл это понятие тесно связанное с комбинаторной производной.
Комбинаторная производная определяется так: d(F(n)) = F(n+1) - F(n)
Видим, например, что к.п. от 2^n равна 2^(n+1)-2^n = 2^n, то есть 2^n выступает здесь в роли e^x.
Похожие правила работают и для полиномов.
d(n^2) = (n+1)^2 - n^2 = 2n+1, не очень приятное выражение получается.
Но если вместо обычных полиномов использовать полиномы вида n^(k_) = n(n-1)(n-2)(n-3)...(n - k + 1)
то к.п. берётся проще: d(n^(k_)) = k n^((k-1)_)
Например: d(n(n-1)) = (n+1)n - n(n-1) = 2n
Тут есть ещё много разных вариаций, которые можно вывести, например, d(f(n) g(n)) = f(n) d(g(n)) +d(f(n)) g(n + 1) = f(n+1) d(g(n)) + d(f(n)) g(n)
выглядит почти как правило умножения для производных.
Польза от такой производной в том, что можно взять от неё комбинаторный интеграл. То есть по функции f(n) найти функцию F(n), такую, что F(n+1) - F(n) = f(n)
Зачем нужна эта штука? Допустим, мы хотим найти сумму
f(1) + f(2) + ... + f(k), для этого можно переписать эту сумму как (F(2) - F(1)) + (F(3) - F(2) + ... + (F(k + 1) - F(k)) = F(k+1) - F(1)
Магия - мы научились сворачивать ряды в closed-form формулу.
Пример: найти сумму 1 + 2 + 3 + ... + n
К.и. от n равняется n(n-1) / 2, значит ответ - (n+1)*n / 2 - 0 = (n+1)n/2
Пример 2: найти сумму 1^2 + 2^2 + 3^2 + ... + n^2
Чтобы проинтегрировать n^2 нужно сначала представить его в базисе n^(k_), а именно: n^2 = n^2_ + n, легко проверить: n^2 = n(n-1) + n = n^2
Берём интеграл от n^2_ + n, он равен n^3_ / 3 + n^2_ / 2
Раскрываем скобки: n(n-1)( (n - 2) / 3 + 1/2 ) = n(n-1)(2n - 1)/6
Подставляем границы, ответ равен (n+1)n(2n+1)/6 - 0
Подставляя n=2 и n=3 убеждаемся, что мы нигде не ошиблись.
Если интересно, можете таким способом найти сумму
k 2^k для k=1...n
Подсказка: интегрирование по частям.
А комбинаторный интеграл это понятие тесно связанное с комбинаторной производной.
Комбинаторная производная определяется так: d(F(n)) = F(n+1) - F(n)
Видим, например, что к.п. от 2^n равна 2^(n+1)-2^n = 2^n, то есть 2^n выступает здесь в роли e^x.
Похожие правила работают и для полиномов.
d(n^2) = (n+1)^2 - n^2 = 2n+1, не очень приятное выражение получается.
Но если вместо обычных полиномов использовать полиномы вида n^(k_) = n(n-1)(n-2)(n-3)...(n - k + 1)
то к.п. берётся проще: d(n^(k_)) = k n^((k-1)_)
Например: d(n(n-1)) = (n+1)n - n(n-1) = 2n
Тут есть ещё много разных вариаций, которые можно вывести, например, d(f(n) g(n)) = f(n) d(g(n)) +d(f(n)) g(n + 1) = f(n+1) d(g(n)) + d(f(n)) g(n)
выглядит почти как правило умножения для производных.
Польза от такой производной в том, что можно взять от неё комбинаторный интеграл. То есть по функции f(n) найти функцию F(n), такую, что F(n+1) - F(n) = f(n)
Зачем нужна эта штука? Допустим, мы хотим найти сумму
f(1) + f(2) + ... + f(k), для этого можно переписать эту сумму как (F(2) - F(1)) + (F(3) - F(2) + ... + (F(k + 1) - F(k)) = F(k+1) - F(1)
Магия - мы научились сворачивать ряды в closed-form формулу.
Пример: найти сумму 1 + 2 + 3 + ... + n
К.и. от n равняется n(n-1) / 2, значит ответ - (n+1)*n / 2 - 0 = (n+1)n/2
Пример 2: найти сумму 1^2 + 2^2 + 3^2 + ... + n^2
Чтобы проинтегрировать n^2 нужно сначала представить его в базисе n^(k_), а именно: n^2 = n^2_ + n, легко проверить: n^2 = n(n-1) + n = n^2
Берём интеграл от n^2_ + n, он равен n^3_ / 3 + n^2_ / 2
Раскрываем скобки: n(n-1)( (n - 2) / 3 + 1/2 ) = n(n-1)(2n - 1)/6
Подставляем границы, ответ равен (n+1)n(2n+1)/6 - 0
Подставляя n=2 и n=3 убеждаемся, что мы нигде не ошиблись.
Если интересно, можете таким способом найти сумму
k 2^k для k=1...n
Подсказка: интегрирование по частям.
Циановый даун с кодефорсеса цвета морской волны ищет боевого товарища, чтобы в соревновательно-помогательном режиме ботать прогу. По заявкам оставляю фейко-контакты
Ответы832722
>>832679
Это сколько, 1200-1400 что ли? Могу просто так тебе помочь если че, спрашивай. Я максимум был синим.
Это сколько, 1200-1400 что ли? Могу просто так тебе помочь если че, спрашивай. Я максимум был синим.
Ответы832725
>>832722
1400 - 1600. У меня вопросов особо нет. Надо только надрочиться. А одному это уныленько.
1400 - 1600. У меня вопросов особо нет. Надо только надрочиться. А одному это уныленько.
Ответы832845
>>832725
Ты хочешь сказать, что у тебя в городе нет ни одного места, куда можно ходить на тренировки по асм?
Ты хочешь сказать, что у тебя в городе нет ни одного места, куда можно ходить на тренировки по асм?
Ответы833063
79 Кб, 963x329
Ответы833376
>>832845
Есть. Но этого разве достаточно?
Есть. Но этого разве достаточно?
Ответы833281
>>833204
Нет, я сомневаюсь, что Егор будет вести курс по Android в сраном МИРЭА.
Нет, я сомневаюсь, что Егор будет вести курс по Android в сраном МИРЭА.
Самолет взлетает в X (целое, 0<=X<=23) часов по местному времени в часовом поясе номер M (целое, 0<=M<=23). После полета в течение K (целое, 1<=K<=12) часов он приземляется в часовом поясе номер N (целое, 0<=N<=23). Определите местное время в пункте приземления. Считать, что часовые пояса нумеруются с запада на восток.
Тупая задачка. Почему нельзя просто прибавить ко времени старта врем полета, а потом прибавить разность номеров часовых поясов?
Тупая задачка. Почему нельзя просто прибавить ко времени старта врем полета, а потом прибавить разность номеров часовых поясов?
>>834027
Все, разобрался. Идите нахуй
Все, разобрался. Идите нахуй
>>834027
А кто тебе сказал, что нельзя? Летал самолет или нет, значения не имеет, от этого разница во времени между часовыми поясами не изменится. Здесь просто спрашивается, какое время будет в другом часовом поясе через n-цать часов. И какое все это имеет отношение к погромированию?
А кто тебе сказал, что нельзя? Летал самолет или нет, значения не имеет, от этого разница во времени между часовыми поясами не изменится. Здесь просто спрашивается, какое время будет в другом часовом поясе через n-цать часов. И какое все это имеет отношение к погромированию?
Эй, умники. Есть задачка. У нас имеется n целых неотрицательных чисел, чья сумма не превосходит 10^5. Еще есть некое m до 10^4. Все эти n чисел мы хотим представить в виде целых долей этого числа m, причем нецелые доли мы вольны округлять в любую сторону по желанию левой пятки. Я тут набросал тупой жадник, который, конечно же, доказывать не умею, и он отхватывает wa2. Жадник настолько тупой, что он все округляет вверх, а потом, переокругляет вниз пока не получим нужную сумму, равную m
http://ideone.com/3x53a2
http://ideone.com/3x53a2
Ответы836275
>>835570
Дай ссылку на исходную задачу, потому что ты во-первых написал условие как мудак (блядь, неужели нельзя скриншот запостить хотя бы, и пару примером входа выхода), а во-вторых лучше засабмитить, чем какому-то петуху объяснять.
Дай ссылку на исходную задачу, потому что ты во-первых написал условие как мудак (блядь, неужели нельзя скриншот запостить хотя бы, и пару примером входа выхода), а во-вторых лучше засабмитить, чем какому-то петуху объяснять.
Ответы836278
175 Кб, 1366x768
>>836275
Ну, вот тебе скриншот. А самой задачи на публичных тестилках я не видел. Свой жадник пока что я опровергнуть так и не смог
Ну, вот тебе скриншот. А самой задачи на публичных тестилках я не видел. Свой жадник пока что я опровергнуть так и не смог
Ответы836282
>>836278
Ну вот так-то лучше. Сам-то чувствуешь, что гораздо понятнее выглядит? Очевидная динамика же.
Ну вот так-то лучше. Сам-то чувствуешь, что гораздо понятнее выглядит? Очевидная динамика же.
Ответы836283
>>836282
Я, конечно, толком в динамику не умею. Но тут и намеков не вижу. Не просветишь?
Я, конечно, толком в динамику не умею. Но тут и намеков не вижу. Не просветишь?
Ответы836284
>>836283
Хотя тут даже динамика не нужна, жадный алгоритм должен работать. У тебя, наверное, просто не проверяется, что если число нацело делится, то его двигать нельзя уже.
Хотя тут даже динамика не нужна, жадный алгоритм должен работать. У тебя, наверное, просто не проверяется, что если число нацело делится, то его двигать нельзя уже.
Ответы836287
>>836284
Так ceil же не должен целое число округлять. Или там с точностью может быть лажа?
Так ceil же не должен целое число округлять. Или там с точностью может быть лажа?
Ну динамика, если интересно, такая: f(arr[i:], amount) - можно ли набрать amount сумму, округляя как-нибудь числа начиная с i-й позиции, как в рюкзаке, и по времени проходит - 50е6. Только, повторяюсь, она тут не нужна.
Ответы836291
Ответы836295
Ответы836295
>>836295
Да. Я уже вижу. Спасибо, мил человек
Да. Я уже вижу. Спасибо, мил человек
Сколько сюда не захожу, так и не пойму, чем вы тут занимаетесь
Ответы836961
>>836961
Игра в доту — это спорт. Решение олимпиадных задач по программированию — это не спорт. Выводы делай сам.
> Спортом вестимо.
Игра в доту — это спорт. Решение олимпиадных задач по программированию — это не спорт. Выводы делай сам.
У всех cf лежит?
Ответы839721
>>839721
Пидора ответ.
Пидора ответ.
Как научиться решать CTF?
Ответы840861
>>840732
Приходишь на ctf. Дальше все понятно.
Серьезно. Обычно есть отборочные туры, где есть возможность гуглить
Приходишь на ctf. Дальше все понятно.
Серьезно. Обычно есть отборочные туры, где есть возможность гуглить
Ответы840875
>>840875
Идешь на отборочный тур и узнаешь. Там бывают разные задания: криптография, сети, крекинг етц
Идешь на отборочный тур и узнаешь. Там бывают разные задания: криптография, сети, крекинг етц
284 Кб, 1366x768
Олимпач, я тебе задачу подвез. Пока из идей посортить стержни по максимальному расстоянию от конца до точки d, а потом как-то хитро посчитать. Хитро что-то не выдумывается
Ответы843169
>>843105
Допустим все числа нечетные, тогда просто расположим их так, чтобы их середины находились на оси x и будем зажигать от самого длинного к самому короткому. Допустим, нечетные, тогда то же самое.
Допустим есть четные и нечетные числа. Например, 2 стержня 4 и 5. Тогда придётся все числа той же четности, что и максимальное, зажечь с одного конца, чтобы сделать всех одной четности, а потом применить алгоритм из первого параграфа.
Допустим все числа нечетные, тогда просто расположим их так, чтобы их середины находились на оси x и будем зажигать от самого длинного к самому короткому. Допустим, нечетные, тогда то же самое.
Допустим есть четные и нечетные числа. Например, 2 стержня 4 и 5. Тогда придётся все числа той же четности, что и максимальное, зажечь с одного конца, чтобы сделать всех одной четности, а потом применить алгоритм из первого параграфа.
Ответы843189
>>843169
С четными и нечетными я хуйню написал.
Короче зажигаешь самый длинный стержень с двух сторон, а дальше изъебывайся как хочешь, но чтоб все в один момент лопнули. Это можно сделать.
В первую секунду зажигаешь самый длинный стержень с двух сторон, а стержни длины на 1 меньше - с одной стороны, во вторую секунду все стержни которые горят с одной стороны поджигаешь со второй, а все стержни на 1 меньше - с одной стороны. И так далее.
С четными и нечетными я хуйню написал.
Короче зажигаешь самый длинный стержень с двух сторон, а дальше изъебывайся как хочешь, но чтоб все в один момент лопнули. Это можно сделать.
В первую секунду зажигаешь самый длинный стержень с двух сторон, а стержни длины на 1 меньше - с одной стороны, во вторую секунду все стержни которые горят с одной стороны поджигаешь со второй, а все стержни на 1 меньше - с одной стороны. И так далее.
Ответы843304
>>843304
А, там ещё и определённая точка должна загореться последней, вот я мудак.
А, там ещё и определённая точка должна загореться последней, вот я мудак.
>>797533
ты ебанулся? база индукции очевидно верная. переход не верен (при п=2)
ты ебанулся? база индукции очевидно верная. переход не верен (при п=2)
Я умею искать гамильтонов путь в неорграфе динамикой по подмножествам, где вершин не больше 20. А вот теперь мне надо проверить наличие гамильтонова пути в ацикличном орграфе с количеством вершин вплоть до 10^5. Вроде простая задача должна быть. Думаю пока в сторону топсорта какого-то
>>846398
Сравни длину длиннейшего пути с количеством вершин + 1.
https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths
Сравни длину длиннейшего пути с количеством вершин + 1.
https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths
>>846398
>>846526
Честно говоря не понимаю зачем пишут топсорт делать. Наверное чтобы достичь O(N) вместо O(N*log(n)).
По идее достаточно для каждой вершины предрасчитать списки входящих соседей (если вершин с пустым списком >1, то гамильтонова пути сразу нет), а потом пока есть нерассмотренные вершины берёшь рандомную считаешь расстояние от истока до этой вершины как максимум среди её входящих соседей+1. Применяешь алгоритм рекурсивно, не забывая про мемоизацию.
Короче как поиск кратчайшего, только длиннейшего.
>>846526
Честно говоря не понимаю зачем пишут топсорт делать. Наверное чтобы достичь O(N) вместо O(N*log(n)).
По идее достаточно для каждой вершины предрасчитать списки входящих соседей (если вершин с пустым списком >1, то гамильтонова пути сразу нет), а потом пока есть нерассмотренные вершины берёшь рандомную считаешь расстояние от истока до этой вершины как максимум среди её входящих соседей+1. Применяешь алгоритм рекурсивно, не забывая про мемоизацию.
Короче как поиск кратчайшего, только длиннейшего.
Ответы846934
>>792725
Эх, щас бы в 2016 перебором задачу решать, вместо динамического программирования
Эх, щас бы в 2016 перебором задачу решать, вместо динамического программирования
Окей. Как быстро проверять достижимость каждой вершины из каждой по матрице достижимости? Вершин всего тысяча, но флойд не вариант, потому что там сверху еще будет логн от бинпоиска висеть. Граф плотный, поэтому бфс меня тоже смущает. Или нормально?
>>847029
>>846965
Я, кажется, придумал, что хочу по матрице смежности быстро строить матрицу достижимости
>>846965
Я, кажется, придумал, что хочу по матрице смежности быстро строить матрицу достижимости
Ответы847202
>>847202
Пиздец я проебался, думал граф неориентированный, тогда это просто бинпоиск и SCC
Пиздец я проебался, думал граф неориентированный, тогда это просто бинпоиск и SCC
Нужны две функции. Одна принимает английский неправильный глагол, а возвращает его первую форму, а вторая получает рандомное слово и составляет кучу других слов из таких-же букв. Какие есть способы это сделать быстро?
>>846939
BFS/DFS, компоненты связности. Предподсчёт за V^2, дальше ответ за 1.
BFS/DFS, компоненты связности. Предподсчёт за V^2, дальше ответ за 1.
бумп
>>792098 (OP)
Пререквизиты для Кормена и Кнутопаташика есть ли? Скожите пожалуйста.
Пререквизиты для Кормена и Кнутопаташика есть ли? Скожите пожалуйста.
Ответы861784
Для Кормена только мозг нужен, ну там подумать иногда придётся. Кнутопаташника не читал.
>>856298
У Кормена есть в конце книги поясняется за математику
У Кормена есть в конце книги поясняется за математику
Парни, есть какой нибудь сайт, где перечислены основные олимпиадные алгоритмы? А то я знаю только викиалгоритмы, а он бесполезен для этого
>>861999
огромнейшее спасибо
огромнейшее спасибо
Что, как поживаете? Я вот тут недавно школьную командную олимпиадку писал. Суть в том, что я-то алгоритмов довольно много знаю, могу написать. Префикс, з функции, декартачи, до, всякие графы, хэши. Но, сука, проблема в том, что в команде я ничего не придумывал. Мне говорили: "пиши топсорт, потом проверяй наличие соседних ребер". Или: "Склей строчки, посчитай префикс функцию, пока суффикс совпадает с префиксом, удаляй их. Я, бля, даже условия оригинального не знаю.
Это все круто, но на личной олимпиаде не проканает. Неумение быстро выдумывать решения - это приговор? Или еще есть шанс до феврали задрочить задачки из первой полутысячи тимуса?
Это все круто, но на личной олимпиаде не проканает. Неумение быстро выдумывать решения - это приговор? Или еще есть шанс до феврали задрочить задачки из первой полутысячи тимуса?
Ответы864060
Есть программа с кучей функций. У каждой функции есть название. Известно количество обращений к каждой функции за последнее время.
Надо назначить функциям однобуквенные хоткеи так, чтобы сумма чисел обращений к функциям, которым назначены хоткеи, была максимальна.
Хоткеем функции можно назначить только букву, входяшую в её название.
Знаю про венгерский алгоритм, но у меня вес дуги из функции в каждую из допустимых клавиш одинаков. Есть ли что-то быстрее для такого случая?
Надо назначить функциям однобуквенные хоткеи так, чтобы сумма чисел обращений к функциям, которым назначены хоткеи, была максимальна.
Хоткеем функции можно назначить только букву, входяшую в её название.
Знаю про венгерский алгоритм, но у меня вес дуги из функции в каждую из допустимых клавиш одинаков. Есть ли что-то быстрее для такого случая?
>>863521
на то в команде всегда и есть два прогера, один комп, и один математик который придумывает решения, сечешь?
на то в команде всегда и есть два прогера, один комп, и один математик который придумывает решения, сечешь?
Ответы864257
>>864060
Да. Но мне до студенческих командных нужно дописать личные олимпиадки, где один прогер и один математик в моем лице
Да. Но мне до студенческих командных нужно дописать личные олимпиадки, где один прогер и один математик в моем лице
Вы меня удивляете.
Пишу на крестах и пухтоне.
Последнее время само-собой приходится дрочить адгоритмизацию и математику, причем комбинаторику и статистику (что ненавижу, лучше дифуры).
Я чет не понимаю, как программист может не мочь в такое? Что за бред? Это как себя не уважать.
Пишу на крестах и пухтоне.
Последнее время само-собой приходится дрочить адгоритмизацию и математику, причем комбинаторику и статистику (что ненавижу, лучше дифуры).
Я чет не понимаю, как программист может не мочь в такое? Что за бред? Это как себя не уважать.
>>864307
держите матаноблядь!11
>адгоритмизацию и математику, причем комбинаторику и статистику (что ненавижу, лучше дифуры)
держите матаноблядь!11
>>864557
hellburnization is a part of CS
hellburnization is a part of CS
>>864307
не все такие умные и не все так рано начинали, мне вот 30 лет и на тимусе у меня 50 задач, в школе был далек от программистов, даже не знал об этом, но как сейчас выяснилось тогда по матеше я обходил парней ныне уже участников финала мира acm icpc
не все такие умные и не все так рано начинали, мне вот 30 лет и на тимусе у меня 50 задач, в школе был далек от программистов, даже не знал об этом, но как сейчас выяснилось тогда по матеше я обходил парней ныне уже участников финала мира acm icpc
Пишу алгоритм для игры. В ней нужно набрать максимум очков. Их количество не может уменьшаться. Есть фактор случайности. игра похожа на монополию и количество возможных исходов одного хода меньше чем у шахмат При этом игра может закончиться совсем неожиданно если неколько ходов подряд кубик будет плохо падать. Значит обычный minmax не подойдёт т.к. при большой глубине поиска лучший из худших всегда будет проигрыш. И что делать с линией горизонта? Ведь здесь нельзя форсировать поиск при шахе как в махматах. Реквестирую литературу про программирование ии для игр с влиянием рандома.
Ответы865292
>>865189
Не понял проблему. Оцениваешь все исходы броска кубика, и считаешь матожидание оценок. Или не просто матожидание, а матожидание от некоторой функции, учитывающей твоё отношение к риску. Например если надо срочно догонять противника имеет смысл оценивать нулём исходы, которые не дают тебе достаточно очков.
Пиши эвристический алгоритм.
Если хочешь можно ещё сделать обход дерева ограниченной глубины, а по достижении дна считать оценку. Эвристикой опять же. Альтернативно можно использовать метод Монте-Карло. Берёшь начальное положение и много-много раз отыгрываешь его до конца каким-то простым алгоритмом за обоих игроков, а потом по результатам отыгрышей даёшь оценку положению. Но мне кажется эвристика будет точнее.
Ты слишком напрягаешься, смотри как люди делают:
https://github.com/intrepidcoder/monopoly/blob/gh-pages/ai.js
https://github.com/DepthDeluxe/Monopoly/blob/master/src/monopoly/AIPlayer.java
>обычный minmax не подойдёт т.к. при большой глубине поиска лучший из худших всегда будет проигрыш
Не понял проблему. Оцениваешь все исходы броска кубика, и считаешь матожидание оценок. Или не просто матожидание, а матожидание от некоторой функции, учитывающей твоё отношение к риску. Например если надо срочно догонять противника имеет смысл оценивать нулём исходы, которые не дают тебе достаточно очков.
>похожа на монополию
Пиши эвристический алгоритм.
Если хочешь можно ещё сделать обход дерева ограниченной глубины, а по достижении дна считать оценку. Эвристикой опять же. Альтернативно можно использовать метод Монте-Карло. Берёшь начальное положение и много-много раз отыгрываешь его до конца каким-то простым алгоритмом за обоих игроков, а потом по результатам отыгрышей даёшь оценку положению. Но мне кажется эвристика будет точнее.
>Реквестирую литературу
Ты слишком напрягаешься, смотри как люди делают:
https://github.com/intrepidcoder/monopoly/blob/gh-pages/ai.js
https://github.com/DepthDeluxe/Monopoly/blob/master/src/monopoly/AIPlayer.java
Ответы865330
>>865292
Так и хочу. Но уже на небольшой глубине можно получить большую оценку, но это будет проигрыш и конец игры. Если в одну и ту же сторону идти, то скоро проиграешь. А в алгоритме перебираются все возможные направления и все возможные броски кубика. Потом смотриться на конкретную глубину и выбираеться тот ход минималиный профит от которого самый большой. Что делать с этими проигрышными тупиками?
И исходники читать не интересно. Хоть статьи скинь.
> обход дерева ограниченной глубины, а по достижении дна считать оценку
Так и хочу. Но уже на небольшой глубине можно получить большую оценку, но это будет проигрыш и конец игры. Если в одну и ту же сторону идти, то скоро проиграешь. А в алгоритме перебираются все возможные направления и все возможные броски кубика. Потом смотриться на конкретную глубину и выбираеться тот ход минималиный профит от которого самый большой. Что делать с этими проигрышными тупиками?
И исходники читать не интересно. Хоть статьи скинь.
Ответы865348
>>865330
Оценка не обязательно равна количеству очков. Это может быть и разность очков у тебя и противника, и сложная функция, учитывающая ещё и ситуацию на доске.
Никто не запрещает тебе назначать проигрышам оценку 0.
>получить большую оценку, но это будет проигрыш и конец игры
Оценка не обязательно равна количеству очков. Это может быть и разность очков у тебя и противника, и сложная функция, учитывающая ещё и ситуацию на доске.
Никто не запрещает тебе назначать проигрышам оценку 0.
Ответы865385
>>865348
Так может быть так что все ходы проигрышные. Надо что-то выбрать из тех нулей. Может их в 2 очереди проверять? А с горизонтом что делать? Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный. А алгоритм только на 5 вглубь смотрит и войдёт в проинрышную ветку из которой не выйти.
Так может быть так что все ходы проигрышные. Надо что-то выбрать из тех нулей. Может их в 2 очереди проверять? А с горизонтом что делать? Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный. А алгоритм только на 5 вглубь смотрит и войдёт в проинрышную ветку из которой не выйти.
Ответы865446
>>864996
Ну, так, ты мне какой-то теорию категорий с универсальной алгеброй тычешь. Статистика тут при чём?
Ну, так, ты мне какой-то теорию категорий с универсальной алгеброй тычешь. Статистика тут при чём?
Ответы865490
>>865385
Если у всех стратегий одинаковая оценка, то выбираешь рандомно.
Ну блин, делай как в шахматах делают. По достижении дна оценивай положение на доске эвристикой. В шахматах фигурам назначают цену, цены имеющихся фигур складывают, и ещё как-то расположение учитывают, хз как. Так получают примерную оценку для позиций на дне. Тебе тоже надо придумать эвристику для оценки позиции. Как это сделать я подсказать не могу, тут надо пробовать варианты и проявлять изобретательность.
Попробуй решить https://projecteuler.net/problem=84 может придумаешь как прикрутить себе сети Маркова.
В настолке с кубиком такое нереально. Там слишком много рандома. По этой же причине нет смысла делать сложный алгоритм - разница в уровне игры по сравнению с тривиальным "покупай всё что можешь" будет практически незаметна человеку.
>Так может быть так что все ходы проигрышные. Надо что-то выбрать из тех нулей.
Если у всех стратегий одинаковая оценка, то выбираешь рандомно.
>А с горизонтом что делать?
Ну блин, делай как в шахматах делают. По достижении дна оценивай положение на доске эвристикой. В шахматах фигурам назначают цену, цены имеющихся фигур складывают, и ещё как-то расположение учитывают, хз как. Так получают примерную оценку для позиций на дне. Тебе тоже надо придумать эвристику для оценки позиции. Как это сделать я подсказать не могу, тут надо пробовать варианты и проявлять изобретательность.
Попробуй решить https://projecteuler.net/problem=84 может придумаешь как прикрутить себе сети Маркова.
>Можнт быть так что цепочка из 5 ходов много очков приносит, а любой шестой ходов проигрышный.
В настолке с кубиком такое нереально. Там слишком много рандома. По этой же причине нет смысла делать сложный алгоритм - разница в уровне игры по сравнению с тривиальным "покупай всё что можешь" будет практически незаметна человеку.
>>865443
Чего? На диаграмме показаны соотношения между распределениями случайных величин.
Чего? На диаграмме показаны соотношения между распределениями случайных величин.
>>792140
len([x for x in range(100000, 999999) if sum(map(lambda x: int(x[0]) - int(x[1]),
zip(str(x // 1000), str(x % 1000)))) == 0])
len([x for x in range(100000, 999999) if sum(map(lambda x: int(x[0]) - int(x[1]),
zip(str(x // 1000), str(x % 1000)))) == 0])
>>865492
Ошибка вышла:
len([x for x in range(100000, 1000000) if sum(map(lambda x: int(x[0]) - int(x[1]),
zip(str(x // 1000).ljust(3, '0'), str(x % 1000).ljust(3, '0')))) == 0])
Ошибка вышла:
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
>>867885
Мне это напомнило задачу с прошлогоднего полуфинала или даже финала. Копни в эту сторону Насколько я помню, там отчасти рандомизированный алгоритм. Сперва что-то поспрашивать, а потом решать.
Мне это напомнило задачу с прошлогоднего полуфинала или даже финала. Копни в эту сторону Насколько я помню, там отчасти рандомизированный алгоритм. Сперва что-то поспрашивать, а потом решать.
Ответы867898
>>867898
Прости, я тебе наврал. Мне почему-то вспомнилась задача J https://neerc.ifmo.ru/archive/2015/neerc-2015.pdf
Но это совсем из другой оперы
Прости, я тебе наврал. Мне почему-то вспомнилась задача J https://neerc.ifmo.ru/archive/2015/neerc-2015.pdf
Но это совсем из другой оперы
Ответы867903
>>867903
http://rce.su/randomizirovannyj-protokol-svyazi-chast-1/
Вот это попробуй почитать.
А откуда задача?
http://rce.su/randomizirovannyj-protokol-svyazi-chast-1/
Вот это попробуй почитать.
А откуда задача?
Ответы867918
>>867907
Хорошо, спасибо. На паре по дискретной математике задали.:(
Хорошо, спасибо. На паре по дискретной математике задали.:(
С трудом даются задачи из Конкретной математики. Это нормально? Продолжать задрачивать или прочитать что-нибудь полегче сначала?
Ответы870911
>>870911
Да, спасибо, подходит
Да, спасибо, подходит
анон, в какой порядке решать задачи на codeforces? самые популярные, новые, только A, B..., только div 2 или без разницы?
Ответы873631
>>873630
Отсортируй по количеству решивших. Начинай решать. Если чуешь, что очень легко идет, листай на следующую страницу
Отсортируй по количеству решивших. Начинай решать. Если чуешь, что очень легко идет, листай на следующую страницу
Ответы873646
>>873631
спасибо, так и сделаю
спасибо, так и сделаю
>>875022
http://ideone.com/iTglQT
>>875130
Ты внимательно прочитал условие?
Особенно про то, что размеры строк r^2, а памяти - r, и что она неперезаписываемая?
http://ideone.com/iTglQT
>>875130
Ты внимательно прочитал условие?
Особенно про то, что размеры строк r^2, а памяти - r, и что она неперезаписываемая?
>>875163
Да, задачка решается для строк размера r^2 , r бит неперзаписываемой памяти и r+1 запросе. Я думал, это очевидно.
Да, задачка решается для строк размера r^2 , r бит неперзаписываемой памяти и r+1 запросе. Я думал, это очевидно.
Ответы875366
Стандартная задачка егэ:
Из ряда натуральных чисел выбрать произвольное количество чисел так, чтобы их сумма не делилась на 6. При этом сумму надо максимизировать. На выход количество выбранных чисел и их сумму. Я не совсем ньюфаг в олимпиадном программировании, но тут встал в тупик. А егэ сдавать надо
Из ряда натуральных чисел выбрать произвольное количество чисел так, чтобы их сумма не делилась на 6. При этом сумму надо максимизировать. На выход количество выбранных чисел и их сумму. Я не совсем ньюфаг в олимпиадном программировании, но тут встал в тупик. А егэ сдавать надо
>>875307
Динамическое программирование: f(i, c) = максимальная сумма подпоследовательности arr[:i], делящаяся на c.
Динамическое программирование: f(i, c) = максимальная сумма подпоследовательности arr[:i], делящаяся на c.
Ответы875318
>>875316
s/делящаяся на c/дающая c в остатке при делении на 6/
s/делящаяся на c/дающая c в остатке при делении на 6/
>>875307
Как насчёт взять все, а потом при необходимости выбросить наименьшее, не делящееся на 6?
Как насчёт взять все, а потом при необходимости выбросить наименьшее, не делящееся на 6?
>>875366
Я бы на твоём месте ещё подумал, задача-то простая. Но если совсем зашёл в тупик, то вот
http://lpaste.net/339079
Я бы на твоём месте ещё подумал, задача-то простая. Но если совсем зашёл в тупик, то вот
http://lpaste.net/339079
Ответы875448
>>875413
Ввёл тебе за щёку.
Ввёл тебе за щёку.
>>875369
Я понял задачу так, что обязательно использовать ровно r+1 запрос.
В таком случае возникает проблема, что на каком-то шаге мы можем обнаружить расхождение, но мы обязаны сделать остальные шаги, и непонятно как передать на эти шаги информацию о том, что различия уже найдены.
Я понял задачу так, что обязательно использовать ровно r+1 запрос.
В таком случае возникает проблема, что на каком-то шаге мы можем обнаружить расхождение, но мы обязаны сделать остальные шаги, и непонятно как передать на эти шаги информацию о том, что различия уже найдены.
Ответы875451
>>875448
Нет, ты неправильно понял задачу. Обычно такие странные условия обговариваются. Например, было бы написано "сделав ровно r+1 запрос"
Нет, ты неправильно понял задачу. Обычно такие странные условия обговариваются. Например, было бы написано "сделав ровно r+1 запрос"
Ответы875633
193 Кб, 1280x1707
>>875451
Думаю ты прав, держи няшку.
Думаю ты прав, держи няшку.
Может тут есть кто-нибудь, кто тоже участвует во всероссийской олимпиаде для 11 классов? Сейчас пробный тур проходит как раз.
И еще может кто-нибуд в технокубке участвовал? Какого уровня там задачи? Там вообще ебанутые какие-то правила с этими взломами, не знаю осилю ли я там хороший результат показать.
И еще может кто-нибуд в технокубке участвовал? Какого уровня там задачи? Там вообще ебанутые какие-то правила с этими взломами, не знаю осилю ли я там хороший результат показать.
Ответы876086
>>875793
Ну, участвовал в твоем технокубке. Из-за того, что не в том порядке стал решать задачи, занял не 70-какое-то, а 150 с хуем место. Не понравилось
Ну, участвовал в твоем технокубке. Из-за того, что не в том порядке стал решать задачи, занял не 70-какое-то, а 150 с хуем место. Не понравилось
147 Кб, 917x750
Ебать, как такое делать? Пока что думаю запилить граф и перебирать по нему все варианты, но это же наверняка будет слишком медленно.
Ответы877675
>>877609
Хули тут думать-то, жадный алгоритм же.
Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i.
Хули тут думать-то, жадный алгоритм же.
Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i.
>>877722
Ну а что ты хотел, я тогда только начал вкатываться в си и программирование вообще
Ну а что ты хотел, я тогда только начал вкатываться в си и программирование вообще
>>877675
А если таких нет, то ничего не назначать, а потом делать дополнительный проход, заполняя дни без назначений?
И как находить такие дни - поддерживать отсортированную по штрафу коллекцию, и в неё докидывать работы из заранее подготовленного списка работ, сгруппированных по дедлайну?
Мне кажется проще назначать день работе с наибольшим штрафом. Если есть свободные дни до дедлайна, то забираем последний. Иначе забираем последний из дней после дедлайна.
>среди работ с дедлайном >= i.
А если таких нет, то ничего не назначать, а потом делать дополнительный проход, заполняя дни без назначений?
И как находить такие дни - поддерживать отсортированную по штрафу коллекцию, и в неё докидывать работы из заранее подготовленного списка работ, сгруппированных по дедлайну?
Мне кажется проще назначать день работе с наибольшим штрафом. Если есть свободные дни до дедлайна, то забираем последний. Иначе забираем последний из дней после дедлайна.
Ответы878128
Какую теорию погуглить для олимпиадного программирования? Я просто совсем неадвно вкатился и пока что просто на логике всё делаю. Жадные алгоритмы, динамическое алгоритмы, что ещё?
Ответы877923
>>877910
Способы представления графов в памяти, DFS/BFS, алгоритм Дейкстры, комбинаторика на уровне итерации по всем перестановкам и сочетаниям, бинарный поиск, алгоритм Эвклида, решето Эратосфена, генерация пифагоровых троек, метод ветвей и границ.
На самом деле сам поймёшь что нужно когда будешь натыкатьсся на трудные задачи.
Способы представления графов в памяти, DFS/BFS, алгоритм Дейкстры, комбинаторика на уровне итерации по всем перестановкам и сочетаниям, бинарный поиск, алгоритм Эвклида, решето Эратосфена, генерация пифагоровых троек, метод ветвей и границ.
На самом деле сам поймёшь что нужно когда будешь натыкатьсся на трудные задачи.
Ответы878010
Как научиьься реализовывать алгоритмы? Смотрю в интернете всякие видео уроки по популярным алгоритмам, типа quicksort, но реализовать на языке который изучаю не могу. Сто делать?
>>877991
Как научиьься выступать в суде защитником в деле об ебле козы бабы Нюры? Смотрю в интернете всякие видео уроки по выступлениям-заседаниям, типа quicksort, но выступить в суде в котором выступаю не могу. Сто делать?
Как научиьься выступать в суде защитником в деле об ебле козы бабы Нюры? Смотрю в интернете всякие видео уроки по выступлениям-заседаниям, типа quicksort, но выступить в суде в котором выступаю не могу. Сто делать?
>>877991
Находишь в интернете реализацию ксорта на твоем языке. Понимаешь. Потом переписываешь, можно подглядывать. Как переписал, закрываешь. На следующий день без подглядывания пиши.
Находишь в интернете реализацию ксорта на твоем языке. Понимаешь. Потом переписываешь, можно подглядывать. Как переписал, закрываешь. На следующий день без подглядывания пиши.
Ответы878045
>>877923
Спасибо.
Спасибо.
>>877991
Задвай себе вопрос "а что надо делать" и делай. Потом "а что теперь?" и так далее. После каждого такого шага чекай всё ли правильно работает.
Задвай себе вопрос "а что надо делать" и делай. Потом "а что теперь?" и так далее. После каждого такого шага чекай всё ли правильно работает.
Ответы878045
>>877675
И какая у этого алгоритмическая сложность? По-моему, не меньше O(N^2). Многовато.
> Идёшь с конца, в i-й день выполняешь работу с самым большим штрафом среди работ с дедлайном >= i.
И какая у этого алгоритмическая сложность? По-моему, не меньше O(N^2). Многовато.
Ответы880775
>>879289
Про кучу не слышал?
Про кучу не слышал?
Продублирую тут, пожалуй.
Сап. Есть в треде алгоритмодрочеры?
Есть таблица связей в бд (postgres): юзер id - группа id.
Нужно выделить несколько секций юзеров (нужно, чтобы было максимум N юзеров в каждой такой секции), которые входят в группы "эксклюзивно".
Другими словами. Допустим N=1000. В секции #1 будет 10 групп, в которые входят только юзеры из этой секции, всего 980 юзеров в секции #1. В секции #2 будет 14 групп, в которые входят только юзеры из секции #2, всего 900 юзеров в этой секции. Всех остальных относим в последнюю секцию. Нужно найти такие вот секции, приблизительно.
Какой тут алгоритм применять?
Главное чтобы быстрее работало, какая-то точность разбития на секции (типа, чтобы максимально скомпоновать юзеров по N=1000 в секции) не нужна.
Пока вижу просто тупо ходить в цикле по группам (в порядке возрастания популярности групп, навеhное), собирать юзеров, пока не наберется 1000, после чего собирать следующую.
Сап. Есть в треде алгоритмодрочеры?
Есть таблица связей в бд (postgres): юзер id - группа id.
Нужно выделить несколько секций юзеров (нужно, чтобы было максимум N юзеров в каждой такой секции), которые входят в группы "эксклюзивно".
Другими словами. Допустим N=1000. В секции #1 будет 10 групп, в которые входят только юзеры из этой секции, всего 980 юзеров в секции #1. В секции #2 будет 14 групп, в которые входят только юзеры из секции #2, всего 900 юзеров в этой секции. Всех остальных относим в последнюю секцию. Нужно найти такие вот секции, приблизительно.
Какой тут алгоритм применять?
Главное чтобы быстрее работало, какая-то точность разбития на секции (типа, чтобы максимально скомпоновать юзеров по N=1000 в секции) не нужна.
Пока вижу просто тупо ходить в цикле по группам (в порядке возрастания популярности групп, навеhное), собирать юзеров, пока не наберется 1000, после чего собирать следующую.
Ответы881503
>>881288
Трудно что-то сказать не зная как распределены пользователи по группам и что значит "приблизительно" и "эксклюзивно".
Выбирай очередную группу рандомом пока не наберёшь достаточно, делай несколько подходов, выбирай лучший результат.
Трудно что-то сказать не зная как распределены пользователи по группам и что значит "приблизительно" и "эксклюзивно".
Выбирай очередную группу рандомом пока не наберёшь достаточно, делай несколько подходов, выбирай лучший результат.
>>881503
Как угодно, считай, это группы в вк.
Я имел, ввиду, что не хочу найти лучшее решение из возможных (где секции максимально укомплектованы - по 999, 998 юзеров, например, в каждой), а более быстрое (то есть, пусть там в каждой секции будет по 900-1000 юзеров, это ок).
Это я просто так назвал, не знаю как правильно. Смысл - в каждой секции должны быть группы, в которые входят только юзеры из этой секции, не пересекаясь с другими секциями.
Как я уже написал, группы - это как группы в вк. То есть, например, соберу секцию #1, где будет группа любителей хентая 500чел + группа любителей гуро 400чел (из них 100, например, входят в группу хентая) + группа любителей golang 10чел. В других секциях любителей хентая, гуро и golang быть не должно.
И т.д. Большие группы, типа мдк, где >1000чел, не входят в секции. Но их подписчики могут быть любителями хентая, гуро, golang.
>не зная как распределены пользователи по группам
Как угодно, считай, это группы в вк.
>"приблизительно"
Я имел, ввиду, что не хочу найти лучшее решение из возможных (где секции максимально укомплектованы - по 999, 998 юзеров, например, в каждой), а более быстрое (то есть, пусть там в каждой секции будет по 900-1000 юзеров, это ок).
>"эксклюзивно"
Это я просто так назвал, не знаю как правильно. Смысл - в каждой секции должны быть группы, в которые входят только юзеры из этой секции, не пересекаясь с другими секциями.
Как я уже написал, группы - это как группы в вк. То есть, например, соберу секцию #1, где будет группа любителей хентая 500чел + группа любителей гуро 400чел (из них 100, например, входят в группу хентая) + группа любителей golang 10чел. В других секциях любителей хентая, гуро и golang быть не должно.
И т.д. Большие группы, типа мдк, где >1000чел, не входят в секции. Но их подписчики могут быть любителями хентая, гуро, golang.
>>881518
Это строго обязательно? Это условие сильно усложняет задачу.
>В других секциях любителей хентая, гуро и golang быть не должно.
Это строго обязательно? Это условие сильно усложняет задачу.
Ответы881663
Сап. Я школьник, 10 класс. Алгоритмы знаю на уровне "quick sort, binary search, bfs, dfs, dijkstra". Такой вопрос - можно ли за год вкатиться в олимпиады так, чтобы получить хоть какие-то бонусы для поступления? И на что следует обратить внимание? Готов сидеть у книжек часами каждый день. Если что, пишу на плюсах.
>>792098 (OP)
Скажите, а есть возможность на каком-нибудь из этих ресурсах сдавать задания на питоне?
>codeforces.com
>acm.timus.ru
>informatics.mccme.ru
>acmp.ru
>TopCoder.com
>etc
Скажите, а есть возможность на каком-нибудь из этих ресурсах сдавать задания на питоне?
Ответы881581
>>881549
Думаю можно. Выясни какие олимпиады тебе подходят, посмотри задачи прошлых лет. Нарешивай подобные задачи и читай теорию.
Думаю можно. Выясни какие олимпиады тебе подходят, посмотри задачи прошлых лет. Нарешивай подобные задачи и читай теорию.
>>881574
Да
>>881549
Есть знакомые, которые из твоего положения и хуже брали себе потом диплом всероса, так что дрочи задачки. Посмотри на иоип, например
Да
>>881549
Есть знакомые, которые из твоего положения и хуже брали себе потом диплом всероса, так что дрочи задачки. Посмотри на иоип, например
Ответы881616
>>881616
На топкодере вроде нельзя. Но вообще не надо писать олимпиады на питоне
Ты сам не можешь посмотреть?
На топкодере вроде нельзя. Но вообще не надо писать олимпиады на питоне
Ты сам не можешь посмотреть?
>>881616
на всех, даже etc
на всех, даже etc
как самые популярные темы задач на codeforces? дп, жадные алгоритмы, графы, структуры данных...
что задрачивать, чтобы стать хотя бы синим?
что задрачивать, чтобы стать хотя бы синим?
Ответы881668
>>881665
На синего хватит простых графов, бинпоиска, качественного конструктива. Сложные алгоритмы начинаются после Ddiv2
На синего хватит простых графов, бинпоиска, качественного конструктива. Сложные алгоритмы начинаются после Ddiv2
Ответы881671
>>881668
спасибо
спасибо
>>881654
Спасибо
Спасибо
>>881768
Потому что рано или поздно ты столкнешься с тл. Мало где на олимпиадах гарантируют решабельность на питоне
Потому что рано или поздно ты столкнешься с тл. Мало где на олимпиадах гарантируют решабельность на питоне
>>881518
Ну что же вы, бэтманы?
Я думал, в треде есть бородатые гики, что пояснят по хардкору, какой мне алгоритм нужен.
> Как я уже написал, группы - это как группы в вк. То есть, например, соберу секцию #1, где будет группа любителей хентая 500чел + группа любителей гуро 400чел (из них 100, например, входят в группу хентая) + группа любителей golang 10чел. В других секциях любителей хентая, гуро и golang быть не должно.
> И т.д. Большие группы, типа мдк, где >1000чел, не входят в секции. Но их подписчики могут быть любителями хентая, гуро, golang.
Ну что же вы, бэтманы?
Я думал, в треде есть бородатые гики, что пояснят по хардкору, какой мне алгоритм нужен.
Ответы882783
>>882755
Сколько групп всего?
Если не больше нескольких тысяч, то можно представить их в виде графа, в котором две вершины соединены если в соотв. группах нет общих членов. Перебираешь в нём клики Броном-Кербошем, и когда находишь подходящую удаляешь её из графа. В принципе может и не обязательно хранить граф в явном виде, в конце концов проверить наличие дуги между группами можно глянув на пользователей.
Но лучше делай как я уже написал >>881503
Можешь ещё отранжировать группы по аутичности, то есть отношению количества пользователей группы к количеству других групп в которых они состоят (или суммарному количеству пользователей в которых они состоят). Начинать наполнение секции лучше с аутистов.
Вангую что результаты тебя огорчат из-за того что есть боты, вступающие в дохуярд групп.
Сколько групп всего?
Если не больше нескольких тысяч, то можно представить их в виде графа, в котором две вершины соединены если в соотв. группах нет общих членов. Перебираешь в нём клики Броном-Кербошем, и когда находишь подходящую удаляешь её из графа. В принципе может и не обязательно хранить граф в явном виде, в конце концов проверить наличие дуги между группами можно глянув на пользователей.
Но лучше делай как я уже написал >>881503
>Выбирай очередную группу рандомом пока не наберёшь достаточно, делай несколько подходов, выбирай лучший результат.
Можешь ещё отранжировать группы по аутичности, то есть отношению количества пользователей группы к количеству других групп в которых они состоят (или суммарному количеству пользователей в которых они состоят). Начинать наполнение секции лучше с аутистов.
Вангую что результаты тебя огорчат из-за того что есть боты, вступающие в дохуярд групп.
>>881549
Я вот вообще не пробовал олимпиадное программирование раньше, но опыта в пограммировании каких-то практических вещей и всякой хуйни у меня куча. И вот в этом году я неплохо так начал в него вкатываться. 11-класс
Я вот вообще не пробовал олимпиадное программирование раньше, но опыта в пограммировании каких-то практических вещей и всякой хуйни у меня куча. И вот в этом году я неплохо так начал в него вкатываться. 11-класс
Кто-то сказал Данилюку, что это не кодфорс, чтобы решать с конца?
Анончики, не нашел ваш тред на нулевой и поднимаю этот, вроде бы актуальный.
Интересует решение задания "743D - Хлоя и приятные подарки" на codefoces
Разбор здесь http://codeforces.com/blog/entry/49049 , но я в упор не понимаю, как его реализовать.
Кому не лень и кто шарит, можете разжевать идиоту.
Интересует решение задания "743D - Хлоя и приятные подарки" на codefoces
Разбор здесь http://codeforces.com/blog/entry/49049 , но я в упор не понимаю, как его реализовать.
Кому не лень и кто шарит, можете разжевать идиоту.
>>895409
бамп посту
бамп посту
Бампать последний пост, каеф
>>895409
Там же решение на С++. Да и рекурсивное решение тупое как с перестановками:
Вывести все перестановки N чисел.
Перестановка N чисел - это перестановка первого числа и последовательности N-1. И так повторять пока N не будет равно 2, а два элемента переставить может даже школьник.
>я в упор не понимаю, как его реализовать
Там же решение на С++. Да и рекурсивное решение тупое как с перестановками:
Вывести все перестановки N чисел.
Перестановка N чисел - это перестановка первого числа и последовательности N-1. И так повторять пока N не будет равно 2, а два элемента переставить может даже школьник.
Ответы895517
>>895494
На минуточку N до 2*10^5.
Вот если ты вообще не в теме, но нахуя лезть в каждую бочку затычкой?
>решение тупое
>Вывести все перестановки N чисел.
На минуточку N до 2*10^5.
Вот если ты вообще не в теме, но нахуя лезть в каждую бочку затычкой?
Ответы897955
Как лучше себя прокачивать? Мотивации изучать что то новое совсем нету. На codeforces голубенький.
Ответы897930
>>895517
На минуточку ты долбаеб, а первоначальная задача легко решается рекуррентно за n операций. Я же привел задачу намного сложнее, которая тоже легко решается похожим образом.
Толку в этих задачах все равно 0, а автора кода надо бить палкой по голове за такой код
На минуточку ты долбаеб, а первоначальная задача легко решается рекуррентно за n операций. Я же привел задачу намного сложнее, которая тоже легко решается похожим образом.
Толку в этих задачах все равно 0, а автора кода надо бить палкой по голове за такой код
Ответы905560
>>897953
Тогда у тебя дохуя мотивации. От халявного поступления в вуз и повышенной стипухи, до чемпионата мира в пендосии. Открыл книгу и начал читать, нахуй
Тогда у тебя дохуя мотивации. От халявного поступления в вуз и повышенной стипухи, до чемпионата мира в пендосии. Открыл книгу и начал читать, нахуй
анон, помоги решить задачу. https://puu.sh/sWIUR/cf666599d0.png
Ответы898775
>>898360
ну тут сразу понятно что вершины надо не удалять, а добавлять в обратном порядке.
дальше очевидный флойд уоршел
получается 500^3, норм тебе?
только смотри не объебись - в двух внутренних циклах надо итерироваться по всем вершинам, а не только по добавленным.
ну тут сразу понятно что вершины надо не удалять, а добавлять в обратном порядке.
дальше очевидный флойд уоршел
получается 500^3, норм тебе?
только смотри не объебись - в двух внутренних циклах надо итерироваться по всем вершинам, а не только по добавленным.
Ответы899601
не умирай
Ответы903374
>>903655
На что мне твой зуб?
На что мне твой зуб?
В чем секрет чуваков, которые на codeforces делают все задачи раунда за 2 ебаных часа? А?А?
>>903807
То есть секрет чуваков, которые делают это за час тебя не интересует?
То есть секрет чуваков, которые делают это за час тебя не интересует?
>>903807
Буду краток. знаешь, буквально на днях я был в Российской Академии
Наук, провёл беседу со многими учёными, в том числе молодыми, кстати,
очень грамотные ребята. Так вот мы обсудили, в частности и данную
проблему, поговорили о текущей экономической обстановке в стране; они
так же рассказали о своих планах на будущее.
Вкратце, ответ на твой вопрос такой: эти ребята довольно быстро решают задачи, что позволяет им придумать алгоритм и написать код для задач всего раунда всего за два часа.
Буду краток. знаешь, буквально на днях я был в Российской Академии
Наук, провёл беседу со многими учёными, в том числе молодыми, кстати,
очень грамотные ребята. Так вот мы обсудили, в частности и данную
проблему, поговорили о текущей экономической обстановке в стране; они
так же рассказали о своих планах на будущее.
Вкратце, ответ на твой вопрос такой: эти ребята довольно быстро решают задачи, что позволяет им придумать алгоритм и написать код для задач всего раунда всего за два часа.
> Покажите, что алгоритм, который содержит не больше некоторого по-
> постоянного количества вызовов процедуры с полиномиальным временем
> работы, сам работает полиномиальное время. Если же алгоритм делает
> полиномиальное число вызовов такой процедуры, то общее время работы
> может быть экспоненциальным.
Посоны, откуда здесь экспоненциальное время выполнения?
>>904151
Выглядит странно. Очевидно, что суперпозиция полиномов есть полином. Может, там процедура может сама себя дёргать или алгоритм?
Выглядит странно. Очевидно, что суперпозиция полиномов есть полином. Может, там процедура может сама себя дёргать или алгоритм?
>>903807
Секрет в том, что родились с более подходящей для решения подобных задач генетикой
Секрет в том, что родились с более подходящей для решения подобных задач генетикой
Ответы904546
>>905503
У меня вот прямо щас лежит открытая в туалете глава про NP, но ничего наводящего на мысль не нахожу. Подскажешь конкретнее?
У меня вот прямо щас лежит открытая в туалете глава про NP, но ничего наводящего на мысль не нахожу. Подскажешь конкретнее?
Ответы905527
>>905527
Спасибо. Только легче не стало.
Может я неправильно понимаю эту задачу? Ну подставили мы в x^10 значение x=n^20, получили n^200, экспонента никак не получается.
Спасибо. Только легче не стало.
Может я неправильно понимаю эту задачу? Ну подставили мы в x^10 значение x=n^20, получили n^200, экспонента никак не получается.
>>897955
Тут шизофазия, смотрите
Тут шизофазия, смотрите
>>792098 (OP)
Бля у третьего дедка волосы как солнце хех
Бля у третьего дедка волосы как солнце хех
Ответы906450
54 Кб, 1148x836
Сам код (естественно, Паскаль):
http://rgho.st/6smPy2ygw
http://rgho.st/6smPy2ygw
>>906492
Задача Эйлера в классическом виде же?
Задача Эйлера в классическом виде же?
>>906492
#3296 Поход (6-9)
Темы: [Динамическое программирование: два параметра]
Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2011, Задача D ]
#3296 Поход (6-9)
Темы: [Динамическое программирование: два параметра]
Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2011, Задача D ]
Ответы906581
>>906581
Тут не нужны никакие графы и поиски кратчайших путей.
Это задача для 6ого класса. Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу. Код на богоподобной Яве по ссылке.
http://ideone.com/34HGKf
Тут не нужны никакие графы и поиски кратчайших путей.
Это задача для 6ого класса. Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу. Код на богоподобной Яве по ссылке.
http://ideone.com/34HGKf
>>906612
Частный случай поиска кратчайшего пути, вариант реализации с бинарным графом.
>Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу
Частный случай поиска кратчайшего пути, вариант реализации с бинарным графом.
Ответы906643
>>906628
Так то да, но тут время О(n) и памяти O(1), а у Дейкстры? Впрочем можешь не отвечать. Просто покажи реализацию, лучше всего на фибоначчевой куче, тебе явно это раз плюнуть, делов на 5 минут. А мне интересно.
Так то да, но тут время О(n) и памяти O(1), а у Дейкстры? Впрочем можешь не отвечать. Просто покажи реализацию, лучше всего на фибоначчевой куче, тебе явно это раз плюнуть, делов на 5 минут. А мне интересно.
Ответы906857
>>906612
Так мой код тоже самое и делает, нет? Конечно, там есть дохуя костылей, но всё же.
>Нужно просто запоминать кратчайшее число переправ до текушей точки на левом и правом берегу
Так мой код тоже самое и делает, нет? Конечно, там есть дохуя костылей, но всё же.
Ответы906673
>>906661
Прости, но твой код написан так, что его даже читать не хочется. В нем нем ясной выраженной мысли. Зачем ты проверяешь следующий символ в строке? Зачем тебе переменная up? И где у тебя хранится минимум переправ до текущей точки (и правого и левого) берега реки?
Прости, но твой код написан так, что его даже читать не хочется. В нем нем ясной выраженной мысли. Зачем ты проверяешь следующий символ в строке? Зачем тебе переменная up? И где у тебя хранится минимум переправ до текущей точки (и правого и левого) берега реки?
Ответы906683
>>906673
Для логичности, если сверху слева, конечно, но по картинке как будто сверху(т.е переменная up=1, а если снизу справа, ага, то соответственно up=0) идут два подряд (этот символ и следующий -- LL) притока, то выгоднее будет переправиться вниз, где таких притоков нет. Если сверху идёт лишь один приток, а второй снизу (LR), то выгоднее будет переправиться дальше вправо, чем переправиться вниз, а потом снова вверх.
Собственно, в переменной p, которая и выводится в конце. Правда, там по-другому описано, и нет отдельно левого и правого берега.
Я неофит просто, в этом году едва в регионалку по всеросу не попал.
>Зачем ты проверяешь следующий символ в строке?
Для логичности, если сверху слева, конечно, но по картинке как будто сверху(т.е переменная up=1, а если снизу справа, ага, то соответственно up=0) идут два подряд (этот символ и следующий -- LL) притока, то выгоднее будет переправиться вниз, где таких притоков нет. Если сверху идёт лишь один приток, а второй снизу (LR), то выгоднее будет переправиться дальше вправо, чем переправиться вниз, а потом снова вверх.
>И где у тебя хранится минимум переправ до текущей точки (и правого и левого) берега реки?
Собственно, в переменной p, которая и выводится в конце. Правда, там по-другому описано, и нет отдельно левого и правого берега.
Я неофит просто, в этом году едва в регионалку по всеросу не попал.
Ответы906702
>>906702
Действительно, у меня при притоках по всем сторонам (B) он поворачивает, хотя это совсем не обязательно.
Спасибо, спустя ещё несколько костылей будут все сто баллов, а так пока что 60.
Действительно, у меня при притоках по всем сторонам (B) он поворачивает, хотя это совсем не обязательно.
Спасибо, спустя ещё несколько костылей будут все сто баллов, а так пока что 60.
Ответы906758
>>906723
Анончик, не делай так. Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед. Посмотри выше решение готовое. И просто разберись почему оно работает. В нем мы идем, как будто по обеим сторонам реки одновременно.
Анончик, не делай так. Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед. Посмотри выше решение готовое. И просто разберись почему оно работает. В нем мы идем, как будто по обеим сторонам реки одновременно.
Ответы906805
>>906758
Но почему? Извини, понять не могу.
Хотелось бы всё же допилить своё решение, а если совсем не выйдет -- разобраться в чужих.
>Сейчас ты с удивлением увидишь, что для нижнего берега тебе нужно будет смотреть уже на 2 символа вперед
Но почему? Извини, понять не могу.
>И просто разберись почему оно работает.
Хотелось бы всё же допилить своё решение, а если совсем не выйдет -- разобраться в чужих.
>>906643
Ну не на пять минут, но мне тоже интересно. Мои соображения:
- в каждой точке графа у нас есть два возможных пути
- выбирая каждый раз пусть с меньшим весом, вы в итоге получим кратчайший (в волновом алгоритме всегда обсчитываем только одну ветку)
- переход протоки на стороне, где сейчас игрок, стоит 1
- переход на другую сторону учитывается вместе с переходом протоки на другой стороне (то есть результирующий вес на этом шаге либо 0, либо 2)
Память не нужна, сложность O(n).
Ну не на пять минут, но мне тоже интересно. Мои соображения:
- в каждой точке графа у нас есть два возможных пути
- выбирая каждый раз пусть с меньшим весом, вы в итоге получим кратчайший (в волновом алгоритме всегда обсчитываем только одну ветку)
- переход протоки на стороне, где сейчас игрок, стоит 1
- переход на другую сторону учитывается вместе с переходом протоки на другой стороне (то есть результирующий вес на этом шаге либо 0, либо 2)
Память не нужна, сложность O(n).
>>906857
Хотя да, заняло минут 7-10.
Хотя да, заняло минут 7-10.
>>906857
Тут есть маленький нюанс, но пусть спрашивающий сам догадается. Я могу дать подсказку.
Тут есть маленький нюанс, но пусть спрашивающий сам догадается. Я могу дать подсказку.
>>906857
опечатка: 1 либо 2*
опечатка: 1 либо 2*
>>906857
Считать надо 2 шага, этот и следующий (как сумму), а при прочих равных выбирать правый берег.
Считать надо 2 шага, этот и следующий (как сумму), а при прочих равных выбирать правый берег.
>>906857
Код покажи.
Код покажи.
>>907423
Лул
Лул
Сап, анончики, какой набор скиллов нужно выучить/повторить для предстоящей областной?
мимо-школьник
мимо-школьник
Ответы908019
Хуй знает, где такое спрашивать, так что спрошу тут пожалуй, это лучше, чем ньюфаг-тред. Есть алгоритм Кнута-Морриса-Пратта. Можно ли им сделать поиск подстроки, если в заданной для поиска подстроке допустим символ, который бы допускал, что на его месте может быть любая другая подстрока?
Ответы908016
>>907948
Задача о ноп?
Задача о ноп?
Что почитать школьнику нужно больше примеров, чтобы научиться решать задачи на динамическое программирование? А как решать задачи на графы, про всякие j-е дороги между i-ми городами. Я учусь в 10 классе и недавно заинтересовался программированием, пытаюсь в задачи на Codeforces, но получается только А.
Может, уже поздно вкатываться, но хотелось бы уметь это для себя.
Может, уже поздно вкатываться, но хотелось бы уметь это для себя.
Ответы908049
>>908037
Вкатываться не поздно, читай Шеня, Окулова и архивы олимпиад (mccme.ru и прочее, что есть в шапке)
Вкатываться не поздно, читай Шеня, Окулова и архивы олимпиад (mccme.ru и прочее, что есть в шапке)
>>908019
Добра тебе
Добра тебе
Для всех, кто вкатывается в ОП на курсере очередной тысячный раз стартует курс по алгоритмам Седжвика.
https://www.coursera.org/learn/algorithms-part1
https://www.coursera.org/learn/java-data-structures-algorithms-2
Быстро проходишь оба курса.
Перестаешь быть зеленым на форсах.
https://www.coursera.org/learn/algorithms-part1
https://www.coursera.org/learn/java-data-structures-algorithms-2
Быстро проходишь оба курса.
Перестаешь быть зеленым на форсах.
Ответы914987
179 Кб, 1024x683
Ответы913248
Наконец то апнулся на форсах
Ответы913244
>>912857
молоток, какой теперь? как к этому шел?
молоток, какой теперь? как к этому шел?
>>913248
да они офигенные, это 2011 год в Орландо
да они офигенные, это 2011 год в Орландо
2362 Кб, 1920x1080
ОЛИМПИАДНОЕ ПРОГРАММИРОВАНИЕ
>>914987
Для форсов и ОП итмошный куср лучше, причем сильно лучше. Но у него выше уровень входа. В нем мало теории и много отличных задач.
Для форсов и ОП итмошный куср лучше, причем сильно лучше. Но у него выше уровень входа. В нем мало теории и много отличных задач.
>>915189
Сайты верстать не поможет. Так что можешь не париться.
Сайты верстать не поможет. Так что можешь не париться.
>>915488
Кстати, если не был зарегистрирован, то никак.
Есть список презентаций из учебных видео.
https://courses.edx.org/courses/course-v1:ITMOx+I2CPx+3T2016/bf78f3a948074b16ba7146b1be3b4850/
Список задач с разборами добрые люди дожны были выложить на гитхаб.
Кстати, если не был зарегистрирован, то никак.
Есть список презентаций из учебных видео.
https://courses.edx.org/courses/course-v1:ITMOx+I2CPx+3T2016/bf78f3a948074b16ba7146b1be3b4850/
Список задач с разборами добрые люди дожны были выложить на гитхаб.
Ответы918735
99 Кб, 930x748
13 Кб, 871x257
69 Кб, 869x668
40 Кб, 837x420
Помогите, я нихуя не понимаю. 1 пик условия, остальные объяснение.
на 3 пике:
Что это значит? То есть есть строка aabbbaaaaabbaa то в этот массив поместят(2,3) и (5,2)?
И дальше - почему надо найти такое чтобы это выполнялось?
на 3 пике:
>Сложим все пары (ki, li)длин таких блоков в массив.
Что это значит? То есть есть строка aabbbaaaaabbaa то в этот массив поместят(2,3) и (5,2)?
И дальше - почему надо найти такое чтобы это выполнялось?
>>915679
Сначала для пары (a,b) в массив поместят (2,5)(3,2).
Затем для пары (b,a) -> (3,2)(5,2)
>Что это значит? То есть есть строка aabbbaaaaabbaa то в этот массив поместят(2,3) и (5,2)?
Сначала для пары (a,b) в массив поместят (2,5)(3,2).
Затем для пары (b,a) -> (3,2)(5,2)
>>915679
>>915707
>>915708
Как это работает:
Пусть у нас есть строка abbbaabbaaab, рассмотрим для начала только пару (a,b)
Тогда странностью такой строки будет количество не повторяющихся странных подстрок вида {a}{b}. Для abbb - это 3. Для aabb - 4, для aaab - 3. Но при этом мы несколько раз посчитали одни и теже подстроки.
Вопрос, как посчитать только различные варианты?
Для этого представим ось координат с абсциссой колво 'a' и ординатой колво 'b'. И расположем на этой плоскости прямоугольники с одним углом в начале координат и вторым в нашем случае (3,1)(2,2)(1,3) почитаем площадь фигуры. Это и будет ответ без повторений. Теперь повторим все для пары ('b','a').
У тебя на третьей пикче алгоритм нахождения такой площади.
>>915707
>>915708
Как это работает:
Пусть у нас есть строка abbbaabbaaab, рассмотрим для начала только пару (a,b)
Тогда странностью такой строки будет количество не повторяющихся странных подстрок вида {a}{b}. Для abbb - это 3. Для aabb - 4, для aaab - 3. Но при этом мы несколько раз посчитали одни и теже подстроки.
Вопрос, как посчитать только различные варианты?
Для этого представим ось координат с абсциссой колво 'a' и ординатой колво 'b'. И расположем на этой плоскости прямоугольники с одним углом в начале координат и вторым в нашем случае (3,1)(2,2)(1,3) почитаем площадь фигуры. Это и будет ответ без повторений. Теперь повторим все для пары ('b','a').
У тебя на третьей пикче алгоритм нахождения такой площади.
Ответы915893
>>915712
Дошло, спасибо.
Дошло, спасибо.
Как лучше считать хэш? По модулю 2^64 - 1 или 10^9 + 1?
Первый больше, но зато второй простой.
И как лучше хэшировать множество (то есть порядок не важен)?
Первый больше, но зато второй простой.
И как лучше хэшировать множество (то есть порядок не важен)?
Ответы917407
Если имеются средние знания алгоритмов, на каком ресурсе советуете решать подряд задачи?
Ответы916547
Ох ебать я набухался, чувствую себя быдлом, ааааа, мимо готовлюсь к области, ахахахаха
Ответы916568
Пиздец
>>916483
Решай на ацмп
Решай на ацмп
>>916542
какой на форсах, сколько на тимусе?
какой на форсах, сколько на тимусе?
Посоветуйте, как вкатиться в алгоритмы и структуры данных с нуля школьнику?
Ответы916859
>>916859
Так я не для олимпиад хочу вкатиться, а просто, чтобы перестать писать велосипеды
Так я не для олимпиад хочу вкатиться, а просто, чтобы перестать писать велосипеды
>>915940
1) по модулю 2^32 - 1, это быстрее
2) любой ассоциативной операцией от хешэй элементов (я часто xor использую)
1) по модулю 2^32 - 1, это быстрее
2) любой ассоциативной операцией от хешэй элементов (я часто xor использую)
156 Кб, 880x878
Полный текст задачи на пике. Если своими словами, то у нас есть неизвестная последовательность нулей и единиц. И запросы на четность единиц в подпоследовательности с L элемента до R элемента. Вопрос, начиная с какого запроса последовательности удовлетворяющей всем запросам не существует?
Как решить используя DSU?
Как решить используя DSU?
Ответы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. Сумму проверяешь на чётность
Попробуй сделать так:
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
>>918001
Пункт 4. Не ясен. Почему для четного отрезка все внутренние точки добавляются в нечетное множество?
Вот на пикче есть объяснение с форсов, но я его тоже не понимаю.
Т.е. вот есть запрос l r odd. Это значит, что либо (1,l-1)=odd и (1,r)=odd либо (1,l-1)=even и (1,r)=even. Но что с этим делать не ясно.
Пункт 4. Не ясен. Почему для четного отрезка все внутренние точки добавляются в нечетное множество?
Вот на пикче есть объяснение с форсов, но я его тоже не понимаю.
Т.е. вот есть запрос l r odd. Это значит, что либо (1,l-1)=odd и (1,r)=odd либо (1,l-1)=even и (1,r)=even. Но что с этим делать не ясно.
Ответы928351
Олимпиудники, как вы в файлы ввод/вывод перенаправляете?
Парни, объясните тупому, что такое взлом задачи во время контеста на cf?
Ответы923411
>>923255
взлом решения мб?
кто-то посмотрел твой код, который прошёл претесты, увидел что он выдаст неправильный ответ на какие-то допустимые входные и типа запустил твоё решение на этих входных
взлом решения мб?
кто-то посмотрел твой код, который прошёл претесты, увидел что он выдаст неправильный ответ на какие-то допустимые входные и типа запустил твоё решение на этих входных
Ответы923464
>>923464
На главной странице контеста нажимаем замок напротив решенной задачи.
Переходим в раздел "комната", дабл-кликом по кол-ву очков открываем решение для просмотра.
Находим ошибку
Жмем кнопку взломать, пишем тест(грузим генератор)
????
профит
На главной странице контеста нажимаем замок напротив решенной задачи.
Переходим в раздел "комната", дабл-кликом по кол-ву очков открываем решение для просмотра.
Находим ошибку
Жмем кнопку взломать, пишем тест(грузим генератор)
????
профит
Ответы923822
>>923568
спасибо
спасибо
Как CTF начать тащить?
v
Поясните за вот эту задачу
http://codeforces.com/problemset/problem/7/C
Я ее решил через длинную арифметику: сначала нашел решение (x0, y0). Потом все решения имеют вид
x = x0 + (b/d) k
y = y0 - (a/d) k,
где d = gcd(a, b), k - целое.
Дальше я относительно k решаю систему неравенств
-5e18 <= x0 + (b/d) k <= 5e18
-5e18 <= y0 - (a/d) k <= 5e18.
Если хотя бы одно k подходит, я его беру и подставляю в формулы выше. Это и есть ответ. Посмотрел решения других людей - они тупо решают уравнение и все. У меня 2 вопроса:
1) почему не может быть такого, что решая это уравнение расширенным алгоритмом Евклида, мы получим какую-то точку, выходящую за ограничения, но при этом существует точка, которая нам подходит?
2) почему не может быть переполнения? насколько большими могут оказаться x и y, когда мы решаем линейное диофантово уравнение?
http://codeforces.com/problemset/problem/7/C
Я ее решил через длинную арифметику: сначала нашел решение (x0, y0). Потом все решения имеют вид
x = x0 + (b/d) k
y = y0 - (a/d) k,
где d = gcd(a, b), k - целое.
Дальше я относительно k решаю систему неравенств
-5e18 <= x0 + (b/d) k <= 5e18
-5e18 <= y0 - (a/d) k <= 5e18.
Если хотя бы одно k подходит, я его беру и подставляю в формулы выше. Это и есть ответ. Посмотрел решения других людей - они тупо решают уравнение и все. У меня 2 вопроса:
1) почему не может быть такого, что решая это уравнение расширенным алгоритмом Евклида, мы получим какую-то точку, выходящую за ограничения, но при этом существует точка, которая нам подходит?
2) почему не может быть переполнения? насколько большими могут оказаться x и y, когда мы решаем линейное диофантово уравнение?
Ответы927851
Блджад. Участовал в контесте на форсах (1400 мусор), решил только А и В. Остальные три были пиздец какой-то. В тренировках такая же хуйня, дальше В никогда не уходил. Причем я не понимаю - вроде основные алгоритмы знаю (да если меня разбудят в 4 утра и насильно посадят за комп, на изи напишу бинпоиск, сортировку за O(n*log(n)), бфс, беллмана-форда, дфс, дейкстру, поиск порядковой статистики, каркас минимальной длины итд). Задачи на динамику тоже решал, получается с шансом 40%, хардово спалить закономерность. Когда читаю разборы последних трех задач, охуеваю - как люди додумываются до ЭТИХ решений. Как вообще люди на олимпиадах побеждают? Я уже с этим тимусом проебался до 100 решенных задач, ацмп решал, читал Шеня.
Короче, как вообще люди умудряются искать правильное решение в задачах, где хуй поймешь, какой алгоритм нужен? Тупо нарешивать овердохуя с архивов? И всё?
Короче, как вообще люди умудряются искать правильное решение в задачах, где хуй поймешь, какой алгоритм нужен? Тупо нарешивать овердохуя с архивов? И всё?
>>927755
Большинство олимпиадников -- олимпиадники по математике тоже (хотя есть исключения), это сильно прокачивает смекалочку, то есть умение понять, как же найти ключ к этой задаче.
Большинство олимпиадников -- олимпиадники по математике тоже (хотя есть исключения), это сильно прокачивает смекалочку, то есть умение понять, как же найти ключ к этой задаче.
Ответы927794
>>927764
Никогда не увлекался олимпами по матану. Значит, нужно забить болт на форсы, ибо без скиллов с математических олимпиад никак не апнуться?
Никогда не увлекался олимпами по матану. Значит, нужно забить болт на форсы, ибо без скиллов с математических олимпиад никак не апнуться?
Ответы927823
>>927794
Нет, не обязательно. Просто они прокачивают скилл, которого тебе не хватает.
Попробуй решать много-много простых задач -- на бинпоиск, поиск в глубину и простенькую динамику (в первых трёх задача на этом вашем КФ только это и нужно). Меньшикова на информатикс, региональные этапы, задачки по темам разным.
Нет, не обязательно. Просто они прокачивают скилл, которого тебе не хватает.
Попробуй решать много-много простых задач -- на бинпоиск, поиск в глубину и простенькую динамику (в первых трёх задача на этом вашем КФ только это и нужно). Меньшикова на информатикс, региональные этапы, задачки по темам разным.
>>927755
Очень мало. Это сколько в сумме ты потратил на решение - 50 часов? Хз почему ты не побеждаешь на олимпиадах, когда целых 50 часов потратил. В доте-то, наверное, 1050 часов.
> Я уже с этим тимусом проебался до 100 решенных задач
Очень мало. Это сколько в сумме ты потратил на решение - 50 часов? Хз почему ты не побеждаешь на олимпиадах, когда целых 50 часов потратил. В доте-то, наверное, 1050 часов.
Ответы927879
>>927872
100500 часов в дотке и все равно в брозе, потому что тима не тянет =)
100500 часов в дотке и все равно в брозе, потому что тима не тянет =)
>>927866
Ну так если длинная арифметика нужна.
Ну так если длинная арифметика нужна.
>>927755
Лол, что за хуйня, если меня ночью разбудить, я нихуя не напишу. Мимо-2000-на-кф
Лол, что за хуйня, если меня ночью разбудить, я нихуя не напишу. Мимо-2000-на-кф
Ответы928351
>>927755
Нужен опыт именно в олимпиадных задачах, со временем начинаешь узнавать неочевидные использования того или иного алгоритма и решаешь.
В школе ходил на олимпиады по математике, там та же хуйня была, если видел несколько сотен задачек то почти всегда сразу знаешь куда копать.
Нужен опыт именно в олимпиадных задачах, со временем начинаешь узнавать неочевидные использования того или иного алгоритма и решаешь.
В школе ходил на олимпиады по математике, там та же хуйня была, если видел несколько сотен задачек то почти всегда сразу знаешь куда копать.
Каким образом можно надрочиться за 2 года, чтобы стать победителем на олимпиаде 1 уровня? Знания по математике хуевые, с программированием еще хуже, даже сортировку не могу написать.
>>929003
informatics.mccme.ru
Сидишь и решаешь. Вместо Доты. Тебе должно быть настолько же интересно.
Как прокачаешься, пишешь так же кодфорсы сможешь писать.
informatics.mccme.ru
Сидишь и решаешь. Вместо Доты. Тебе должно быть настолько же интересно.
Как прокачаешься, пишешь так же кодфорсы сможешь писать.
Помогите решить задачу про RSA
http://acm.timus.ru/problem.aspx?space=1&num=1141
Я прям не ебу, почему у меня WA
http://pastebin.com/Vg6Sj7Cf
Я просто вычисляю
d = eφ(φ(n)) - 1 (mod φ(n)),
m = cd (mod n).
Что вообще там может не работать?
http://acm.timus.ru/problem.aspx?space=1&num=1141
Я прям не ебу, почему у меня WA
http://pastebin.com/Vg6Sj7Cf
Я просто вычисляю
d = eφ(φ(n)) - 1 (mod φ(n)),
m = cd (mod n).
Что вообще там может не работать?
>>929248
Как там круды поживают?
Как там круды поживают?
>>929003
Pizda треду
Pizda треду
Как восстановить ответ в задаче о рюкзаке, используя O(N+L) памяти? (N предметов, L вместимость рюкзака)
Знаю аналогичный алгоритм в задаче о расстоянии Ливенштейна, но он какой-то сложный (хотя задача вроде проще).
Знаю аналогичный алгоритм в задаче о расстоянии Ливенштейна, но он какой-то сложный (хотя задача вроде проще).
>>932655
Проиграл со сложного алгоритма о расстоянии Левенштейна.
https://www.cs.colostate.edu/~cs575dl/Sp2015/Lectures/Knapsack.pdf
Проиграл со сложного алгоритма о расстоянии Левенштейна.
https://www.cs.colostate.edu/~cs575dl/Sp2015/Lectures/Knapsack.pdf
>>932655
Забавно, ты назвал Алгоритм Левештейна сложным, хотя это просто разделяй и властвуй. Обычно когда какой-нибудь алгоритм не до конца разбираешь, считаешь его сложным, хотя на самом деле ты просто не понял его идею.
Если бы ты понял как работает Левенштейн, ты бы сразу понял как можно сделать то же самое для рюкзака.
http://ideone.com/abUEBD
Забавно, ты назвал Алгоритм Левештейна сложным, хотя это просто разделяй и властвуй. Обычно когда какой-нибудь алгоритм не до конца разбираешь, считаешь его сложным, хотя на самом деле ты просто не понял его идею.
Если бы ты понял как работает Левенштейн, ты бы сразу понял как можно сделать то же самое для рюкзака.
http://ideone.com/abUEBD
Ответы934730
>>934821
Технически можно приебаться к копированию items при делении пополам - будет N*log(N) памяти, но так более читаемо. Понятно, что можно не копировать, а хранить [l, r]
Технически можно приебаться к копированию items при делении пополам - будет N*log(N) памяти, но так более читаемо. Понятно, что можно не копировать, а хранить [l, r]
Не тони.
В школе прогал с удовольствием и довольно много, но бессистемно и навыков, кроме непосредственного написания кода, не развил. Потому что долбоеб.
Как итог, в 11 классе в олимпиадки не смог, пришлось идти на физику. Сейчас учусь в приличном вузе мфти, но направление скорее связано с математикой и физикой, буду менять.
Так вот, летом у меня будет около двух свободных месяцев на то, что бы достичь в своем развитии в плане проганья хотя бы уровня хорошего школьного олимпиадника, с какого бока за это лучше взяться? Я так понимаю, сначала нужно освоить алгоритмы, был даже сайт где список из 80 штук, этого хватит для начала? Как распределить время между теорией и практикой?
Есть ли где-то видео-курсы? Так-то я могу ботать по 8 часов, но нужна программа, координация, что бы кто-то вел, по книжкам это тяжело. Ангельский intermediate, речь понимаю, но трачу на это слишком много сил, на постоянный просмотр меня не хватит.
Как итог, в 11 классе в олимпиадки не смог, пришлось идти на физику. Сейчас учусь в приличном вузе мфти, но направление скорее связано с математикой и физикой, буду менять.
Так вот, летом у меня будет около двух свободных месяцев на то, что бы достичь в своем развитии в плане проганья хотя бы уровня хорошего школьного олимпиадника, с какого бока за это лучше взяться? Я так понимаю, сначала нужно освоить алгоритмы, был даже сайт где список из 80 штук, этого хватит для начала? Как распределить время между теорией и практикой?
Есть ли где-то видео-курсы? Так-то я могу ботать по 8 часов, но нужна программа, координация, что бы кто-то вел, по книжкам это тяжело. Ангельский intermediate, речь понимаю, но трачу на это слишком много сил, на постоянный просмотр меня не хватит.
>>956844
Вебмакак сейчас очень много, поэтому лучше вкатываться в низкоуровневое программирование и embedded.
Вебмакак сейчас очень много, поэтому лучше вкатываться в низкоуровневое программирование и embedded.
>>956872
Embedded-макак сейчас очень много, поэтому лучше вкатываться в высокоуровневое программирование и веб.
Embedded-макак сейчас очень много, поэтому лучше вкатываться в высокоуровневое программирование и веб.
>>956893
Зачем?
Вкатиться в алгоритмы и структуры данных необходимо, но олимпиады не нужны.
>олимпиадное программирование после школы
Зачем?
Вкатиться в алгоритмы и структуры данных необходимо, но олимпиады не нужны.
Ответы956911
>>956896
Нравится формат, короткие вызовы на несколько часов. Хочется научиться быстрее решать задачи.
Если получится, по вузику можно будет ходить как на понтах, с замдекана за руку здороваться
Нравится формат, короткие вызовы на несколько часов. Хочется научиться быстрее решать задачи.
Если получится, по вузику можно будет ходить как на понтах, с замдекана за руку здороваться
Котятки, напоминаю что открыта регистрация в код джем.
>>956844
1) Одному тяжело будет, тренер нужен. Если ты в мфти, с этим 100% проблем не будет.
2) Решай текущие контесты на codeforces + архив на codeforces, там есть разборы задач и можно смотреть чужие решения.
Но вообще, ты какой-то аутист. Олимпиады нужны, чтобы поступить в вуз, а если ты уже поступил, то они нахуй не всрались. В вузе надо либо заниматься наукой (если дохуя умный), либо на работу устраиваться как можно быстрее, чтоб по окончанию вуза уже было много опыта.
1) Одному тяжело будет, тренер нужен. Если ты в мфти, с этим 100% проблем не будет.
2) Решай текущие контесты на codeforces + архив на codeforces, там есть разборы задач и можно смотреть чужие решения.
Но вообще, ты какой-то аутист. Олимпиады нужны, чтобы поступить в вуз, а если ты уже поступил, то они нахуй не всрались. В вузе надо либо заниматься наукой (если дохуя умный), либо на работу устраиваться как можно быстрее, чтоб по окончанию вуза уже было много опыта.
Ответы958018
>>957744
1. Искать тренера пока рано, как мне кажется. Никто не будет нянчить дауна без базовых алгоритмических знаний, разве что за большие деньги. Собственно, вопрос был про структурированный курс конкретно по спортивным алгоритмам, что бы направляли и объясняли фишки. В свое время начинал просто решать задачи, но сложилось впечатление что это довольно малоэффективный процесс.
Так со стороны для себя вижу несколько выгод:
1) Идея пачками макачить игрушки для айос на модных фреймворках, пусть даже за большие деньги, меня не очень прельщает.
А вот идея написания высокоэффективного кода кажется гораздо интереснее, поэтому спортивное программирование кажется мне актуальнее для себя, чем тот же технотрек.
2) Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании, поэтому получить этот навык будет так или иначе полезно. При этом лучше сейчас, чем чеез 6 лет, когда придется начинать работать и гнаться за рынком. Тем более, что учить прикладные технологии сейчас не имеет смысла.
1. Искать тренера пока рано, как мне кажется. Никто не будет нянчить дауна без базовых алгоритмических знаний, разве что за большие деньги. Собственно, вопрос был про структурированный курс конкретно по спортивным алгоритмам, что бы направляли и объясняли фишки. В свое время начинал просто решать задачи, но сложилось впечатление что это довольно малоэффективный процесс.
Так со стороны для себя вижу несколько выгод:
1) Идея пачками макачить игрушки для айос на модных фреймворках, пусть даже за большие деньги, меня не очень прельщает.
А вот идея написания высокоэффективного кода кажется гораздо интереснее, поэтому спортивное программирование кажется мне актуальнее для себя, чем тот же технотрек.
2) Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании, поэтому получить этот навык будет так или иначе полезно. При этом лучше сейчас, чем чеез 6 лет, когда придется начинать работать и гнаться за рынком. Тем более, что учить прикладные технологии сейчас не имеет смысла.
Ответы959229
>>958018
Блять, что значит нянчить? Ты просто ходишь на тренировки, где ты один или с командой таких же ньюфагов решаешь задачи, а потом идет разбор этих задач. После разбора можешь дорешивать задачи и задавать всякие вопросы. Фишка в том, что если ты решаешь один и не понимаешь, почему у тебя задача не принимается, ты можешь очень долго думать и в итоге все равно не додуматься. Намного лучше у кого-нибудь спросить.
Ты понимаешь, что все, что не наука - это макакинг? Да, есть более высококвалифицированные макаки. Вот я немного шарю в алгоритмах и математике, но макакой я от этого быть не перестаю, потому что я не могу создать что-то новое, чего не было до меня. Я могу хуйнуть нейросеть и распознавать изображения, но не я же придумал алгоритм backpropagation, это будет просто реализация чужой идеи. Ничуть не лучше, чем сайты на пхп хуярить. Если не хочешь заниматься макакингом - поступай в магистратуру, потом в аспиранутру и т д. Если ты тупой как я и не можешь в науку, лучше сразу задумайся о будущей работе и начинай дрочить все разделы cs, а не только алгоритмы. Прочитай все книги Таненбаума.
На большинстве вакансий не спрашивают динамическое программирование, теорию чисел, геометрию, графы и прочую хуету. Из алгоритмов спрашивают что-нибудь "на смекалочку" (типа найти подмассив с максимальной суммой за O(n)) + то, что реально полезно знать в работе: деревья (красно-черные, b-tree и т д), хэши, сортировки и т д. На олимпиадах ты никогда не будешь писать красно-черное дерево / свою сортировку / свою хэш-таблицу.
> 1. Искать тренера пока рано, как мне кажется. Никто не будет нянчить дауна без базовых алгоритмических знаний, разве что за большие деньги.
Блять, что значит нянчить? Ты просто ходишь на тренировки, где ты один или с командой таких же ньюфагов решаешь задачи, а потом идет разбор этих задач. После разбора можешь дорешивать задачи и задавать всякие вопросы. Фишка в том, что если ты решаешь один и не понимаешь, почему у тебя задача не принимается, ты можешь очень долго думать и в итоге все равно не додуматься. Намного лучше у кого-нибудь спросить.
> Идея макачить меня не прельщает.
Ты понимаешь, что все, что не наука - это макакинг? Да, есть более высококвалифицированные макаки. Вот я немного шарю в алгоритмах и математике, но макакой я от этого быть не перестаю, потому что я не могу создать что-то новое, чего не было до меня. Я могу хуйнуть нейросеть и распознавать изображения, но не я же придумал алгоритм backpropagation, это будет просто реализация чужой идеи. Ничуть не лучше, чем сайты на пхп хуярить. Если не хочешь заниматься макакингом - поступай в магистратуру, потом в аспиранутру и т д. Если ты тупой как я и не можешь в науку, лучше сразу задумайся о будущей работе и начинай дрочить все разделы cs, а не только алгоритмы. Прочитай все книги Таненбаума.
> Достаточно начитался бугуртов про схожие со спортивными задачки на собеседованиях в крутые компании
На большинстве вакансий не спрашивают динамическое программирование, теорию чисел, геометрию, графы и прочую хуету. Из алгоритмов спрашивают что-нибудь "на смекалочку" (типа найти подмассив с максимальной суммой за O(n)) + то, что реально полезно знать в работе: деревья (красно-черные, b-tree и т д), хэши, сортировки и т д. На олимпиадах ты никогда не будешь писать красно-черное дерево / свою сортировку / свою хэш-таблицу.
Ответы962769
Анон, помоги. Что-то не получается решить элементарнейшую задачу на тимусе (сложность 81) http://acm.timus.ru/problem.aspx?space=1&num=1106.
Мой код:
http://acm.timus.ru/forum/thread.aspx?id=36064&upd=636260865438522774
Моё решение заключается в том, чтобы с помощью BFS покрасить все вершины и записать в ответ те, которые имеют одинаковый цвет
Мой код:
http://acm.timus.ru/forum/thread.aspx?id=36064&upd=636260865438522774
Моё решение заключается в том, чтобы с помощью BFS покрасить все вершины и записать в ответ те, которые имеют одинаковый цвет
Аноны, есть какие-нибудь методы по решению таких задач, как эта: http://acm.timus.ru/problem.aspx?space=1&num=1502 ?
Я проебал на ней два часа, вывел какую-то ебанутую формулу, которая почему-то работает и получил AC. Вопрос - есть какие-нибудь статьи/книги, где рассказывается, как решать похожие задачи с нахождением формул?
Я проебал на ней два часа, вывел какую-то ебанутую формулу, которая почему-то работает и получил AC. Вопрос - есть какие-нибудь статьи/книги, где рассказывается, как решать похожие задачи с нахождением формул?
Накидайте плз задач на cf или тимусе на префикс- или z-функцию.
Ответы962676
>>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;
}
Ты че, поехавший?
#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
>>959229
Прости, братишка, но по работе скорее всего это не пригодится. Пригодится умение распаковать протобуф, запаковать, написать конфиг, итд. Никогда тебе на работе не придётся задуматься о чём-нибудь реально сложном. Лично я таких работ не встречал.
>то, что реально полезно знать в работе
> (красно-черные, b-tree и т д), хэши, сортировки
Прости, братишка, но по работе скорее всего это не пригодится. Пригодится умение распаковать протобуф, запаковать, написать конфиг, итд. Никогда тебе на работе не придётся задуматься о чём-нибудь реально сложном. Лично я таких работ не встречал.
9 Кб, 886x212
>>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 операций (если это не какие-то сложные операции с дробными числами).
Во-первых,
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 операций (если это не какие-то сложные операции с дробными числами).
>>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>.
Можно ли это сделать за вменяемое время? Как вообще натянуть подгруппу на перестановки в комплуктере?
Посоны, если кто-нибудь знает подходящую книжку, или пакет в каком-нибудь эре или петухоне, либо хоть что-нибудь способное помочь, напишите, пожалуйста.
Спрошу тут, ибо хуй знает, где еще спрашивать.
Есть массив множеств перестановок 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
>>962900
Маттред в /sci/, dxdy, math.stackexchange.com
Но для начала сформулируй вопрос понятней.
>Спрошу тут, ибо хуй знает, где еще спрашивать.
Маттред в /sci/, dxdy, math.stackexchange.com
Но для начала сформулируй вопрос понятней.
Ответы963216
>>963087
Пусть так.
Есть два множества перестановок A = {tau_1, ... tau_m} и B = {delta_1, ... delta_m}.
Узнать, равны ли подгруппы <A> и <B>.
>Но для начала сформулируй вопрос понятней.
Пусть так.
Есть два множества перестановок A = {tau_1, ... tau_m} и B = {delta_1, ... delta_m}.
Узнать, равны ли подгруппы <A> и <B>.
Ответы963217
>>963216
A, B подмножества группы перестановок S_n.
A, B подмножества группы перестановок S_n.
>>970469
Ещё суффдерево можно + дфс, но раз ты такое спрашиваешь, вряд ли ты его напишешь с первого раза.
Ещё суффдерево можно + дфс, но раз ты такое спрашиваешь, вряд ли ты его напишешь с первого раза.
Ответы980789
Можно ли на КФ как-то смотреть тесты, если соревнование уже прошло?
Ответы972158
>>972160
Лол, вот это я тебя обманул. Извини, плохая память. Так это, после сабмита тебе должно выдать все входы и выходы (если ты не в олимпиадном режиме решаешь)
Лол, вот это я тебя обманул. Извини, плохая память. Так это, после сабмита тебе должно выдать все входы и выходы (если ты не в олимпиадном режиме решаешь)
Как найти совершенное паросочетание минимального веса в двудольном графе?
Между долями есть всё рёбра, если это важно (наверно нет, потому что можно надобавлять ребёр с весом ∞).
http://informatics.mccme.ru/mod/statements/view.php?id=6555#1 - вот эта задача, короче
Между долями есть всё рёбра, если это важно (наверно нет, потому что можно надобавлять ребёр с весом ∞).
http://informatics.mccme.ru/mod/statements/view.php?id=6555#1 - вот эта задача, короче
Ответы980814
>>980814
Спасибо.
Спасибо.
А как делать неасимптотические оптимизации?
Я вот не знаю, разве что очевидные вещи типа:
1) Вот этого заклинания.
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
2) Сделать один ресайз вместо множества пушбэков в векторе. (а кстати, быстрее ли вообще заменить векторы статическими массивами?)
3) Отсечения в переборе писать. Всяких брейков понаставить.
Вот. Вообще компилятор очень умный и всякие штуки сам оптимизирует, да? Типа
for (int i = 0; i < m n; ++i) {...};
Он тут не будет скорее всего умножать m на n много раз, а сделает типа
int mn = m n;
for (int i = 0; i < mn; ++i) {...};
(в теле цикла, понятно, эти переменные не трогают)
Я вот не знаю, разве что очевидные вещи типа:
1) Вот этого заклинания.
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
2) Сделать один ресайз вместо множества пушбэков в векторе. (а кстати, быстрее ли вообще заменить векторы статическими массивами?)
3) Отсечения в переборе писать. Всяких брейков понаставить.
Вот. Вообще компилятор очень умный и всякие штуки сам оптимизирует, да? Типа
for (int i = 0; i < m n; ++i) {...};
Он тут не будет скорее всего умножать m на n много раз, а сделает типа
int mn = m n;
for (int i = 0; i < mn; ++i) {...};
(в теле цикла, понятно, эти переменные не трогают)
>>982275
for (int i = 0, to = m n; i < to; ++i) ...
Вместо new Node использовать deque.push_back() && return &deque.back()
Но обычно этим не заморачиваются и делают такие тест кейсы, чтобы твой перебор не влез даже с байтоебскими оптимизациями (ну это в нормальных контекстах)
for (int i = 0, to = m n; i < to; ++i) ...
Вместо new Node использовать deque.push_back() && return &deque.back()
Но обычно этим не заморачиваются и делают такие тест кейсы, чтобы твой перебор не влез даже с байтоебскими оптимизациями (ну это в нормальных контекстах)
>>982275
Да. Эта оптимизация называется hoisting.
> Он тут не будет скорее всего умножать m на n много раз, а сделает типа
> int mn = m n;
Да. Эта оптимизация называется hoisting.
>>982275
В идеале надо читать книги по архитектуре компьютеров и по компиляторам, но на контестах почти всегда можно обойтись без этих знаний. Иногда выстреливает, у меня было несколько примеров.
Например, была задача про дерево с N = 400000. Я подумал, что N какое-то большое и зачем авторы так сделали. Понял, что стэк может переполниться и сделал обход дерева не через рекурсию, а помещая номера вершин в очередь.
В другой раз я решал какую-то задачу через linked list и там были запросы, в результате которых могла создаться новая нода в листе, а могла и не создаться. Запросов там было 100000, но задача не прошла. До сих пор не уверен в чем дело, но видимо в том, что динамическое выделение памяти занимает много времени. Вот если бы компилятор видел, что я подряд в цикле выделяю, он бы соптимизировал и сразу выделил сколько нужно, а там были запросы. Потом я понял, что затупил, и что можно заменить linked list на deque, и задача прошла, потому что deque устроена как массив, который при необходимости увеличивается во сколько-то раз (в 2, кажется), соответственно, делается всего log N запросов на выделение нового участка памяти.
Еще была ситуация, что я решил писать код через лямбды, а компилятор какую-то лямбду скомпилировал во что-то хуевое, задача не проходила. Заменил на императивный вариант и прошла. С тех пор на контестах я все пишу в императивном стиле.
В идеале надо читать книги по архитектуре компьютеров и по компиляторам, но на контестах почти всегда можно обойтись без этих знаний. Иногда выстреливает, у меня было несколько примеров.
Например, была задача про дерево с N = 400000. Я подумал, что N какое-то большое и зачем авторы так сделали. Понял, что стэк может переполниться и сделал обход дерева не через рекурсию, а помещая номера вершин в очередь.
В другой раз я решал какую-то задачу через linked list и там были запросы, в результате которых могла создаться новая нода в листе, а могла и не создаться. Запросов там было 100000, но задача не прошла. До сих пор не уверен в чем дело, но видимо в том, что динамическое выделение памяти занимает много времени. Вот если бы компилятор видел, что я подряд в цикле выделяю, он бы соптимизировал и сразу выделил сколько нужно, а там были запросы. Потом я понял, что затупил, и что можно заменить linked list на deque, и задача прошла, потому что deque устроена как массив, который при необходимости увеличивается во сколько-то раз (в 2, кажется), соответственно, делается всего log N запросов на выделение нового участка памяти.
Еще была ситуация, что я решил писать код через лямбды, а компилятор какую-то лямбду скомпилировал во что-то хуевое, задача не проходила. Заменил на императивный вариант и прошла. С тех пор на контестах я все пишу в императивном стиле.
>>982598
Может имел место произвольный доступ к элементам списка?
>linked list
>Запросов там было 100000, но задача не прошла. До сих пор не уверен в чем дело
Может имел место произвольный доступ к элементам списка?
Ответы982798
>>982598
Вообще пушка.
Ты сам смотрел на ассемблерный код, или просто так ляпнул что-то от балды? Я думаю, что ты просто не знаешь С++ и пишешь чушь.
>компилятор какую-то лямбду скомпилировал во что-то хуевое
Вообще пушка.
Ты сам смотрел на ассемблерный код, или просто так ляпнул что-то от балды? Я думаю, что ты просто не знаешь С++ и пишешь чушь.
Ответы982798
>>982693
Зачем мне смотреть, если я и так знаю, что лямбды могут сконпелироваться в хуйню и не только в плюсах. Заменил лямбду на эквивалентный императивный вариант и зашло. Какой тут еще вывод можно сделать?
>>982673
Нет, там только в начале и в конце добавлялись элементы.
> Ты сам смотрел на ассемблерный код
Зачем мне смотреть, если я и так знаю, что лямбды могут сконпелироваться в хуйню и не только в плюсах. Заменил лямбду на эквивалентный императивный вариант и зашло. Какой тут еще вывод можно сделать?
>>982673
Нет, там только в начале и в конце добавлялись элементы.
Ответы982843
>>982798
Короче не слушайте этого шизика, он где-то как-то обжёгся на лямбдах (небось не отличает [=] от [&]), а обосновать или привести примеры не может.
Чтобы не стать такими как он всегда докапывайтесь до истины, если видите, что что-то не работает, а не "ща тут cout вставим чтобы глючить перестало"
>если я и так знаю
Короче не слушайте этого шизика, он где-то как-то обжёгся на лямбдах (небось не отличает [=] от [&]), а обосновать или привести примеры не может.
Чтобы не стать такими как он всегда докапывайтесь до истины, если видите, что что-то не работает, а не "ща тут cout вставим чтобы глючить перестало"
>>982368
Такие ссылки не инвалидируются при новых пушбэках? Или как-то можно указать, чтобы дэк на основе связного списка генерировался? Но тогда какая это оптимизация, если всё равно при каждом добавлении системный вызов.
> &deque.back()
Такие ссылки не инвалидируются при новых пушбэках? Или как-то можно указать, чтобы дэк на основе связного списка генерировался? Но тогда какая это оптимизация, если всё равно при каждом добавлении системный вызов.
Ответы983332
>>982368
Ну не скажи. Разница между O(n) и O(n log n) весьма призрачная, и оптимизированный логарифм может работать быстрее, чем линейное решение, особенно если у него константа пожирнее.
Изредка даже O(n^2) вместо O(n) может зайти, если тесты слабые, либо такое решение, что для него тест непросто придумать, особенно заранее, не зная решение.
Конечно, чаще проще решить по честному, но сдать задачу, не решая, тоже весело.
Ну не скажи. Разница между O(n) и O(n log n) весьма призрачная, и оптимизированный логарифм может работать быстрее, чем линейное решение, особенно если у него константа пожирнее.
Изредка даже O(n^2) вместо O(n) может зайти, если тесты слабые, либо такое решение, что для него тест непросто придумать, особенно заранее, не зная решение.
Конечно, чаще проще решить по честному, но сдать задачу, не решая, тоже весело.
>>983087
Ты вообще представляешь что такое deque в С++? Как он внутри устроен? Почитай cppreference прежде чем такие вопросы задавать.
Ты вообще представляешь что такое deque в С++? Как он внутри устроен? Почитай cppreference прежде чем такие вопросы задавать.
Эй, отвечающие в тред, расскажите, когда и как вы начинали упарывать олимпиадки, какой лвл, где учились/учитесь/работаете. Что читали с самого начала, на какие курсы ходили?
Ответы984956
>>984536
Ходил на курсы в академю ШАГ, но там скучно был и я вместо занятий ходил к твоей мамке заниматься любовью.
Ходил на курсы в академю ШАГ, но там скучно был и я вместо занятий ходил к твоей мамке заниматься любовью.
Тред утонул или удален.
Это копия, сохраненная 23 мая 2017 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Это копия, сохраненная 23 мая 2017 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.