Настало время перекатить и такой тред. Основные ресурсы с задачками:codeforces.com - Клевый проект, чуть ли не еженедельные контесты. Система писькомерства рейтинга уровня ELO с Короткевичем 4к+. Задачки своеобразные, пилятся комьюнити, мало общего с задачками стандартного ACM, что продиктовано форматом соревнований. Так же codeforces выбирают площадкой для множества престижных соревнований уровня VK Cup, в тренировки заливаются все крупные контесты оффлайн.acm.timus.ru - великолепный архив. Решишь 500 задач на тимусе - будешь гарантированно красным на кфеinformatics.mccme.ru - хорош для новичковДальше идут ресурсы, которые оп не юзал особенно по своему скудоумию:acmp.ru - ничего сказать пока не могуTopCoder.com - пендосский codeforces, регулярные контесты, открытые турниры и тому подобное e-olymp.com - не знаюF. A. Q.Что почитать?Грэхэм, Кнут, Паташник "Конкретная математика"Кормен "Алгоритмы. Построение и анализ"...Как вкатиться?Читай книжки сверху, и решай как можно большеШапка за пять минут, надеюсь треду жить, принимаются предложения по оформлению
Открою тред насущным вопросом. Есть задача, в которой мне надобно в отсортированном в порядке неубывания массиве найти подотрезок заданной длины и с заданной суммой. Причем, таких запросов может быть порядка 2x10^5, и элементов в массиве столько же. Я знаю, что можно написать дерево отрезков и для каждого запроса бегать по этому дереву и получать сумму за log, но это в целом дает ассимптотику m n logn, что неприемлемо для ограничений (2 секунды)
Какой-то сайт с олимпиадной теорией http://hecs.info/
Чем кодефорсес лучше хакерранка? На КФ ебаные РАСПИСАНИЯ, за это его не люблю.
>>706325>>706304 (OP)Да, про теорию я, кстати, забыл.http://hecs.info - поделка школьников - олимпиадников, попытка собрать все в одном местеhttp://e-maxx.ru - великолепный ресурс, кладезь понятнейших описаний алгоритмов и структур данныхhttp://neerc.ifmo.ru/wiki - описания более академичныhttp://wikipedia.org - как ни странно, алгоритмы в статьях на русском языке представлены очень и очень неплохоДостаточно много полезной информации можно получить из блогов на ресурсах из шапки. Информации не только по решению задач, но и по сопутствующим темам вроде стратегии на контесте и т.п.
>>706334Ну, есть массив 1 2 3 4 5Подотрезки длины 3:
>>7063371 2 32 3 43 4 5
>>706313Деревья не нужны. Сделай массив частичных сумм s = a[1] + a[2] + ... + aС помощью них вычислить сумму отрезка m..n можно как s[n] - s[m-1].Массив у тебя отсортирован, и это надо использовать. Благодаря упорядоченности сумма отрезка будет монотонно возрастать по мере сдвигания начала отрезка к концу массива. Похоже тут у нас работка для бинарного поиска.
Посоветуйте статьи по Trie.
>>706339
>>706339Ладно, я переусердствовал. Спасибо
>>706313Если точно задана длина отрезка и нужна сумма, то высчитываешь среднее (сумму делишь на длину отрезка). Находишь в массиве это число или ближайшее меньшее. Это число будет концом отрезка - проходишь к началу массива на нужное количество элементов и высчитываешь сумму (сам отрезок не нужно хранить - только сумму и индекс конца). Проверяешь сумму - если равна то все. Если меньше то сдвигаешь отрезок - увеличиваешь индекс конца, прибавляешь к сумме новый елемент и вычитаешь старый (тот что вылетел). Снова проверяешь сумму и если надо повторяешь. Если сумма стала больше искомой то отрезка нет. Правда сложность сложно определить, она зависит от скорости роста значений елементов массива.
>>706349Разве тут асимптотика не просто mlogn выходит? Бинпоиск на число запросов
>>706340https://habrahabr.ru/post/111874/
>>706353У тебя нет гарантии на то сколько тебе времени прийдется двигать отрезок. Можно (скорее всего) подобрать такие входные данные что бинарным поиском найдешь конец отрезка в самом начале массива и потом будешь двигать в самый конец, тоесть в худшем случае получается m n logn, но для этого значения в массиве должны почти не изменятся. А если значения более-менее возрастают то тогда да, получается m logn. Для худшего случая можно как-то модифицировать алгоритм, например двигать отрезок не сразу по одному элементу, а например, после первого найденого (бинарным поиском) елемента, начать от него перескакивать сразу на несколько десятком или сотен (в зависимости от размера) элементов пока не убедимся что дальше сумма больше - и тогда уже можно искать точнее сдвигая по одному элементу.
Кто в Гугл код жэм участвовать будет?
>>706332Бамп вопросу.
>>706332В смысле "расписания"? На хаккерранке соревнования тоже по расписанию. Есть задачи которые проссто можно решать - но на КФ тоже же (вроде) можно.
>>706627Да, на кфе перманентно доступен архив со ВСЕМИ задачами прошедших соревнований
>>706304 (OP)Стоит ли тратить на это время, если мне не нравится этим заниматься? Скажем, для того чтобы показывать работодателям и все такое?
>>706651Нет, это просто обычное хобби. Бывает, на собеседованиях что-то олимпиадное дают, но обычно самое простое. Работодателю даже более интересно будет посмотреть, как ты будешь пытаться решить, а если ты ему сходу алгоритм выдашь уже известный тебе по каким-то причинам, то все скучно
Заключительный этап всероса - это примерно какой уровень задач на CF (div1-2 A-E)?
>>706792Это тебе надо решать обычно весь div1
>>706596Я
>>706794У меня сосед был, с 7-го класса брал призера, а в 11-м победителя. Как-то писал КФ при мне, решил то ли 3 задачи, то ли 2. Может, конечно, несерьезно подошел.
>>706809На кфе немного своя специфика-таки. И времени меньше, и задачи менее идейные. Есть знакомый математик, который в девятом классе выиграл всерос по математике, решив там все задачи. По программированию он тоже на всерос ездит и берет там призерство за счет идейных задач. Я даже не уверен, напишет ли он сам Декартку или ДО
Что я делаю не так при вычислении медианы целочисленного потока онлайновым алгоритмом?https://www.hackerrank.com/challenges/find-median-1https://ideone.com/WKvtSb
Тут кто-нибудь умеет хорошо решать динамику?
Я ньюфаг, записался в ВУЗе на курсы, щас тренируют на acmp, говорят, что потом нужно на Тимус с Кодфорсами переходить. И у меня возник вопрос: какова сложность задач на олимпиадах (на том же acm) по сравнению с acmp? Если я решаю на acmp задачи сложности 30-40% это же все хуйня по сравнению с олимпиадами?
>>706872Да, хуйня.
Пацаны, дайте подсказку, с какой стороны подходить вообще.
>>706979Представь граф, в котором все команды - вершины, а рёбра соединяют команды, сыгравшие друг с другом хотя бы один матч.Теперь забудь про этот граф. Тебе понадобится другой - в котором ребра соединяют команды, НЕ игравшие друг с другом.В этом втором графе тебе надо найти связный подграф размера K.Пишешь Брона-Кербоша, с тем отличием, что тебе надо находить не максимальный связный подграф, а первый попавшийся размера K.
>>707003Эх, пока не мой уровень. Но попробую накостылить.
>>706809И где сейчас этот сосед, к чему пришел?
>>7070593 курс ФИВТ МФТИ, преподает в Мытищинской школе программистов, уже год вроде. 3-х учеников поднял до финалистов - победитель/призер/призер.Может уже и перебрался куда, связи не имею с ним.
>>706979Это всерос 2013?
>>707003Лол, и как твой Брон-Кербош в TL влезать будет?
>>707184Ну вообще я надеялся, что там до бектрекинга не дойдёт. Но ты прав, на это полагаться нельзя.Надо использовать тот факт, что у каждой вершины 2 ребра. Это значит, что граф целиком состоит из циклов.Надо найти все циклы, и из каждого убрать по одному элементу.
>>707198То есть не убрать по одному элементу, а брать через один.
>>707003Как тут вообще строить граф по стольким данным? 100000 матчей - это 50000 команд. По идее тут не пройдут алгоритмы хуже линии.Может какая хитрая маска.
>>707255>>707198
>>707259Кстати, может быть так, что пара команд играла друг с другом в обоих раундах.
>>707255Берёшь случайную вершину V1, произвольно выбираешь одно из её рёбер. Переходишь по этому ребру в V2.У V2 два ребра. По одному ты пришёл, а другое ведёт куда-то ещё. Переходишь по второму ребру и т.д.Рано или поздно ты вернёшься в V1. Это значит цикл замкнулся.
>>707263Частный случай - цикл длины 2. Но да, может поломать алгоритм, если ты не предусмотрел это.
>>707264Это ты к чему?
>>707269К >>707255
>>707270Как ты его хранить будешь, скажи для начала. Вектор векторов или 2д-массив булов? Размер инверсированного графа в любом случае будет 50000*50000=2500000000=2.5 гига. Я про это писал.
>>707272Про Брона-Кербоша идея неудачная, как правильно заметил >>707184Но не потому что проблема представить граф. Его на самом деле не надо хранить в явном виде. Достаточно хранить комплементарный граф>в котором все команды - вершины, а рёбра соединяют команды, сыгравшие друг с другом хотя бы один матчЭто будет просто другое представление графа в памяти. Все нужные операции можно делать и с таким представлением.
>>707274Блин, точняк. Тупо идти через один. С поправкой на не входящие в основной остов пары. Стало понятно, когда представил граф.
>>706886А какой сложности вообще задания на олимпиадах по той же шкале acmp? Сам определить не могу.
>>707375Варьируются. Обычно есть и та задача, которую должны решить все, и та, которую вероятнее всего не решит никто
>>706841else if (max_heap.size() > min_heap.size()) return max_heap.top();else return min_heap.top();из нижней части нужен максимальный элемент, а из верхней минимальный. А ты берёшь из обоих максимальный.На самом деле тут достаточно очереди для верхней половины списка и одного значения для нижней. Первые (n-2)/2 элементов не могут повлиять на результат, их не надо хранить.
>>707421Ну а средняя часть между этими 2 задачами? Вообще какой сложности я должен уметь решать, чтобы дойти до полуфинала acm.
>>707548http://codeforces.com/gymsТолько на первой странице полно четвертьфиналов московских
А у каких задача на acmp вообще подходящая сложность?мимо ещё ньюфаг
>>707447Ой, чёт показалось, что входной список отсортирован. Последнее предложение можно игнорировать.
Всесибирская в этом году - лютая параша. Ощущение, что просто пропихивали своих учеников в победители. На проверку принималось 3 языка, на компах не было нормальных сред разработки. Год подготовки коту под хвост.Намного приятнее было писать всеросс, организация на высоте, соревнование не предполагало знания какого-то конкретного ЯПа, интересная система начисления баллов. Хоть тут победителя получил.
>>708418>Хоть тут победителя получилПобедителя параши? Заключительный этап только начался.
>>708524тьфу ты. я говорил про краевой этап. на заключительный ехать денег нет.
>>708559Краевой - это хуйня. И она тебе никаких льгот не даст. Призер заключительного = поступление в любой вуз БВИ.
Попробую вбросить идею
В общем, мы тут решили конкурс-олимпиадку запилить на 4 недели.Пока только наброски идеи и правил: https://my.mixtape.moe/osxgjw.txtКритика (кроме сообщений о кривой кодировке) приветствуется.
>>708589Кодировка кривая
>>708589Иди покакай.
Алсо, кто не решил сокобан на тимусе, тот не спортивный программист.
>>708581и я о том же. поэтому и готовился к всесибу (собираюсь в НГУ). задачи к слову были куда проще, чем на всероссе, даже краевом. знания алгоритма рекурсивной заливки и флойда-уоршела хватило бы для решения всех задач, остальные "идейные". теперь только егэ сдавать на 100, и все в тот же нгу.
>>708596А че не в Москву
>>708602думал про МАИ, но жить и работать хочу в Новосибирске, например в ДубльГис. Сейчас вот думаю какой из двух вузов выбрать: НГУ или НГТУ
>>708418Как понять нет денег на всеросс ехать? У кого нет денег? Поступай в УрФУ вместо москвы, там очень крутой тренер асмщик Миша. В Москве ты не пробьешься в команды.
>>708671денег нет доехать до Москвы. я живу в Алтайском крае, тут билеты до Москвы стоят 2 месячные зарплаты. И я не планирую дальше заниматься acm, раньше рассматривал только как способ поступления в топовый вуз, например НГУ
>>708702Заключительный этап в Казане.
>>708702управление образования же должно оплачивать
Да и ЕГЭ выдрочить гораздно проще чем асм
>>708717Скорее всего, он не прошел.
>>708717Оплачивает регион, так что всегда находятся регионы, откуда за свои едут.
>>708717регион. а я живу в наверное, самом бедном регионе страны. тут на уличное освещение то денег не находится. в прошлом году>>708711стоимость билета одна. и в прошлом году в Инополис на роботехнику пришлось ехать через Москву (хз почему так)
бесполезная дрочка с тошнотворными задачкамимимо бывший олимпиадник
>>709634А теперь кто?
>>709634какой уровень у тебя был? к чему сейчас пришел?
>>709634полезная вещь в плане освоения некоторых тонкостей языков, навыков поиска багов, доказательства решений и знания алгоритмов но действительно дрочкапочти бывший олимпиадник
>>709701А в каком деле не дрочка?
>>709707Да ни в каком, ясное дело, но спортивное программирование уж слишком узкая область. Становится тесно и скучно.
Туристу хуйнули -600 рейтинга.
>>710403Дай ссылку на драму что-ле
>>710411На главной. Он, мол, каждый раз побеждал сам себя.
>>710443То есть каждый раз он бы получал все больше рейтинга за первое место?
>>710455Да. Дельта рейтинга зависит от рейтинга участников, которых ты опередил. Был баг, что сам участник всегда был в этом списке. И турист всегда фактически обыгрывал чела с 4000+ рейтинга.
Прикольно быть Геной
>>710478Все жду, когда он повесится, аки всякие вундеркинды
>>710478Прикольнее быть сыном олигарха.
>>710485Зато у него есть девушка, а у тебя нет))0)
Напоминаю, что меньше чем через сутки начинается квал Google Code Jam.
>>710693поможете решить? хочу стажировку с сша, но не умею решать ничего
>>710903Чёт в голосяндру с тебя
>>710903Лол, там чтобы чёртову футболку получить надо быть где-то на уровне призёра всероса. иди вон из треда
>>711215топ 500 надо быть
АЦМщики, среди вас крутые шахматисты?
>>711232Неткак ты связал в своей голове шахматы и олимпиадодрочку?
>>711293Потому что и то, и другое являются интеллектуальными занятиями. Нередко бывает, что олимпиадники-предметники играют в ЧГК, шахматы или еще что подобное.
>>711315Программист-олимпиадник, неплохо играю в шахматы, в ЧГК тащу с командой.Вещи эти не сильно связаны между собой. Тут скорее объединяет общий вопрос: любишь думать?
>>711318ЧГК - рилейтед хобби, потому что в обоих занятиях решает уровень абстракции мышления
>>711343А шахматы чем не подходят?
>>711348Шахматы - дроч схем, дебютов, эндшпилей, мидшпелей. Творчества там не осталось. На высоком уровне играют до ошибки соперника
>>711231Топ500 это в 3 раунд, футболка топ1000, по крайней мере, в том году так было.
>>711350>дроч схем, дебютов, эндшпилей, мидшпелей.А как же шахматы Фишера, не слышал что ли? Даже в нашей деревне в них в школе рубились, чтобы вывести на чистую воду соперника, который постоянно одной и той же тактики придерживался.
Началось!
Чёт долго тупил над первой. Наверное ночь сказывается.
Есть B. Тоже несложная. Билл Гейтс что-то такое мутил по молодости.
Решил C small.
Да и large засабмиттил.
Вроде въехал в D.
Заебись, можно спать.
>>711515>>711517>>711527>>711528>>711529Как же я вам вундеркиндам завидую.Какая цель у тебя, на работу к ним хочешь?
>>711573Бля, это квалификационный раунд. Чему ты там завидуешь?
>>711573Ну вот прикинь, готовится моё собеседование в Яндекс. Тут дверь распахивается, и вхожу я в футболке от Гугла.
>>711765Я и такое не могу решить. А вообще бывают кто стал неплох в асм своими силами без кружков, тренеров и универов?
>>711851Как ты представляешь участие в студенческой олимпиаде без универов?И что считается "неплох"?
>>711832ахуенно же. яб вдул
>>711832А в чём проблема? Не футболке самого яндекса же.
Такое чувство, что полдвача олимпиадники.
>>711905На кфе должно быть достаточно таких "вылезаторов"
>>711851Ты бы хоть форум codeforces почитал, там половина околокрасных это подпивасные самоучки. а другая половина - школьники, лол
Квалификация закончилась. Я так высоко в рейтинге, что мне вас отсюда почти не видно.
>>712453Очки протри, лол. Русских вверху рейтинга полно. D-large хоть правильно решил? Все остальное примитивно совсем.
Я не прошёл квал, начал изучать программирование 2 месяца назад
>>712475За счёт того что у меня все большие оказались решены правильно, а у некоторых нет я где-то на 20 мест поднялся при финализации результатов.
>>712453Квал никому не интересен, в 3 раунде веселее будет если ты туда пройдёшь, лол
Я тут один буду вайлдкард вк капа писать?
>>713007Ну пиздец.Вижу в прошедших контестах VK Cup 2016 и VK Cup 2016 - Round 1. При этом напротив "VK Cup 2016 - Уайлд-кард раунд 1" активна кнопка зарегистрироваться. Что это значит, я всё-таки могу участвовать?Лезу читать детали, раскапываю что требуемый возраст от 14 до 23, да и вообще я со своим пустым профилем иду лесом.Зачем прятать эту информацию так далеко? Почему нельзя убрать кнопку "зарегистрироваться" у тех, кто не проходит по условиям?I am dissapoint.Ещё и моих любимых языков нет в их списке. Ну нафиг этот codeforces.
>>713048что это за такие любимые языки?
>>713050VisualBasic, perl
>>713050Не скажу конкретно, я и так близок к деанону после >>712693Но почему нет Prolog, Erlang, Rust, F#, Clojure, Groovy, J, R наконец?
>>713007Я буду, 1 раунд проебал.
>>713085Я вообще первый раунд не писал. За меня отдувался сокомандник, но он вообще серый, лол. Почти, кстати, прошел
>>713065А ты крут, много зарабатываешь?
>>713103Не, у меня просто много свободного времени потому что я безработный.
>>713106Какой рейтинг у тебя на кфе? Давно занимаешься программированием?
>>713113На кфе пустой профиль пока.Занимался в универе не слишком активно, потом работал программером 3 года. Год назад контора закрылась. Надрачивался в основном последний год.
>>713065> я и так близок к деанонуДа всем похуй на тебя. Хоть скрин паспорта сюда вбрось.
Почему ещё не сделали официальную команду /pr/?
>>713048Дишка есть, надо попробовать.
>>713093Я это и имел в виду, проебал это мы просто забили. Так пока раунд нормально идёт.
Пиздец. Я так и не осилил этот ебучий J
>>713405А мы 5 штучек сделали в итоге.
>>713408ПоздравляюУ меня просто сокомандник даун. Вот вообще не помогал. Печально. Интересно, что и где пишут на этом языке
Кто может идей как решить задачу "reverse rmq"?т.е. вместо массива и следующих за ним запросов нам даются только запросы с ответами на них, и по этим данным должен дать подходящий вариант массива
>>713426Ну если навскидку, то идёшь по индексам массива, для каждого индекса проверяешь в какие ренджи он попадает, и пишешь наибольший из их максимумов.
>>713428*минимумов
>>713428и перед этим, для пущей ахуенности отсортить по левой границе. так?
>>713430запросы
>>713426scanline по запросам.
>>713430Я бы сделал два мапа, оба с ключом по индекса. Один - ренджи в которые ты входишь на этом индексе, другой - из которых выходишь.
>>713433я хз что такое сканлайныгугла на мусор выводит
>>713439Собственно, прямой перевод: сканирующая прямая. Короче, я имел в виду сортировку запросов, и дальше мы идём по индексу итогового ответа и поддерживаем текущие запросы, по ним строим число в этом месте или говорим, что ответа нет
>>713443нормас, спасибоплюс к рейтингу на кф тебе, бродяга
Помогите осознать простенькую динамику. Я-то сам умею только считать количество способов дойти куда-то в n-мерном пространстве за k шагов, а тут еще за каждый шаг дают разное число очков и его надо максимизировать. Если конкретнее, то есть полоска из клеток, у каждой клетки есть приз, и каждый из k ходов мы должны либо уйти на x в одну сторону, на y в другую или вообще на месте. Как тут переходы должны выглядеть?
>>713551Непонятно, напиши подробнее.
>>713738Есть полоса из клеток. У каждой клетки приз за то, что наступаешь в нее. Есть k шагов. Каждый ход идем в клетку, которая лежит в х клетот слева, или в y справа, либо вовсе остаемся на месте и снова получаем очки, будто мы только что пришли в эту клетку. Теперь надо максимизировать наш счет
>>713816Черт, только что подумал. Может, это тупой рекурсией зайдет? Вечером ограничения уточню
>>713816Вроде обычная двухмерная динамика по индексу клетки и по номеру хода, очередной ход пересчитывается через предыдущий. Здесь, почти как и в любой динамике, прокатит рекурсия с мемоизацией.
>>713848Рекурсия с мемоизацией кушает много памяти - почти NK вместо 2N.
>>713848Я понимаю, что это динамика, что двумерная. А вот как переход делать не догоняю
>>713853Ну да, кушает, ограничений-то мы всё равно не знаем. >>713856Как говорится, переход очевиден. Пусть прошло М шагов, мы рассматриваем клетку К. D - динамика, А - бонусы. Тогда мы к D[M+1][K-x] прибавляем D[M][K]+A[K-x], остальные два перехода по тому же принципу.
>>713875Не прибавляем, а обновляем значение, если новое больше старого, или если D[M+1][K-x] было не инициализировано.Да и на D[M][K] надо для начала посмотреть, инициализировано ли оно.
>>713878Ну да, обновляем. Смотреть никуда не надо, просто сначала нормально инициализировать динамику нужно и всё.
>>713884Нормально это как?
А на этом говне (J) ктонибудь кодит в реале? Или оно годится только для этих тестиков?
>>713888Я кодю. Пруф: $%(&^%^$%^&()((&^%^&()_)(&(*%$
>>713889Давай рассказывай как его правильно запускать чтобы я мозги не ебал.
>>713891Тащемта никакого секрета тут нет. Просто берёшь и запускаешь без задней мысли.
>>713897Ладно, попробую собрать новую 8 версию желания ебаться с косяком 7ого pkgbuild'а нету.
>>713885Ну или нулями, или -INF, по ситуации.
>>713907Нулями некорректно. После первого хода ты можешь достичь 3-х ячеек, а с нулями будет выглядеть будто ты оказался и в этих трёх, заработав сколько-то, и достиг всег остальных, заработав 0.-INF можно, но некрасиво.null самое то.
Оффтопик конечно, но почему автор компиля J забил на ворнинги?
>>713913На олимпиадах красота никого не интересует... Что нулями некорректно, я отлично понимаю, просто сказал два самых частых решения. Ещё иногда -1 используется, вместо null.
>>713920Ты серьёзно сел разбираться с этим говном?
Ребята, вы у телочек пользуетесь популярностью?
>>713976нет
>>713976Семь лет и 30 килограмм назад у меня были шансы.
>>713979>>713985Короткевич с Бардашевичем так то крутыми выглядят , особенно с наградами в руках, телки любят таких
>>714046Ну где они, а где мы... Другое дело, что я вижу много успешных ребят, вышедших из школьной олимпиадной тусовки.
>>713875>>713878Спасибо огромное, но не объясните ли вы, почему этот алгоритм не вырождается в обычную жадность? Разве мы не локально для каждого прыжка выбираем самый выгодный ход?
>>714242А ты условие объясни сначала. Мы из любой клетки можем начинать или как, ограничения какие, это всё важно.
>>714243
>>714246Интуитивно можно пояснить, что алгоритм не вырождается в жадность, потому что при количество_ходов->∞ самая выгодная стратегия это кратчайшим путём добраться до максимально выгодной клетки и стоять там. При уменьшении количества ходов сначала решение может перейти в поход до самой выгодной клетки по самому выгодному пути, при дальнейшем уменьшении уже вообще непонятно что будет, всё ближе и ближе к результатам жадного алгоритма. Надеюсь, стало чуть более понятно, я имею опыт только таких полуинтуитивных догадок, почему в одной задаче жадник, а в другой динамика.Закрой ты уже доки по J, в самом деле, и забудь о нём навсегда.
>>714252Я понимаю, почему эту задачу не решить жадностью, но не понимаю, почему работает такая динамика, где мы просто каждый ход выбираем самый выгодный следующийЧто не так с J?
>>714254О, это уже намного проще пояснить. Сначала, очевидный факт, что решение для N шагов зависит только от решения для N-1 шагов. Дальше ты доказываешь корректность перехода так: во-первых, такой переход не ухудшает ответ, во-вторых, лучше сделать нельзя, следовательно, он оптимальный.Это совсем кратко, но в общем это схема типичного доказательства перехода.он отвратителен, его синтаксис не для людей
>>714256Все, понял. Сотни нефти тебеА мне доставляет
>>714259Для хардкорной практики придумывания и доказательства динамики есть прекрасная задача "Казино": всерос 2005, финал, день 1, задача С; №11 на informatics.mccme.ru.
>>714261Ага, гляну. А еще такой вопрос. Мне для следующей итерации, какую клетку считать новой стартовой? Неужели просто ту, на которой я отхвачу максимум очков в предыдущей итерации?
>>714276Ты не понял сути. В ДП ты идёшь по всем путям одновременно, шаг за шагом.Стартовыми будут все клетки полученные на предыдущей итерации.
>>714295Да, я уже написал. Каждый раз загоняю в вектор возможные стартовые клетки и от них стартую. Ва на тесте 8 - это на что похоже? Переменные, где может быть переполнение, вроде уже проверил
>>714299Зачем ты их загоняешь куда-то?? У тебя есть массив динамики, сначала ты инициализируешь позиции перед первым ходом как надо, например, в нужные клетки ставишь 0, в остальные -INF. Тогда при пересчёте ты вообще не паришься, пути из неправильных клеток всё равно дадут отрицательные значения и в ответ не попадут. Только тогда надо учесть, что все состояния динамики на каждый ход надо тоже сначала поставить -INF.
>>714328Действительно. Получил AC. Надо, короче, нарешивать динамику, а то ни один нормальный контест без нее не обходится
Терпеть не могу геометрию. Если нам задан выпуклый многоугольник координатами его вершин вдоль обхода, то как найти самую длинную диагональ быстрее, чем за квадрат?
>>715014https://en.wikipedia.org/wiki/Rotating_calipers
>>715014Берем две(или три если точки трехмерные) оси (90 град одна относительно другой), проецируем на них все точки. Ищем на осях крайние точки - это будет потенциальные длинейшие диагонали.За какое время такой алгоритм? Линейное?
>>715114А если не будут?
>>715121Может и не будут.Наверно пару осей нужно взять из первой и средней грани предварительно проверив их на сонаправленость.
>>715126А не, средняя не нужна, перпендикуляр от первой норм будет.
>>715129Что ты называешь первой гранью?
>>715131У тебя же полигон точками задан?Первая грань - vect (p[0] - p[1])
>>715134Ну вот контрпример на оба случая. Если A и B это p[0] и p[1], то проверка ничем не будет отличаться от первого варианта что ты предложил.
>>715155Засада. Предлагаю вбить костылей и добавить еще две оси по 45 град. к первым. Инфа 146% этого точно должно хватить!Хотя может лучше из рандомной грани оси брать. Полик выпуклый - значит примерно на 1/4 граней приходится поворот на 90 град. Значит оптимально, брать перую, n*1/4 и их перпедикуляры.
>>715014Скорее всего если взять какую-то вершину, и потом по очереди смотреть длины диагоналей по очереди, то они будут сначала расти а потом падать (на выпуклом многоугольнике). Тоесть можно искать чем-то типа бинарного поиска.
>>715181Но искать придется для каждой вершины же.
>>715181
>>715197Опередил.
Короче, я уже ответил в >>715107Там асимптотика O(n). Зачем изобретать велосипед?
>>715200>Зачем изобретать велосипед?Интересно же. Потом когда кора одеревенеет, тогда и можно сразу в гугол.
>>715014Берём любую вершину, ищем для неё противоположную. Дальше, из очевидных соображений, если мы первую вершину сдвинем на 1 по часовой (то есть возьмём следующую вершину), то для этой вершины ответом будет являться либо уже найденная противоположная, либо эту противоположную надо будет так же сдвигать по часовой стрелке. Таким образом, если у нас есть список вершин в порядке обхода по часовой стрелке, то нахождение диагонали занимает линейное время, так как первая вершина пройдёт полный оборот, и противоположная ей суммарно пройдёт тоже ровно 1 оборот.Обход по часовой стрелке строится за O(NlogN) построением выпуклой оболочки, например, хотя может оказаться, что это пушка по воробьям и тут можно проще.
>>715209Насколько я понимаю, я описал что-то похожее на >>715107 , ну, чукча не читатель.
>>710693Напоминаю, что уже идёт раунд 1А Google Code Jam.
Не прошёл, лол.Решил первые две. Долго тупил над второй, и на третью не хватило времени.Хотя понял её быстрее чем вторую.Убираем тех, в кого нет входа, в оставшемся графе находим петли.Посадить в круг можно либо петлю в полном составе, либо пару + входящие в неё с каждой стороны цепочки.
Во второй довольно быстро понял, как найти диагональ, но после этого застрял.Мне казалось, что надо восстановить сетку полностью.Где-то час я ломал голову как это сделать. Пытался рекурсией - убираем первый столбец и первую строку, и решаем меньшую задачу. Но соснул на этом пути.
>>718197Тоже не прошёл, решил всё кроме Clarge, потом просто смотрел, как с 700 места медленно съезжаю вниз.
>>718195>>718356Приглашение на собеседование то получите?
>>718730Ну хватит уже.jpg
Что дают подобные занятия, кроме удовлетворения фаллометрии? Ни одна из этих задач на практике не пригодится. Хотя алгоритмы это нужная тема, если ты не вебмакака, но тут они слишком уж оторваны от жизниПост не вброс. Просто никогда не занимался олимпиадным погроммированием.
>>718829Занимаюсь олимпиадной прогой 5 лет, по сути, так и попал в программирование. Мне это помогло научиться программировать, искать баги, писать код нормально и понятно (потому что как раз на олимпиадках пишешь код настолько блевотно, что больше никогда так делать не хочется, и понимаешь, что никто это не поймёт даже через 5 минут). Алгоритмы дали понимание оптимизации программ, использование оптимальных структур, понимание вообще как это работает в глубине, желание сделать покрасивее и в то же время быстро рабочим. В целом, ящитаю несколько лет олимпиадной проги намного полезнее нескольких лет фронтенда, ну только если ты на фронтенде не собираешься сидеть всю жизнь.Если ты уже более-менее понимающий программист, то тебе это нахуй не упало, ну разве что немного алгоритмы подкачать, но как начало самое то для некоторых.
>>718843+++++
>>718843Вот проблема только лежит в переходе между началом и дальнейшими действиями.Вопрос ко всем тут: я сейчас заканчиваю десятый класс, балуюсь олимпиадками на среднем уровне, во всех рейтингах-таблицах уровня выше районного стабильно в серединке. Но я отдаю себе отчет в том, что мои некоторые скиллы в спортивом программировании нахуй не сдались в том, что называют промышленным программированием. И для меня сейчас остро стоит вопрос о переходе к такому виду работы. И если с олимпиадками все просто - задач пруд-пруди, то на чем мне практиковаться на начальном уровне в обычном программировании я ума не приложу. Наверное, я безыдейное говно. Вот как олимпиадники вообще существуют в ит-структуре?
>>718970Отлично существуют, промышленное программирование это надо прочитать пару кодстайлов и книгу банды четырёх, всё.
>>718974Допустим я познакомился с крестами только для олимпиад. Я знаю синтаксис, знаю стл. ООП мне нахуй не нужен был до этого. Теперь я хочу познать ооп, прочитал я пару глав книжки. Что-то понял. Но как мне это закрепить на практике? Один раз писал условный класс time, но это же, писец, скучно. Ничего интереснее не найти?
>>718977Что там в ООП учить-то. Если очень хочешь, то придумай себе проект какой-нибудь, например, обработка русского текста. Я на ООП никогда внимание не обращал, интересовался новыми фичами, а теперь мои кресты никому и не нужны, на работе почти всегда на питоне пишу, иногда шарп ещё.
>>718983А как ты на работу попал?
>>718990hh,ru
>>718995А скиллы для собеседования где взял. Писал проект какой-нибудь, например, обработку русского текста?
>>718997Нет, только олимпиадная прога, просто я сейчас в безопасности работаю.
Вы что, сдохли тут все?
>>724912Все на gcj уехали
>>725170Но финал же только через 3 месяца...
>>725170>>725339Привезите мне футболку, хочу ходить в ней летом по своему городу как король
Кароч тред официально мертворождённый, прошёл 2 раунд VK Cup и ни одного нового сообщения.
>>706979откуда задача?
>>725985Всерос 2013.
>Что почитать?И что, обязательно читать теорию от корки до корки, прежде чем лезть в программирование?
>>726265Нет, но вероятнее всего, что ты однажды напорешься на то, что твоих мозгов не хватит, чтобы придумать какую-то структура данных или алгоритм, но которые уже описаны умными людьми. Это полезно
>>726265Все не нужно, в олимпиадках используется подмножество алгоритмов, то что легко и быстро написать. Но что-то нужно посмотреть обязательно, ты не можешь в одиночку придумать все что придумало человечество за 60+ лет, кем бы ты там небыл.
Сколько задач нужно решить на тимусе, чтобы можно было уже пробовать себя на кодефорсес, чтобы рейтинг сразу в парашу не скатить? Вообще, стоит ли прорешивать тимус?
>>726314Тимус стоит прорешивать однозначно. Думаю, сотка задач позволит претендовать на эксперта
>>726316Я прорешал сотку снизу по сложности. Теперь я эксперт?
>>726317На всеросе не сильно соснёшь. А вот кодефорсес пока отложи.
>>726316>Тимус стоит прорешивать однозначноСпасибо, значит, буду прорешивать.>>726317>Я прорешал сотку снизу по сложностиДавно тренируешься?
>>726330>Давно тренируешься?Ну сотку это я переборщил. Где-то 60.Перед вузом пару месяцев поигрался. На самом деле, на этом уровне почти нет серьезных алгоритмов. В основном матеша и смекалка. Когда встретился с победителями/призерами всероса, потерял мотивацию продолжать.
>>726340Потерял по какой причине?
>>726346Недосягаемый уровень. У людей 5 лет форы во всяких СУНЦах и физмат-лицеях против моей гуманитарной гимназии.
>>726353А как же Ренат Муллаханов, вечная ему память, из обычной школы, на 1 курсе засел за тренировки, на 3 курсе взял золото финала ЧМ.
>>726400Талант, имхо
>>706304 (OP)> че почитатьe-maxx же, нет?
>>726340> В основном матеша и смекалка. Когда встретился с победителями/призерами всероса, потерял мотивацию продолжать. на всеросе можно взять диплом, не написав алгоритма сложнее бинпоиска, атвичяю. одноклассник так и сделал
>>726443>>726443>одноклассник так и сделалВ каком году?
>>726448в этом
>>726454Он сильно задрачивался?
>>726554ваще нет.
>>726400Ебать охуенный чувак был. Просто взял и опустил в парашу мамкиных корзиноидов, которых дрочили со школьного возраста.До сих пор бомблю со всяких "одаренных детей", у которых на проверке оказывается мамка/папка либо сорт оф ученые/преподы, либо бохатые и наняли корзине репетиторов.В то время как плебс продолжает в неведеньи кушать убогую школьную программу.
>>726690> а проверке оказывается мамка/папка либо сорт оф ученые/преподы, либо бохатые и наняли корзине репетиторов.такие одаренности далеко всё равно не идут. а если идут, то шли бы и без мамок-папок-репетиторов
>>726727>такие одаренности далеко всё равно не идутВерно.>а если идут, то шли бы и без мамок-папок-репетиторовНеверно.
>>726400>Ренат Муллахановhttps://www.fl.ru/users/mrk84/
>>726727>такие одаренности далеко всё равно не идутНа чугунной жопе как раз и идут. Думаешь, все спортивные программисты гении что ли? В основном они стали такими благодаря долгой задрочке, и под присмотром наставников.>то шли бы и без мамок-папок-репетиторовУвы, но такое бывает редко. "Маменькиных сынков" больше на порядок. Каким бы ты не был талантом, но без ресурсов и вовремя преподнесённых знаний ты пролетаешь.
>>726747> без ресурсов"ресурсы" и "мамка/папка либо сорт оф ученые/преподы, либо бохатые и наняли корзине репетиторов" -- разные вещи. некоторым хватает просто некоторой поддержки, а не последнего> Думаешь, все спортивные программисты гении что ли?топовые -- да. а нетоповые на то и нетоповые, сколько бы их мамки и преподы ни надрачивали, они не оч много могут>>726730> неверноимелось в виду "без таких мамок, о которых говорил ты", см. выше
Теперь это памяти Рената М. тред
>>726797Ну всё, ты прав, ты прав, осади уже.>сколько бы их мамки и преподы ни надрачивали, они не оч много могутВпрочем, надо ли? Поиграться для души/мозгов и задрачивать до посинения ради прокачки ЧСВ или пристройки своей жопы в говновуз - немного разные вещи.
>>726822А что с ним? На кфе так и не сказали, чому он откинулся
>>726889Что-то с давлением было.
>>726847> надо лиувы, в этом случае решают мамки. > задрачивать до посинения ради ради влажных фантазий мамки обычно. по крайней мере, не конченый человек, которому не очень импонирует спортивное программирование(да что угодно подобное) не будет им заниматься сам даже ради каких-то своих целей
>>726889Рак жопы.
>>726900Меня вот моя мамка-швея заставляла только ходить в церковь. И гулять в день как минимум 2 часа. Приходилось тупо стоять у подъезда, чтобы потом посидеть за компом, а то шнур забирала. А когда она уебывала на работу, со мной оставалась бабка, которая бухала до состояния говнины и валялась обоссанной в туалете.А теперь сравни с родителями Короткевича, программистами, которые обучали его с самого детства.
>>726906>гулять в день как минимум 2 часа. Приходилось тупо стоять у подъездаНу да, мамка виновата в том, что ты ебанат, не умеющий жить.
>>726914Увы, но в школьном возрасте подрастающий член общества просто не знает ещё, как жить, и как можно жить иначе. У него тупо нет опыта, знаний, кругозора. Всё зависит от окружения.Так что возвращайся в /b/, школьник.
>>726925верно говоришь
>>726443Я примерно так в 13 призёром стал, правда, вместо алгоритмов пришлось из сообразительности все соки выжимать.
>>726945так я и говорил, что алгоритмов чувак не очень писал
>>726906> Приходилось тупо стоять у подъездаты идиот чтоле? по крайней мере гулять много интереснее, чем стоять у подъезда. результат сравнения очевиден, но давайте сравним просто семью, в которой ребёнку хотя бы не мешают. тогда вероятность получить не корзинку с испорченной психикой и мировоззрением сильно меньше, соответственно действительно одарённый ребёнок в таком случае будет явно более успешен
Можно ли обойти связный неорграф без циклов, то есть просто дерево, но без перекрашивания вершин?
>>727305Обойти, конечно, рекурсивным дфсом
>>706979Понимаю, что поздно, только щас заметил тред.Задача дико тупая, не слушай тех, кто сыпет какими-то заумными словами. У тебя есть граф, вершины это команды, ребро есть если был матч. У тебя у каждой вершины степень ровно 2 по условию. Тогда граф разбивается на циклы (это вроде не очень сложное утверждение например, можно просто начать идти от какой-то вершины по ребрам, по одному ребру пришел, по другому вышел, так как вершин N, рано или поздно ты попадешь в какую-то вершину, где ты уже был. Это может быть только первая вершина с которой ты начал, иначе ты получил вершину степени 3 - ты в нее вошел, вышел, а сейчас еще раз пришел)Очевидно, что из каждого цикла длины k можно взять не более k / 2 команд. При этом, k / 2 можно взять - просто берешь через одну. А циклы это компоненты связности. Разбиваешь dfs-ом граф на компоненты связности, считаешь сумму (размер очередной компоненты / 2), если она хотя бы К - то все заебись
>>729739Да, деление везде целочисленное.Алсо, двукратный призер всероса ИТТ, сейчас занимаюсь АСМ-ом в вузике хоть и не столь активно дрочу, как некоторые, задавайте свои ответы
>>729740Какой вуз? Регион какой хотя бы?
>>729739Так ровно это же выше и говорили
>>729743Кек, проебался, увидел только пост с каким-то алгоритмом>>729742ДС2
Олимпиадники, подскажите, как учить язык, с чего начать, примерно подскажите по своему опыту?
>>729779Берешь, читаешь какую-нибудь книжку/курсы (проси совета в соответствующем треде), параллельно решай задачи из первого блока отсюда, чтобы освоить основы http://informatics.mccme.ru/Далеко копать в язык не надо (в смысле про всякие слова уровня ООП и прочее), если надо чисто для олимпиадокНа тимусе можешь еще порешать тупенькие задачки.
https://www.youtube.com/watch?v=gNRgvF9x12w&index=15&list=PLtb_PNVHdsV4qZgyqMFC6Tq2wsA0CybJB
>>730826Такой сильной антирекламы я давненько не видел. Если бы не возможность удаленки и миграцию, я бы давно уже дропнул эту хуйню нахуй, но я слишком тупой для сложных вещей и не умею наебывать на даллары.
>>731065Там ещё и жиды сплошныенормально защитились от тянок, сразу видно людей которые берегут свой пестик для единственной, моё увожение
>>730826БЛЯЯЯЯЯЯЯЯЯЯ ПХАХАХАХАХАХАХА ЕБАТЬ УНТЕРМЕНШИ ГДЕ ОНИ ИХ НАБРАЛИ?ЫТА ВОБЩЕ ЛЕГАЛЬНО???
>>731080Олимпиадоилита и байтослесари как они есть, не то что эти тупые хипсторы!
>>731083Это ж тупые жиды, они сами не кодють. Вот у них в подвале сидит Ванька-программист который ебашит все проекты в одно рыло по 12 часов в день без выходных за два доширака и упивается своей элитарностью и знанием алгоритмов.
>>731086лол
>>731101Вообще-то Денис очень талантливый, и многие задачки, где куча текста в виде сказки или фэнтези придумал именно он. Бронзовая медаль на ЧМ асм айсиписи
>>731115Да я то без претензий к ним, кроме разве что к художественной ценности их рекламы. Просто не мог пройти мимо и не подметить некоего сходства.
>>731101
>>730826Заметили, что достаточно много ребят и топа олимпиадников остались в рашке?
https://www.youtube.com/watch?v=27F46WPVJBsВторой раунд коде джема уже через 17 минут.
Почему они все такие всратые, пиздец?
Есть A
>>731153Это пока. Кто знает, что будет дальше.
ИДЕ повисла? Нет времени ждать, быстрее перезапустить! Я наверняка сохранил код, который писал последние полчаса!Дебил ёбаный.
>>731460Никогда еще иде не висла. Ты там кучу переполнял чтоле?
>>731468Ну, ИДЕ это громкое слово в данном случае. Я пишу прямо в Groovy console. Её легко повесить.
>>706325хехе, творение знакомых засветилось
Ваши ставочки на последние два часа Чемпионата Урала?
http://acm.timus.ru/monitor.aspx?id=384
>>732383Я болею за команду Ural FU : UF larU, но они не пробьются. Думаю, что на первое место выйдут Ural FU: Dandelion (Меркурьев, Сивухин, Данилюк).
>>732398Знаю из твоей команды Чаплыгина. Классный парень, но они слабоваты
>>732401Он из моего города, потому и болею за них.
>>732398Что-то Данделионы посасывают
>>732414Они по польской системе, будут сдавать кучу решений в самом конце.
>>732437Много насдавали?
>>732528не фартануло, но все равно крутые
Книги из ОП поста подходят свовсем нубам вроде меня? Если нет то посоветуйте плиз что-нибудь, желательно с малым количеством матана
>>732798А ты возьми и почитай
>>732798Язык программирования уже знаешь какой-нибудь?
>>733065Тут ещё и язык нужен?? О_о
>>706304 (OP)>Решишь 500 задач на тимусе - будешь гарантированно красным на кфеОткуда такая инфа пошла?
>>733065Изучаю С++
>>733265Как ты его изучаешь?
>>733337По книге Стенли Б. Липпмана, Жози Лажойе, Барбары Э. Му "Язык программирования C++. Базовый курс". До этого опытов с программированием почти не имел
>>733390Ты школьник?
>>733393первокурсник
>> Для проведения эксперимента надо выбрать из N имеющихся приборов только три. Для этого выполняют следующую операцию - если в группе приборов больше трех, то их нумеруют и выбирают одну из групп: с четными или нечетными номерами. Операцию повторяют до тех пор, пока в группе не останется три или менее приборов. Если их остается ровно три, то они и берутся для эксперимента.Требуется написать программу, которая подсчитает количество способов такого выбора приборов.Как сделать это за 1 секунду при 1 <= N <= 2147483647. Не могу уложиться в эти условия.
>>735642http://ideone.com/iAPf6W
Ребята помогите тупому с задачкой пожалуйста
>>735863^(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$
>>735933Спасибо, но мы на курсе не дошли до такого, надо как то через циклы if for while getline и функцию stoi
>>735933Буду благодарен если напишешь примерно, что у тебя в коде написано, чтобы я погуглил
>>735937Ты язык не написал.
>>735937Хуевый у тебя второй курсМимо-МФТИшник
>>735947>>735954Прохожу курс Густокашина по С++ на степике
>>735956А олимпиадное программирование тут причём? http://stackoverflow.com/a/10200328
>>735996Да потому что эта задачка вполне подходит, я на тимусе решал, там есть похожие по сути.
>>735996Густокашин сам крутой олимпиадник, вот и курсе своем дает задачки такие
>>735642Вот оптимизированный вариант: https://ideone.com/ROocYY
Вот это норм олимпиадка, не то что ваши днище-ацмыhttps://meduza.io/feature/2016/05/03/my-nachinaem-nashe-mochilovo
>>735940Нынешние студенты не знают про регулярки? Значит я за свое будущее спокоен.
>>737611А как в это дело вкатиться? Обязательно иметь ученую степень в иб? Вот как катываться в олимпиадки без сторонней помощи хотя бы понятно, а тут какая-то закрытая система
>>737615>а тут какая-то закрытая система
>>737612Ты дебил блять какие студенты, месяц назад начал проходить курс, до этого о проге не слышал даже
>>737611CTF ни чем не круче ACM
>>737619Блджад, enter случайно отправил.Короче, по моему скромному мнению, даже школьные олимпиадки это отчасти закрытая система. Потому что у ололомпиадников есть свои "клубы", есть тренера, короче мафия задротов, и типа всеобщая олимпиада сводится к эстафете "между своими".Бомбит например с того факта, что в обоссаном ацм победителем уже хуй сколько раз был летмо, хотя по мне говношарага говношарагой. Подебителей надрачивают тренерки, причем только из числа отборных задротов, а все остальные желающие сосут хуй.
>>737622>ни чемИди интегралы под водовку решай, второкур.
>>737623В итмо на тренировки могут приходить все желающие, всему научат. Я сам, как школьник, тренируюсь у Маврина, просто в начале учебного года кинул анкетку и все
>>737625>как школьникТы собираешься поступать по результатам олимпиадки?
>>737629Да
>>737623>ИТМОНе надо тут, два года назад СПбГУ затащил, например
>>739327Да много годных универов, ИТМО вывозит еще за счет того, что туда больше всего задротов олимпиадников съзжается, причем не только из Рашки. Самарский вуз сильный, УрФУ тоже, ПермГУ тоже золото брали
>>739630Ну да, только в тот же СПбАУ перевелся на первый курс со второго ИТМОшник, а еще перешел (в прошлом году) вот как раз победитель межнара из СПбГУ. Так что, возможно, это не надолго, хех
>>739631Лол, в ау вообще не особо приветствуют занятия асмом, потому что отнимает много времени и сил, а программа там и без того сильная.Мимо имею друзей и на кт, и в ау, и в спбгу, и в урфу и в пермгу
>>739632Ты уже закончил универ?
>>739633Еще не начинал
>>739632Ну да, но на финал команды вот проходят, пусть и выступают не очень. Да и на всякие сборы ездят себе спокойно, например
А тут у всех вас есть кружки, тренера, команды? Есть такие кто сам в одиночку с помощью интернета превозмогает?
>>740633На кфе видел посты таких. Всякие I_Love_Tanya_Romanova
>>740641>I_Love_Tanya_RomanovaПочитал его блог, какой- то монстр просто.
Ало, здравствуйте, это тред специальных олимпиад?
>>740698Да, вы пишите на Ruby?
>>740726Гхм... нет. Вы извините, но, может быть, я номером ошибся? Это точно тред специальных олимпиад, а не клуб гей-знакомств?
Ну что, кто на ЯндексАлгоритм зарегался? Как оцениваете шансы? Трудно ли попасть в топ-512?
>>744073Впервые услышал про него. Попробую, наверное.
Посмотрел разминочный раунд и охренел от сложности задач на 1.5 часа времени.
>>744329А чем ты на работе занимаешься?
>>744329а чем они там сложные?
>>740641Он из ЛНУ, чувак в олимпиадках с восьмого класса (сейчас он на шестом курсе). Потом в ЛНУ учился, тренер - Василь Білецький, он тоже брал золото ACM в 2008 году. Так что там не интернетом, а благодаря хорошей тусовке в том числе. Хотя решал он дофига, спорить не буду
>>744329Ты про яндекс.алгоритм? Последние тяжелые. А первые то вообще херня.
>>745228Ну вот шашматы, например. Там целую игру надо закодить с перебором вариантов. На все это дается 1:40 времени. Может, конечно, вы тут все чемпионы по скоростному набору кода, но мне нужно полдня чтобы такое закодить и отладить. Ты пробовал эту задачу делать? Сколько времени потратил?
>>745261Что там было? Сейчас только какую-то хуйню "A+B" выводит, не вижу нигде шашмат.
>>745268https://contest.yandex.ru/algorithm2016/contest/2497/problems/C/Поиск Яндекса отлично работает с блогами, так что во время поиска и последующего чтения блогов может найтись много экзотической информации. Например, описание игры шашматы.Игра шашматы происходит на стандартной доске 8 × 8: вертикали пронумерованы буквами от a до h, горизонтали — числами от 1 до 8, поле a1 — чёрное, каждое чёрное поле может граничить по стороне только с белыми, и наоборот.Игроки ходят по очереди. У белых одна фигура — шахматный конь, у чёрных — обычная шашка. Фигуры делают ходы в соответствии с правилами своих игр. А именно, шашка изначально располагается на чёрном поле и может передвигаться только по чёрным полям, уменьшая номер горизонтали на 1, номер же вертикали может как увеличиться на 1, так и уменьшиться; разумеется, выход за края доски запрещён. Конь ходит на одну клетку в некотором выбранном направлении (горизонтальном или вертикальном) и на две в перпендикулярном ему; при этом начальная и конечная клетки хода должны находиться на доске.Правила, по которым определяется победитель, таковы: Если на ходу белых конь может пойти на поле, занятое шашкой, конь берёт шашку, и белые выигрывают. Если на ходу чёрных шашка может пойти на поле, занятое конём, при этом следующее в том же диагональном направлении поле существует (то есть конь стоит не на краю доски), шашка берёт коня, и чёрные выигрывают. Если на ходу чёрных шашка может пойти на поле, занятое конём, но при этом конь стоит на краю доски, шашка не может сделать соответствующего хода. Если это был единственный возможный ход шашки, белые выигрывают. Если чёрные своим ходом приводят шашку на первую горизонталь, чёрные выигрывают.По заданной начальной позиции и цвету игрока, делающего ход первым, выясните, кто выиграет при правильной игре.
>>745154>Так что там не интернетом, а благодаря хорошей тусовке в том числеДвачую. Если не связи со всякими ололо-тренерами и прочей петушнёй, то хотя бы иметь товарища, который подскажет, что и как учить, какую литературу читать. Я в 8 классе в одиночку пытался решать задачи и обломался на них по полной, без соответствующих знаний было СЛОЖНА и страшно.
>>745271Я сделал первые две за 8 минут, и лёг спать, так как там только одну достаточно, чтобы пройти. для тренировок есть кодфорсес.Шашматы -- просто написать перебор. Не так долго и писать, ведь всего две фигуры. Наложить ограничения. Делать проверку на победу. запихать это всё в рекурсию. Посмотреть на дерево. Вывести ответ.
>>740659А что там такого-то?http://codeforces.com/blog/entry/7162Чувак не знает про передачу параметров по ссылке.http://codeforces.com/blog/entry/13207Чувак не знает про ненормализованные даблы и не в состоянии нагуглить.Остальное - приглашения на какие-то конкурсы.
https://mitpress.mit.edu/sites/default/files/Chapter%2026.pdf26-3Это CLRS.Скиньте пожалуйста пример решения этой или концептуально похожей задачи. Ну или на пальцах поясните, я обучаемый.
>>745271Ща попробую.
>>745533Ну вот что получилось. Прогнать тесты не могу потому что не зареган. На это ушло около 45 минут.https://ideone.com/Sra0zX
>>745343Это не то, что тебе нужно. Я тебе уже в ньюфаг треде намекал, что тебе надо собрать ранецhttps://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D0%B0%D0%BD%D1%86%D0%B5
>>745339>А что там такого-то?Ну он же пишет, что не было команды, что в одиночку превозмогал, а теперь он охуенно-красный.
>>745541Это вместе с отладкой, или ты просто написал и все?
Хотел послать твое решение, но там груви не принимается.
>>745541https://ideone.com/3P69JNe4 e3 white -> white winsнеправильно, должно быть блэкСобственно, о чем я и говорил. 45 минут ушло на написание этого, потом еще час на отладку, вот и закончилось время. А это только третья задача.
>>745761Написал и всё, проверил что запускается. Не имею возможности потестить.
>>745766Ну вообще у меня на диске пылится готовое решение для https://www.e-olymp.com/ru/problems/32Так что в контесте я бы взял его за основу и поменял только минимум - разницу между пешкой и шашкой. Получилось бы быстрее.И насчёт часа на отладку ты загнул. Так редко бывает с олимпиадными задачками при грамотном подходе к дебагу.
>>745567Во-первых, перестань меня преследовать.Во-вторых, Кормен лучше знает что нужно, а что ненужноВ-третьих, ты нихера не условия задачи.Собственно, с третьего пункта мне нужно было и начинать.
>>746065Ну давай, расскажи мне как в твоей жизни встала задача поиска максимального паросочетания в двудольном графе.
>>746185Приходит такой прафесар и говорит, кароч)) вот вам задача, кто не решит - тому пизда.
>>746185Альзо, если двудольный граф это bipartite graph, то ты опять пальцев в жопу.При всем уважении, не мучай себя.
Ну что тут есть олимпиадники с Пхукета?
>>747688Не удивлюсь, что Бардашевич двачует. Правда, явно не тут. Ближе к желтым колобкам
>>747692Лол, а что так?
>>749520Сначала на листочек выписывается строка. Игроки ходят по очереди и на каждом ходе можно стереть один символ из начала или конца строки. Побеждает игрок, перед ходом которого строка была палиндромом. Палиндромом называется строка, которая читается одинаково слева направо и справа налево.Определите, какой игрок победит при оптимальной стратегии обоих игроков.
>>749623Что за сложный мемес?
>>749623Так это тренер.
Ребяты. У меня есть 30 задач на тимусе, и целое лето впереди. Но я сам безвольное хуйло. Никто не хочет со мной в соревновательной, менторской или иной форме порешать это дело?
>>750634> соревновательнойчуваки с codeforces или topcoder очень хотят. если дрочишь на рейтинг, то добро пожаловать туда. мне более-менее помогало(это единственное место кроме олимпиадок, где я решал задачи). правда призером всероса так и не стал
>>751251Контесты проходят не достаточно часто, чтобы быть постоянной тренировкой
>>750634 у меня 25 задач на тимусе и я вообще не шарю, держи гайд от великого мастера
>>751251>правда призером всероса так и не сталЧем сейчас занимаешься? Куда поступил/будешь поступать?
>>751622Да, спасибо. Но это я уже раз четвертый читаю.
>>751629Знаешь Мишу?
>>751669Рубинчика? Увы, нет
>>750634А ты как занимаешься? Какой язык выучил?
>>751628> Чем сейчас занимаешься?страдаю хуйнёй, cf пишу, ну и соревнования типа codejam, rcc> Куда поступил/будешь поступать? видимо, в итмо(олимпиадки 1 уровня есть). хотелось бы в мгу ибо корочка пижже, но егэ сдать хорошо если на подтвержение в итмо смогу
>>751884Самый жесткий буст получил в школе. Нам преподавала сестра одного из чемпионов ACM в прошлом, менее успешная. Это было в 8 классе. Потом на кружке при ИТМО пересел на кресты, с тех пор только стал более уверенным
>>751496можно писать старые(виртуально), но лично я такой парашей не страдал никогда
>>751919М-м-максимум уныло. И слишком велик соблазн подсмотреть тесты, почитать разбор или чужое решение.
>>751924не было такого. ваще есть 3 случая:1) эта фигня для самолюбования а ты показываешь что ты слабый -> провал2) эта фигня просто чтобы порешать интересные таски -> нафиг читерить если цель -- решить?3) остальное -> нафиг ваще решать?
>>751935Попеременно испытываю все три предпосылки
>>751942ок, тогда как может возникнуть желание считерить? в любом случае оно нерационально
>>751949Наверное, акцептед доставляет больше чем весь процесс. Или это временное, или мне не место в олимпиадном движении
https://www.hackerrank.com/ Олимпиач, что скажешь про эту помйку?Для новичка порешать задачки пойдет?
>>751997т.е. для тебя AC полученный путем прочтения чужого решения -- заебись? если так, то, видимо, не место. едиственная ситуация, когда это нормально -- это если ты хочешь научиться хорошо реализовывать(тогда разбор надо читать без деталей, естесна)
Есть два прямоугольника, один размера a x b, другой размера c x d, напишите функцию, которая будет возвращать true если второй прямоугольник можно поместить внутри первого, иначе false.
Немножко пищи для ума страждущим:Есть массив уникальных дат месяца, отсортированный по возрастанию, на которые вам требуется купить билет t[0..30], где t = [1..30]. И есть следующие типы билетов:1) Билет на 1 день за 2 рубля;2) Билет на 7 дней за 7 рублей;3) Билет на 30 дней за 25 рублёй.Напишите программу, которая поможет пидорахе сэкономить на проезд в текущем стабильном положении в стране.Программа должна возвращать минимальную сумму в рублях, которая покрывает все поездки.Пример [1, 2, 4, 5, 7, 29, 30] = 11.
>>758150Что с этим столбом? Он вкусняшкой обмазан?
>>759132Жить захочешь и не так раскорячишься такие вкусняшки найдешь.
>>758150Очевидная динамика очевидна.
>>758150последовательность дней из:23~30 = 25 рублей22 = 23 рубля18~21 = 21 рубль15~17 = 14+(2,4,6) рублей11~14 = 14 рублей8~10 = 7+(2,4,6) рублей4~7 = 7 рублей1~3 = (2,4,6) рубля(-ей)Осталось выделить последовательности
>>760540Дэбил, зачем пытаешься жадник придумать. Много таких по весне оттаяло, в этой задаче думать вообще не надо, пишешь динамику и всё. Уметь отличать задачи на жадник от задач на динамику – крайне важный скилл.
>>760596Мсье, а как вы определили, что тут лучше динамическим программированием решить?
>>760609Определил из того, что задача стандартная и обычной линейной динамикой решается в два счёта.
>>760596>Уметь отличать задачи на жадник от задач на динамику – крайне важный скилл.Подкинь чтива на этот счёт.
>>760611реши
>>760616Решил
>>760617покеж
>>760615Нет никакого чтива, по крайней мере, я так и не нашёл. В Кормене есть про динамику, сам пытался в своё время понять по нему, но не вышло. Есть только стандартный принцип: если тебе кажется, что задача на жадник, но что-то не выходит, или слишком тяжело, то попробуй динамику. В случае этой задачи вообще беспроигрышный вариант, что жадник что динамика одну сложность имеют.
>>760618Нечего показывать, мне решение и так очевидно. Могу на пальцах: мы по каждому дню от него вперёд проставляем оптимальные варианты. Пусть сегодня 0 день, тогда мы смотрим, есть ли поездки в день 1. Если есть, то ставим на 1 день 2 рубля, иначе 0. Смотрим на поездки с 1 по 7, если есть, то ставим в 7 7 рублей, иначе 0. Дальше принцип понятен, думаю, когда я говорю "ставим", то имею в виду взятие минимума из нашего промежуточного варианта и того, который уже для этого дня есть. Изначально 0 дню ставим 0, остальным INF. По тесту из условия, на 0 дне в 7 ячейку проставится 7, дальше эта семёрка будет ползти до 28 дня, откуда два раза прибавится 2.
>>760627Чтобы решение было за линию, наличие поездок на промежутке проверяется с помощью префиксных сумм.
>>760619Под жадником это имеется ввиду?https://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC
>>760665Не, вроде вот этотhttps://otvet.mail.ru/question/3504695
>>760627Что-то как-то сложны ты на 2-х пальцах объясняешься.Вот что у меня вышло:https://github.com/arbitrary-dev/problem/blob/master/ticket/src/main/java/com/problem/ticket/Ticket.java
Сосаны, с каких лет лучше начинать готовиться к олимпиаде?
>>771543К жизни лучше подготовься, придурок.
>>771699Успокойся, сопи в две дырки ровно
>>771373Ок, просто мне больше нравится решать задачи более общими методами. Вот тут ты напрямую пользуешься тем, что один из билетов всего на 1 день, а другой сразу на 30, то есть на весь промежуток. Давай тогда дадим тебе промежуток в 100000 дней и 10 каких-нибудь случайных чисел как длительности билетов. Тогда ты придёшь ровно к тому же, что я и написал, иначе пальцы отвалятся случаи разбирать.
>>771373http://paste.ofcode.org/8ErWwmMWpEa9JJksEAbhHp вот, в общем, короткое и более мощное решение.
>>706304 (OP)Секунду, так писать на 1С?
>>771543после 6 класса
http://acm.timus.ru/problem.aspx?num=1406 хелпп
>>775884У тебя сколько задач решенных?
Как решать?
>>778407Просто.Найди первый элемент в отсортированном массиве, он на позиции k (нумерация с 0). Разберём два случая:1. k%2 == 0 -> проводим операцию на подотрезке от 1 до k -> k элемент стал k-1.2. k%2 == 1 -> проводим операцию на подотрезке от 0 до k -> k элемент стал k-1.Таким образом доводим первый элемент на его место (нулевое), дальше точно таким же образом обрабатываем суффиксы массива длиной n-1, n-2, ... , 2. Так как элементов всего 100, то задача решается втупую за куб. Если ограничения были бы чуть побольше, то элементы попарно в массиве можно свапать за логарифм двумя неявными декартовыми деревьями, с ними получится решение за N^2 * logN.
>>778520Пиздец перемудрил, это же тупо на сортировку пузырьком, типа такой хитровыебанной операцией просто завуалировали, что ты можешь свапать два соседних элемента. Пишешь обычный пузырёк, хотя за квадрат, хоть за куб, и всё.
>>778522В пузырьке не соседние свапаются.
>>778525Ты хоть раз пузырёк писал?
>>778525В общем, вот тебе википедос https://ru.wikipedia.org/wiki/Сортировка_пузырьком#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.80_.D1.80.D0.B0.D0.B1.D0.BE.D1.82.D1.8B_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0
>>778538>>778538Прикиньте я всегда вместо сортировке пузырьком писал сортировку выбором.
>>778544Вопрос в другом: зачем ты вообще писал сортировку?
>>778546Ну тогда был паскаль и мне сказали писать сортировку пузырьком.
>>778547Помню полулегенду, что Гена пишет qsort на паскале за 40 секунд.
>>778548Знаю девочку, которая знает Гену лично. Замеряли они это дело как-то. Там было что-то чуть больше двух минут, если мне память не изменяет
>>778549Зря ему про плюсы рассказали, мог бы в книгу рекордов Гинесса попасть.
>>775884https://ideone.com/Ut6YQW
>>778557как ты перешел на язык Груви и почему?
>>778998На работе заставили выучить. Там был джава проект, но нужно было и скрипты писать. Нравится что есть опциональная типизация.
>>7782120мне на пересдачу дают одну из них я сижу туплю.вру одна решена Козла пустили в Огородтак же есть пак решении на эти задачи?
>>778557это блять что такое?
Я конечно не знаю но олимпиадные задачки настолько запутанные, что мне их лень расшифровывать чтобы узнать что от меня хотят. В фрилансе очень четко известно что нужно писать. Нахуй эти олимпиадные задачи, лучше решать реальные.
>>779632Как это, обычно как раз наоборот, в задачке абсолютно чётко сказано, что от тебя хотят, с ограничениями и примерами. А вот что бывает в типичных ТЗ...
А если допустим 1000 таких задачек решить и на github выложить, то работу можно так найти?
>>779643Нуу, нет, но большой рейтинг на кодфорсах или топкодере это плюс на собеседовании во всякие яндексы.
>>779643>>779646Вот вакансия, где пишут про олимпиадки, например http://www.aimtech.com/vacancies/C++%20Developer/
>>710693Мне бы хоть три штуки из предыдущих google code jam решить, дак я и одну задачку не потяну.https://code.google.com/codejam/contest/32004/dashboardЕё за два часа решают, я за два часа даже не разберусь что нужно от меня.
>>779646Буду старые задачки google code jam решать и github выкладывать
>>779654Попробуй, конечно, но рейтинг намного более важен.
>>779656Фигасе из Россси только 255 человек в гугл код джам участвовали. Вообще программистов нету.
>>779656Мне любая работа программистом пойдет. Лишь бы задачи поставленные решать, в топ 500 мне хоть тресни не войти.
>>779658Как посчитал? Если учесть, что на квалах в этом году было больше 27 тысяч человек, то 255 как-то мало звучит.
>>779660https://www.go-hero.net/jam/16/languages/Python#problems254 contestants может я конечно что то не правильно понимаю
>>779660А, это только 255 питонистов, остальных больше.
>>779666>>779665> 988https://www.go-hero.net/jam/16/regions
>>779658Просто если бы участвовал на 1 человек больше, то было бы переполнение и счёт пошёл бы снова с нуля.
>>779671> https://www.go-hero.net/jam/16/name/Louise.de.La.ValliereАхуеть. Помогите найти этого психа. Хочу на гитхаб его посмотреть.
Вы юзаете std::thread в своих задачках?
>>783524http://e-maxx.ru/algo/bipartite_checking
>>783371нет. Даже не знаю, что это
>>783912И как успехи?
>>783913Уверенный первый див пруфов не будет
>>706313считываешь все запросы сначала, а потом одним проходиком отвечаешь на все
>>726314решай задачи прошлых контестов на кф. Там и разборы есть
>>751674Еще Копелович есть, он классный
>>784436Копелиович. У Рубинчика одноклассник асmщик учился с Копелиовичем, потом его вроде отчислили.
Вот смотрю я задачи на тимусе и вижу как растет сложность с годами, див2А сложнее чуть ли не половины задач тимуса
>>784463Сколько задач на тимусе у тебя?
>>78472539
>>785379Но это даже не близко к половине
>>783371Есть очень мало контестов, типа Distributed Google Code Jam, где он может пригодиться. В остальных случаях процессорное время считается, очевидно, как сумма всех тредов, так что оверхед на управление тредами только навредит.
Алгоритмотреда нет, спрошу здесь.Вот есть следующая задача. Дана плоскость, есть несколько точек на ней (до 500), с не очень большими координатами (от 0 до 50, вещественные). Надо найти для каждой пары точек кратчайший путь между ними.Плоскость (можно рассматривать только квадрат 50х50) поделена на единичные квадраты, каждому квадрату сопоставлен какой-то вес. Соответственно, длины всех отрезков внутри квадрата домножаются на его вес.Не обязательно точное решение (я не уверен, что оно есть), но очень хорошее приближение желательно, да и чтобы работало быстро.Я пробовал сделать следующее: покрыть большой квадрат сеткой, построить граф на этом, соединить исходные точки с ближайшими вершинами сетки и запустить 500 раз (количество точек) Дейкстру (которая с кучей)Но это работает медленно при сколько-нибудь большом размере сетки, да и хочется таки сделать более хорошее приближение. Всякие A-star для увеличения скорости тут разумеется не подходят - мне надо от точки искать расстояние до всех, а не до одной, то есть все равно почти весь граф придется обойти
>>786159Какой ты ещё граф делал? Судя по твоему условию, тут всё намного хитрее. То есть минимальное расстояние не факт, что прямая, так как разные веса у секторов. Я всё правильно понял? Тогда физическая аналогия -- свет в материале с разной проницаемостью. То есть минимальное расстояние до заданной точки выражается через тригонометрию. И перебором по всем точкам O(n^2). Можно ли быстрее? Надо думать. Ещё такой вопрос -- какой вес на грани квадрата? То есть из одного сектора перпендикулярно дохожу до другого, а дальше двигаюсь вдоль грани: какой в итоге вес?
>>786249Да, конечно не прямая, иначе в чем задача, лол. Но, тем не менее, это какая-то ломаная с не очень большим числом отрезковСчитаем, что по грани совсем вдоль нельзя идти - либо ты с одной стороны (на eps), либо с другой.А как выражается через тригонометрию, я не понимаю вот чего-то. Ну то есть явное аналитическое уравнение у меня не получилось написать. Для случая если надо перебраться в какую-то точку в соседнем квадрате понятно как считать еще (да и то, если оптимальныей путь не идет как-то в обход), а в общем случае хуй поймет.
>>786249>>786257>какой графЭм, ну в смысле? Я ж сказал: покрываю все мелкой сеткой с небольшим шагом (например, 1/3, если меньше, то дольше работает), вершины - узлы сетки и исходные точки, ребра - отрезки между соседними точками сетки (по всем 8 направлениям), веса считаются легко
>>786262А, понял про граф. Но погрешность же большая.
>>786278Ну так да, я и говорю, что хочется как-то оптимальнее. А не очень понятно как, не увеличивая плотность сетки
>>786341Расскажи подробнее про требуемую точность и производительность.Сколько есть времени на анализ плоскости, и сколько раз после этого надо определять расстояния между точками на ней?Я бы увеличил количество точек, но оставил только точки в фиксированных позициях на границах квадратов.Предрассчитываем таблицу расстояний между точками с фиксированными позициями на сторонах квадрата, чтобы потом забыть про тригонометрию. Цена ребра равна соотв. расстоянию на коэффициент квадрата.Дальше группируешь квадраты в блоки 4x4, строишь для каждого блока матрицу расстояний между всеми его внешними точками (можешь начать с расстояний между внутренними точками квадратов 2x2, потом между их внешними точками, а потом объединить четыре 2x2 в один 4x4 и повторить процесс). Можно придумать оптимизации исходя из геометрического смысла. Например путь из (0.1, 0.1) в (2.1, 0.1) точно не проходит через (1.1, 0.9).Как пользоваться этим я думаю понятно. Но не забывай, что кратчайший путь между точками внутри блока может выходить за пределы блока.
АХТУНГ ВСЕМ ЗАДРОТАМ У ВАС УНИКАЛЬНЫЙ ШАНС ПРИМЕНИТЬ СВОИ ЗНАНИЯ НА ПРАКТИКЕЕсть 1 взвешенный, неориентированный граф. Он разделён на 2 подграфа так что все его вершины входят в один из двух подграфов. При этом оба эти подграфа состоят только из одной компоненты связанности. У этого графа веса имеют не вершины, а рёбра. Ценой графа называется сумма весов всех ребер которые соединяют 2 подграфа. Разрешается переносить любую вершину подграфа в другой подграф кроме некоторых закреплёных. Закреплёные вершины всегда соединенны рёбами только с вершинами своего подграфа и названы заранее. Задача минимизировать цену графа так чтобы количество вершин принадлежащих каждому подграфу осталось неизменным и подграфы остались состоять из одной компоненты связанности.
>>787900Ограничения на размер графа?
>>787900Вот это воды налил, вместо того чтобы просто описать ограничения на минимальный разрез.По теме, решения с ходу не знаю, есть подозрение, что за полином не решается, ну или очень трудно. В любом случае, глянь в сторону как раз минимального разреза.
>>787988Не у тебя у одного такое подозрение возникло. Сходу даже не решается частный случай невзвешенного графа например
>>787900Щас подумал про закреплёные вершины. Они не нужны исли в клнце просто одну проверкц добавить. Может так задача проще станет? Почитал про разрез. Мне его минимального веса надо и размеры подграфов не должны поменяться. Тогда нужно найти минимальный разрез такой алгоритм ведь есть? пока он не будет делить граф правильно искать следующий за ним по размеру разрез. Такое возможно?
>>788264Ну ты сам подумай, что сказал. Фактически ты перебираешь разрезы, а их экспонента (все возможные разбиения на два множества, 2^V)>>788176Ну от твоего частного случая до общего уже очень близко. Если подставим кратные рёбра, то получим дискретный случай.
Ахтунг, ты слишком неопределённо поставил задачу. В общем случае она NP-сложная. Если соединить фиксированные вершины каждого подграфа рёбрами бесконечного веса со своей вершиной (чтобы гарантировать, что фиксированные вершины окажутся в разных подграфах), а также добавить две вершины, соединённые со всеми остальными рёбрами нулевого веса (это возможный частный случай входных данных, при котором связность подграфов гарантирована), то получаем задачу о fixed balance edge cut, которая известна NP-сложностью.Но если знать, например, что вершин не больше сотни, или что максимальная степень графа невысокая, или что он разреженный, или что он планарный, или что требуется приближённое решение, то можно подумать об оптимизациях.Есть ли у задачи физический смысл, типа раскидывания компонентов по сторонам платы, или серверов по датацентрам?
>>788449>что вершин не больше сотни2к максимум. У каждой вершины от 2 до 6 рёбер.>требуется приближённое решениеНу в крайнем случае можно и приближённое. Или сделать вес всех рёбер 1.>Есть ли у задачи физический смыслЕго в некоторых случаях нужно будет в игре применять. Один из них минимизация длины линии фронта или раздел границы после войны. Какой алгоритм там теперь я не знаю, но он либо оставляет какие-то полуострова врезающееся в чужую территорию там где были прорывы, либо анклавы там где были котлы.
http://acm.timus.ru/status.aspx?author=41395смотрите с какой скоростью пацан решал задачки, причем сложные
>>788906Хм, это контест с Петрозаводских сборов. Либо он в числе его авторов, либо он был участником на сборах, а потом досдал задачи, в чем проблема?
>>788646Дуги и вершины нарисованы в фиксированных позициях на плоскости, и должны остаться на тех же местах после проведения разреза? Если да, то это важное ограничение.Оптимальным разбиением пикрелейтеда может быть {A, B, C} и {D, E}, но ты не сможешь провести так границу не пересекая лишних дуг.
>>789363Лол, как ты до такого варианта вообще дошёл? У нас тут на граф задача, а не на геометрию.Твоя геометрия решается за что-то около (V^2)*E то есть не больше чем V^4 в общем случае тупым перебором с сортировкой по полярному углу.
>>791283>Его в некоторых случаях нужно будет в игре применять. Один из них минимизация длины линии фронта или раздел границы после войны.>У нас тут на граф задача, а не на геометрию.Не факт. Возможно >>788449 просто неправильно понял какую задачу ему надо решить.
>>791372fix: Возможно >>787900 просто неправильно понял какую задачу ему надо решить.
>>791372>>791373Да, если это игра, то звучит разумно. Просто надо уточнять такие детали, на плоскости задача, можно сказать, давно известна и решается просто. В общем случае это объект научного исследования.алсо, запилил перекат >>792098 (OP)
