М.Двач / Программирование

Этого треда уже нет.
Это копия, сохраненная 25 июля 2016 года.

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

Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.

55 Кб, 500x500

ОЛИМПИАДНОГО ПРОГРАММИРОВАНИЯ ТРЕД НАМБА 2 02 Апр, 22:28 #706304 В конец треда | Веб

Настало время перекатить и такой тред.

Основные ресурсы с задачками:
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.
Что почитать?
Грэхэм, Кнут, Паташник "Конкретная математика"
Кормен "Алгоритмы. Построение и анализ"
...
Как вкатиться?
Читай книжки сверху, и решай как можно больше

Шапка за пять минут, надеюсь треду жить, принимаются предложения по оформлению

Ответы>>706335>>706651>>726426>>733148>>773859

02 Апр, 22:33 #2 #706313

Открою тред насущным вопросом. Есть задача, в которой мне надобно в отсортированном в порядке неубывания массиве найти подотрезок заданной длины и с заданной суммой. Причем, таких запросов может быть порядка 2x10^5, и элементов в массиве столько же. Я знаю, что можно написать дерево отрезков и для каждого запроса бегать по этому дереву и получать сумму за log, но это в целом дает ассимптотику m n logn, что неприемлемо для ограничений (2 секунды)

Ответы>>706339>>706349>>784402

02 Апр, 22:47 #3 #706325

Какой-то сайт с олимпиадной теорией http://hecs.info/

Ответы>>706335>>731628

02 Апр, 22:52 #4 #706332

Чем кодефорсес лучше хакерранка? На КФ ебаные РАСПИСАНИЯ, за это его не люблю.

Ответы>>706609>>706627

02 Апр, 22:54 #5 #706335

>>706325
>>706304 (OP)
Да, про теорию я, кстати, забыл.
http://hecs.info - поделка школьников - олимпиадников, попытка собрать все в одном месте
http://e-maxx.ru - великолепный ресурс, кладезь понятнейших описаний алгоритмов и структур данных
http://neerc.ifmo.ru/wiki - описания более академичны
http://wikipedia.org - как ни странно, алгоритмы в статьях на русском языке представлены очень и очень неплохо
Достаточно много полезной информации можно получить из блогов на ресурсах из шапки. Информации не только по решению задач, но и по сопутствующим темам вроде стратегии на контесте и т.п.

02 Апр, 22:54 #6 #706337

>>706334
Ну, есть массив 1 2 3 4 5
Подотрезки длины 3:

Ответы>>706338

02 Апр, 22:55 #7 #706338

>>706337
1 2 3
2 3 4
3 4 5

02 Апр, 22:56 #8 #706339

>>706313
Деревья не нужны. Сделай массив частичных сумм s = a[1] + a[2] + ... + a
С помощью них вычислить сумму отрезка m..n можно как s[n] - s[m-1].
Массив у тебя отсортирован, и это надо использовать. Благодаря упорядоченности сумма отрезка будет монотонно возрастать по мере сдвигания начала отрезка к концу массива. Похоже тут у нас работка для бинарного поиска.

Ответы>>706342>>706344

02 Апр, 22:58 #9 #706340

Посоветуйте статьи по Trie.

Ответы>>706360

5 Кб, 635x33

02 Апр, 22:59 #10 #706342

>>706339

02 Апр, 22:59 #11 #706344

>>706339
Ладно, я переусердствовал. Спасибо

02 Апр, 23:03 #12 #706349

>>706313
Если точно задана длина отрезка и нужна сумма, то высчитываешь среднее (сумму делишь на длину отрезка). Находишь в массиве это число или ближайшее меньшее. Это число будет концом отрезка - проходишь к началу массива на нужное количество элементов и высчитываешь сумму (сам отрезок не нужно хранить - только сумму и индекс конца). Проверяешь сумму - если равна то все. Если меньше то сдвигаешь отрезок - увеличиваешь индекс конца, прибавляешь к сумме новый елемент и вычитаешь старый (тот что вылетел). Снова проверяешь сумму и если надо повторяешь. Если сумма стала больше искомой то отрезка нет. Правда сложность сложно определить, она зависит от скорости роста значений елементов массива.

Ответы>>706353

02 Апр, 23:06 #13 #706353

>>706349
Разве тут асимптотика не просто mlogn выходит? Бинпоиск на число запросов

Ответы>>706377

02 Апр, 23:08 #14 #706360

>>706340
https://habrahabr.ru/post/111874/

02 Апр, 23:29 #15 #706377

>>706353
У тебя нет гарантии на то сколько тебе времени прийдется двигать отрезок. Можно (скорее всего) подобрать такие входные данные что бинарным поиском найдешь конец отрезка в самом начале массива и потом будешь двигать в самый конец, тоесть в худшем случае получается m n logn, но для этого значения в массиве должны почти не изменятся. А если значения более-менее возрастают то тогда да, получается m logn. Для худшего случая можно как-то модифицировать алгоритм, например двигать отрезок не сразу по одному элементу, а например, после первого найденого (бинарным поиском) елемента, начать от него перескакивать сразу на несколько десятком или сотен (в зависимости от размера) элементов пока не убедимся что дальше сумма больше - и тогда уже можно искать точнее сдвигая по одному элементу.

03 Апр, 10:47 #16 #706596

Кто в Гугл код жэм участвовать будет?

Ответы>>706798

03 Апр, 11:36 #17 #706609

>>706332
Бамп вопросу.

03 Апр, 12:35 #18 #706627

>>706332
В смысле "расписания"? На хаккерранке соревнования тоже по расписанию. Есть задачи которые проссто можно решать - но на КФ тоже же (вроде) можно.

Ответы>>706635

03 Апр, 12:44 #19 #706635

>>706627
Да, на кфе перманентно доступен архив со ВСЕМИ задачами прошедших соревнований

763 Кб, 1920x1080

03 Апр, 13:16 #20 #706651

>>706304 (OP)
Стоит ли тратить на это время, если мне не нравится этим заниматься? Скажем, для того чтобы показывать работодателям и все такое?

Ответы>>706660

03 Апр, 13:24 #21 #706660

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

03 Апр, 15:43 #22 #706792

Заключительный этап всероса - это примерно какой уровень задач на CF (div1-2 A-E)?

Ответы>>706794

03 Апр, 15:45 #23 #706794

>>706792
Это тебе надо решать обычно весь div1

Ответы>>706809

03 Апр, 15:50 #24 #706798

>>706596
Я

03 Апр, 16:07 #25 #706809

>>706794
У меня сосед был, с 7-го класса брал призера, а в 11-м победителя. Как-то писал КФ при мне, решил то ли 3 задачи, то ли 2. Может, конечно, несерьезно подошел.

Ответы>>706812>>707059

03 Апр, 16:09 #26 #706812

>>706809
На кфе немного своя специфика-таки. И времени меньше, и задачи менее идейные. Есть знакомый математик, который в девятом классе выиграл всерос по математике, решив там все задачи. По программированию он тоже на всерос ездит и берет там призерство за счет идейных задач. Я даже не уверен, напишет ли он сам Декартку или ДО

03 Апр, 16:54 #27 #706841

Что я делаю не так при вычислении медианы целочисленного потока онлайновым алгоритмом?

https://www.hackerrank.com/challenges/find-median-1

https://ideone.com/WKvtSb

Ответы>>707447

03 Апр, 17:07 #28 #706854

Тут кто-нибудь умеет хорошо решать динамику?

03 Апр, 17:35 #29 #706872

Я ньюфаг, записался в ВУЗе на курсы, щас тренируют на acmp, говорят, что потом нужно на Тимус с Кодфорсами переходить. И у меня возник вопрос: какова сложность задач на олимпиадах (на том же acm) по сравнению с acmp? Если я решаю на acmp задачи сложности 30-40% это же все хуйня по сравнению с олимпиадами?

Ответы>>706886

03 Апр, 17:43 #30 #706886

>>706872
Да, хуйня.

Ответы>>707375

193 Кб, 825x517

03 Апр, 18:51 #31 #706979

Пацаны, дайте подсказку, с какой стороны подходить вообще.

Ответы>>707003>>707180>>725985>>729739

03 Апр, 19:24 #32 #707003

>>706979
Представь граф, в котором все команды - вершины, а рёбра соединяют команды, сыгравшие друг с другом хотя бы один матч.
Теперь забудь про этот граф. Тебе понадобится другой - в котором ребра соединяют команды, НЕ игравшие друг с другом.
В этом втором графе тебе надо найти связный подграф размера K.
Пишешь Брона-Кербоша, с тем отличием, что тебе надо находить не максимальный связный подграф, а первый попавшийся размера K.

Ответы>>707014>>707184>>707255

03 Апр, 19:41 #33 #707014

>>707003
Эх, пока не мой уровень. Но попробую накостылить.

03 Апр, 20:39 #34 #707059

>>706809
И где сейчас этот сосед, к чему пришел?

Ответы>>707102

03 Апр, 21:14 #35 #707102

>>707059
3 курс ФИВТ МФТИ, преподает в Мытищинской школе программистов, уже год вроде. 3-х учеников поднял до финалистов - победитель/призер/призер.
Может уже и перебрался куда, связи не имею с ним.

03 Апр, 22:46 #36 #707180

>>706979
Это всерос 2013?

03 Апр, 22:52 #37 #707184

>>707003
Лол, и как твой Брон-Кербош в TL влезать будет?

Ответы>>707198>>707274

03 Апр, 23:28 #38 #707198

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

Ответы>>707199>>707259

03 Апр, 23:29 #39 #707199

>>707198
То есть не убрать по одному элементу, а брать через один.

04 Апр, 01:48 #40 #707255

>>707003
Как тут вообще строить граф по стольким данным? 100000 матчей - это 50000 команд. По идее тут не пройдут алгоритмы хуже линии.
Может какая хитрая маска.

Ответы>>707259>>707264>>707270

04 Апр, 01:52 #41 #707259

>>707255
>>707198

Ответы>>707263

04 Апр, 02:00 #42 #707263

>>707259
Кстати, может быть так, что пара команд играла друг с другом в обоих раундах.

Ответы>>707265

04 Апр, 02:01 #43 #707264

>>707255
Берёшь случайную вершину V1, произвольно выбираешь одно из её рёбер. Переходишь по этому ребру в V2.
У V2 два ребра. По одному ты пришёл, а другое ведёт куда-то ещё. Переходишь по второму ребру и т.д.
Рано или поздно ты вернёшься в V1. Это значит цикл замкнулся.

Ответы>>707269

04 Апр, 02:02 #44 #707265

>>707263
Частный случай - цикл длины 2. Но да, может поломать алгоритм, если ты не предусмотрел это.

04 Апр, 02:06 #45 #707269

>>707264
Это ты к чему?

Ответы>>707270

04 Апр, 02:07 #46 #707270

>>707269
К >>707255

Ответы>>707272

04 Апр, 02:17 #47 #707272

>>707270
Как ты его хранить будешь, скажи для начала. Вектор векторов или 2д-массив булов? Размер инверсированного графа в любом случае будет 50000*50000=2500000000=2.5 гига. Я про это писал.

Ответы>>707274

04 Апр, 02:29 #48 #707274

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

Ответы>>707278

3 Кб, 200x175

04 Апр, 02:55 #49 #707278

>>707274
Блин, точняк. Тупо идти через один. С поправкой на не входящие в основной остов пары. Стало понятно, когда представил граф.

04 Апр, 09:16 #50 #707375

>>706886
А какой сложности вообще задания на олимпиадах по той же шкале acmp? Сам определить не могу.

Ответы>>707421

04 Апр, 11:00 #51 #707421

>>707375
Варьируются. Обычно есть и та задача, которую должны решить все, и та, которую вероятнее всего не решит никто

Ответы>>707548

04 Апр, 12:21 #52 #707447

>>706841
else if (max_heap.size() > min_heap.size())
return max_heap.top();
else
return min_heap.top();
из нижней части нужен максимальный элемент, а из верхней минимальный. А ты берёшь из обоих максимальный.
На самом деле тут достаточно очереди для верхней половины списка и одного значения для нижней. Первые (n-2)/2 элементов не могут повлиять на результат, их не надо хранить.

Ответы>>708342

04 Апр, 14:51 #53 #707548

>>707421
Ну а средняя часть между этими 2 задачами? Вообще какой сложности я должен уметь решать, чтобы дойти до полуфинала acm.

Ответы>>707554

04 Апр, 14:54 #54 #707554

>>707548
http://codeforces.com/gyms
Только на первой странице полно четвертьфиналов московских

05 Апр, 01:46 #55 #708105

А у каких задача на acmp вообще подходящая сложность?
мимо ещё ньюфаг

05 Апр, 12:27 #56 #708342

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

Аноним 05 Апр, 13:48 #57 #708418

Всесибирская в этом году - лютая параша. Ощущение, что просто пропихивали своих учеников в победители. На проверку принималось 3 языка, на компах не было нормальных сред разработки. Год подготовки коту под хвост.
Намного приятнее было писать всеросс, организация на высоте, соревнование не предполагало знания какого-то конкретного ЯПа, интересная система начисления баллов. Хоть тут победителя получил.

Ответы>>708524>>708671

05 Апр, 16:02 #58 #708524

>>708418
>Хоть тут победителя получил
Победителя параши? Заключительный этап только начался.

Ответы>>708559

Аноним 05 Апр, 16:41 #59 #708559

>>708524
тьфу ты. я говорил про краевой этап. на заключительный ехать денег нет.

Ответы>>708581

05 Апр, 17:11 #60 #708581

>>708559
Краевой - это хуйня. И она тебе никаких льгот не даст. Призер заключительного = поступление в любой вуз БВИ.

Ответы>>708596

05 Апр, 17:15 #61 #708586

Попробую вбросить идею

05 Апр, 17:16 #62 #708589

В общем, мы тут решили конкурс-олимпиадку запилить на 4 недели.
Пока только наброски идеи и правил: https://my.mixtape.moe/osxgjw.txt
Критика (кроме сообщений о кривой кодировке) приветствуется.

Ответы>>708592>>708593

05 Апр, 17:23 #63 #708592

>>708589
Кодировка кривая

sage 05 Апр, 17:24 #64 #708593

>>708589
Иди покакай.

05 Апр, 17:27 #65 #708595

Алсо, кто не решил сокобан на тимусе, тот не спортивный программист.

Аноним 05 Апр, 17:29 #66 #708596

>>708581
и я о том же. поэтому и готовился к всесибу (собираюсь в НГУ). задачи к слову были куда проще, чем на всероссе, даже краевом. знания алгоритма рекурсивной заливки и флойда-уоршела хватило бы для решения всех задач, остальные "идейные". теперь только егэ сдавать на 100, и все в тот же нгу.

Ответы>>708602

05 Апр, 17:38 #67 #708602

>>708596
А че не в Москву

Ответы>>708636

Аноним 05 Апр, 18:16 #68 #708636

>>708602
думал про МАИ, но жить и работать хочу в Новосибирске, например в ДубльГис. Сейчас вот думаю какой из двух вузов выбрать: НГУ или НГТУ

05 Апр, 18:59 #69 #708671

>>708418
Как понять нет денег на всеросс ехать? У кого нет денег? Поступай в УрФУ вместо москвы, там очень крутой тренер асмщик Миша. В Москве ты не пробьешься в команды.

Ответы>>708702

Аноним 05 Апр, 19:34 #70 #708702

>>708671
денег нет доехать до Москвы. я живу в Алтайском крае, тут билеты до Москвы стоят 2 месячные зарплаты. И я не планирую дальше заниматься acm, раньше рассматривал только как способ поступления в топовый вуз, например НГУ

Ответы>>708711>>708717

05 Апр, 19:37 #71 #708711

>>708702
Заключительный этап в Казане.

Ответы>>709137

05 Апр, 19:47 #72 #708717

>>708702
управление образования же должно оплачивать

Ответы>>708721>>709006>>709137

05 Апр, 19:48 #73 #708718

Да и ЕГЭ выдрочить гораздно проще чем асм

05 Апр, 19:51 #74 #708721

>>708717
Скорее всего, он не прошел.

06 Апр, 01:52 #75 #709006

>>708717
Оплачивает регион, так что всегда находятся регионы, откуда за свои едут.

Аноним 06 Апр, 10:03 #76 #709137

>>708717
регион. а я живу в наверное, самом бедном регионе страны. тут на уличное освещение то денег не находится. в прошлом году
>>708711
стоимость билета одна. и в прошлом году в Инополис на роботехнику пришлось ехать через Москву (хз почему так)

sage 06 Апр, 21:41 #77 #709634

бесполезная дрочка с тошнотворными задачками

мимо бывший олимпиадник

Ответы>>709635>>709661>>709701

06 Апр, 21:42 #78 #709635

>>709634
А теперь кто?

06 Апр, 22:03 #79 #709661

>>709634
какой уровень у тебя был? к чему сейчас пришел?

06 Апр, 22:52 #80 #709701

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

почти бывший олимпиадник

Ответы>>709707

06 Апр, 22:56 #81 #709707

>>709701
А в каком деле не дрочка?

Ответы>>709737

06 Апр, 23:19 #82 #709737

>>709707
Да ни в каком, ясное дело, но спортивное программирование уж слишком узкая область. Становится тесно и скучно.

07 Апр, 20:26 #83 #710403

Туристу хуйнули -600 рейтинга.

Ответы>>710411

07 Апр, 20:33 #84 #710411

>>710403
Дай ссылку на драму что-ле

Ответы>>710443

07 Апр, 20:54 #85 #710443

>>710411
На главной. Он, мол, каждый раз побеждал сам себя.

Ответы>>710455

07 Апр, 21:08 #86 #710455

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

Ответы>>710461

07 Апр, 21:19 #87 #710461

>>710455
Да. Дельта рейтинга зависит от рейтинга участников, которых ты опередил. Был баг, что сам участник всегда был в этом списке. И турист всегда фактически обыгрывал чела с 4000+ рейтинга.

07 Апр, 21:33 #88 #710478

Прикольно быть Геной

Ответы>>710485>>710511

07 Апр, 21:36 #89 #710485

>>710478
Все жду, когда он повесится, аки всякие вундеркинды

Ответы>>710521

07 Апр, 22:04 #90 #710511

>>710478
Прикольнее быть сыном олигарха.

sage 07 Апр, 22:17 #91 #710521

>>710485
Зато у него есть девушка, а у тебя нет))0)

79 Кб, 423x650

08 Апр, 02:47 #92 #710693

Напоминаю, что меньше чем через сутки начинается квал Google Code Jam.

Ответы>>710903>>718177>>779649

08 Апр, 12:01 #93 #710903

>>710693
поможете решить? хочу стажировку с сша, но не умею решать ничего

Ответы>>711084>>711215

sage 08 Апр, 15:47 #94 #711084

>>710903
Чёт в голосяндру с тебя

sage 08 Апр, 17:43 #95 #711215

>>710903
Лол, там чтобы чёртову футболку получить надо быть где-то на уровне призёра всероса. иди вон из треда

Ответы>>711231

08 Апр, 18:09 #96 #711231

>>711215
топ 500 надо быть

Ответы>>711374

08 Апр, 18:12 #97 #711232

АЦМщики, среди вас крутые шахматисты?

Ответы>>711293

08 Апр, 19:31 #98 #711293

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

Ответы>>711315

08 Апр, 20:05 #99 #711315

>>711293
Потому что и то, и другое являются интеллектуальными занятиями. Нередко бывает, что олимпиадники-предметники играют в ЧГК, шахматы или еще что подобное.

Ответы>>711318

08 Апр, 20:09 #100 #711318

>>711315
Программист-олимпиадник, неплохо играю в шахматы, в ЧГК тащу с командой.
Вещи эти не сильно связаны между собой. Тут скорее объединяет общий вопрос: любишь думать?

Ответы>>711343

08 Апр, 21:30 #101 #711343

>>711318
ЧГК - рилейтед хобби, потому что в обоих занятиях решает уровень абстракции мышления

Ответы>>711348

08 Апр, 21:47 #102 #711348

>>711343
А шахматы чем не подходят?

Ответы>>711350

08 Апр, 21:48 #103 #711350

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

Ответы>>711378

08 Апр, 22:11 #104 #711374

>>711231
Топ500 это в 3 раунд, футболка топ1000, по крайней мере, в том году так было.

08 Апр, 22:17 #105 #711378

>>711350
>дроч схем, дебютов, эндшпилей, мидшпелей.
А как же шахматы Фишера, не слышал что ли? Даже в нашей деревне в них в школе рубились, чтобы вывести на чистую воду соперника, который постоянно одной и той же тактики придерживался.

09 Апр, 02:00 #106 #711511

Началось!

09 Апр, 02:20 #107 #711515

Чёт долго тупил над первой. Наверное ночь сказывается.

Ответы>>711573

09 Апр, 02:34 #108 #711517

Есть B. Тоже несложная. Билл Гейтс что-то такое мутил по молодости.

Ответы>>711573

09 Апр, 03:39 #109 #711527

Решил C small.

Ответы>>711573

09 Апр, 03:43 #110 #711528

Да и large засабмиттил.

Ответы>>711573

09 Апр, 03:53 #111 #711529

Вроде въехал в D.

Ответы>>711573

09 Апр, 04:16 #112 #711530

Заебись, можно спать.

09 Апр, 09:03 #113 #711573

>>711515
>>711517
>>711527
>>711528
>>711529
Как же я вам вундеркиндам завидую.
Какая цель у тебя, на работу к ним хочешь?

Ответы>>711765>>711832

09 Апр, 13:10 #114 #711765

>>711573
Бля, это квалификационный раунд. Чему ты там завидуешь?

Ответы>>711851

09 Апр, 14:06 #115 #711832

>>711573
Ну вот прикинь, готовится моё собеседование в Яндекс. Тут дверь распахивается, и вхожу я в футболке от Гугла.

Ответы>>711963>>711971

09 Апр, 14:22 #116 #711851

>>711765
Я и такое не могу решить. А вообще бывают кто стал неплох в асм своими силами без кружков, тренеров и универов?

Ответы>>711905>>712280

09 Апр, 14:59 #117 #711905

>>711851
Как ты представляешь участие в студенческой олимпиаде без универов?
И что считается "неплох"?

Ответы>>712220

Аноним 09 Апр, 16:09 #118 #711963

>>711832
ахуенно же. яб вдул

09 Апр, 16:15 #119 #711971

>>711832
А в чём проблема? Не футболке самого яндекса же.

09 Апр, 16:58 #120 #712018

Такое чувство, что полдвача олимпиадники.

09 Апр, 21:43 #121 #712220

>>711905
На кфе должно быть достаточно таких "вылезаторов"

09 Апр, 23:25 #122 #712280

>>711851
Ты бы хоть форум codeforces почитал, там половина околокрасных это подпивасные самоучки. а другая половина - школьники, лол

10 Апр, 05:13 #123 #712453

Квалификация закончилась. Я так высоко в рейтинге, что мне вас отсюда почти не видно.

Ответы>>712475>>712937

10 Апр, 07:21 #124 #712475

>>712453
Очки протри, лол. Русских вверху рейтинга полно. D-large хоть правильно решил? Все остальное примитивно совсем.

Ответы>>712693

10 Апр, 09:11 #125 #712496

Я не прошёл квал, начал изучать программирование 2 месяца назад

10 Апр, 14:14 #126 #712693

>>712475
За счёт того что у меня все большие оказались решены правильно, а у некоторых нет я где-то на 20 мест поднялся при финализации результатов.

Ответы>>713065

10 Апр, 16:49 #127 #712937

>>712453
Квал никому не интересен, в 3 раунде веселее будет если ты туда пройдёшь, лол

10 Апр, 17:38 #128 #713007

Я тут один буду вайлдкард вк капа писать?

Ответы>>713048>>713085

11 Кб, 168x348

10 Апр, 18:11 #129 #713048

>>713007
Ну пиздец.
Вижу в прошедших контестах VK Cup 2016 и VK Cup 2016 - Round 1. При этом напротив "VK Cup 2016 - Уайлд-кард раунд 1" активна кнопка зарегистрироваться. Что это значит, я всё-таки могу участвовать?
Лезу читать детали, раскапываю что требуемый возраст от 14 до 23, да и вообще я со своим пустым профилем иду лесом.
Зачем прятать эту информацию так далеко? Почему нельзя убрать кнопку "зарегистрироваться" у тех, кто не проходит по условиям?

I am dissapoint.

Ещё и моих любимых языков нет в их списке. Ну нафиг этот codeforces.

Ответы>>713050>>713369

10 Апр, 18:13 #130 #713050

>>713048
что это за такие любимые языки?

Ответы>>713053>>713065

10 Апр, 18:15 #131 #713053

>>713050
VisualBasic, perl

10 Апр, 18:28 #132 #713065

>>713050
Не скажу конкретно, я и так близок к деанону после >>712693
Но почему нет Prolog, Erlang, Rust, F#, Clojure, Groovy, J, R наконец?

Ответы>>713103>>713137

10 Апр, 18:42 #133 #713085

>>713007
Я буду, 1 раунд проебал.

Ответы>>713093

10 Апр, 18:45 #134 #713093

>>713085
Я вообще первый раунд не писал. За меня отдувался сокомандник, но он вообще серый, лол. Почти, кстати, прошел

Ответы>>713383

10 Апр, 18:52 #135 #713103

>>713065
А ты крут, много зарабатываешь?

Ответы>>713106

10 Апр, 18:52 #136 #713106

>>713103
Не, у меня просто много свободного времени потому что я безработный.

Ответы>>713113

10 Апр, 19:00 #137 #713113

>>713106
Какой рейтинг у тебя на кфе? Давно занимаешься программированием?

Ответы>>713119

10 Апр, 19:05 #138 #713119

>>713113
На кфе пустой профиль пока.
Занимался в универе не слишком активно, потом работал программером 3 года. Год назад контора закрылась. Надрачивался в основном последний год.

10 Апр, 19:22 #139 #713137

>>713065
> я и так близок к деанону
Да всем похуй на тебя. Хоть скрин паспорта сюда вбрось.

46 Кб, 640x480

10 Апр, 21:16 #140 #713338

Почему ещё не сделали официальную команду /pr/?

10 Апр, 21:36 #141 #713369

>>713048
Дишка есть, надо попробовать.

10 Апр, 21:43 #142 #713383

>>713093
Я это и имел в виду, проебал это мы просто забили. Так пока раунд нормально идёт.

10 Апр, 22:10 #143 #713405

Пиздец. Я так и не осилил этот ебучий J

Ответы>>713408

10 Апр, 22:13 #144 #713408

>>713405
А мы 5 штучек сделали в итоге.

Ответы>>713412

10 Апр, 22:16 #145 #713412

>>713408
Поздравляю
У меня просто сокомандник даун. Вот вообще не помогал. Печально. Интересно, что и где пишут на этом языке

10 Апр, 22:45 #146 #713426

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

Ответы>>713428>>713433

10 Апр, 22:52 #147 #713428

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

Ответы>>713429>>713430

10 Апр, 22:54 #148 #713429

>>713428
*минимумов

10 Апр, 22:54 #149 #713430

>>713428
и перед этим, для пущей ахуенности отсортить по левой границе. так?

Ответы>>713431>>713434

10 Апр, 22:55 #150 #713431

>>713430
запросы

10 Апр, 22:57 #151 #713433

>>713426
scanline по запросам.

Ответы>>713439

10 Апр, 22:57 #152 #713434

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

10 Апр, 23:11 #153 #713439

>>713433
я хз что такое сканлайны
гугла на мусор выводит

Ответы>>713443

10 Апр, 23:17 #154 #713443

>>713439
Собственно, прямой перевод: сканирующая прямая.

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

Ответы>>713446

10 Апр, 23:21 #155 #713446

>>713443
нормас, спасибо
плюс к рейтингу на кф тебе, бродяга

11 Апр, 07:44 #156 #713551

Помогите осознать простенькую динамику. Я-то сам умею только считать количество способов дойти куда-то в n-мерном пространстве за k шагов, а тут еще за каждый шаг дают разное число очков и его надо максимизировать. Если конкретнее, то есть полоска из клеток, у каждой клетки есть приз, и каждый из k ходов мы должны либо уйти на x в одну сторону, на y в другую или вообще на месте. Как тут переходы должны выглядеть?

Ответы>>713738

11 Апр, 13:48 #157 #713738

>>713551
Непонятно, напиши подробнее.

Ответы>>713816

11 Апр, 15:40 #158 #713816

>>713738
Есть полоса из клеток. У каждой клетки приз за то, что наступаешь в нее. Есть k шагов. Каждый ход идем в клетку, которая лежит в х клетот слева, или в y справа, либо вовсе остаемся на месте и снова получаем очки, будто мы только что пришли в эту клетку. Теперь надо максимизировать наш счет

Ответы>>713818>>713848

11 Апр, 15:44 #159 #713818

>>713816
Черт, только что подумал. Может, это тупой рекурсией зайдет? Вечером ограничения уточню

11 Апр, 16:18 #160 #713848

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

Ответы>>713853>>713856

11 Апр, 16:23 #161 #713853

>>713848
Рекурсия с мемоизацией кушает много памяти - почти NK вместо 2N.

Ответы>>713875

11 Апр, 16:28 #162 #713856

>>713848
Я понимаю, что это динамика, что двумерная. А вот как переход делать не догоняю

Ответы>>713875

11 Апр, 16:58 #163 #713875

>>713853
Ну да, кушает, ограничений-то мы всё равно не знаем.
>>713856
Как говорится, переход очевиден. Пусть прошло М шагов, мы рассматриваем клетку К. D - динамика, А - бонусы. Тогда мы к D[M+1][K-x] прибавляем D[M][K]+A[K-x], остальные два перехода по тому же принципу.

Ответы>>713878>>714242

11 Апр, 17:06 #164 #713878

>>713875
Не прибавляем, а обновляем значение, если новое больше старого, или если D[M+1][K-x] было не инициализировано.
Да и на D[M][K] надо для начала посмотреть, инициализировано ли оно.

Ответы>>713884>>714242

11 Апр, 17:14 #165 #713884

>>713878
Ну да, обновляем. Смотреть никуда не надо, просто сначала нормально инициализировать динамику нужно и всё.

Ответы>>713885

11 Апр, 17:15 #166 #713885

>>713884
Нормально это как?

Ответы>>713907

11 Апр, 17:18 #167 #713888

А на этом говне (J) ктонибудь кодит в реале? Или оно годится только для этих тестиков?

Ответы>>713889

11 Апр, 17:19 #168 #713889

>>713888
Я кодю. Пруф: $%(&^%^$%^&()((&^%^&()_)(&(*%$

Ответы>>713891

7 Кб, 626x50

11 Апр, 17:20 #169 #713891

>>713889
Давай рассказывай как его правильно запускать чтобы я мозги не ебал.

Ответы>>713897

93 Кб, 811x741

11 Апр, 17:28 #170 #713897

>>713891
Тащемта никакого секрета тут нет. Просто берёшь и запускаешь без задней мысли.

Ответы>>713905

46 Кб, 605x117

11 Апр, 17:45 #171 #713905

>>713897
Ладно, попробую собрать новую 8 версию желания ебаться с косяком 7ого pkgbuild'а нету.

11 Апр, 17:46 #172 #713907

>>713885
Ну или нулями, или -INF, по ситуации.

Ответы>>713913

11 Апр, 17:50 #173 #713913

>>713907
Нулями некорректно. После первого хода ты можешь достичь 3-х ячеек, а с нулями будет выглядеть будто ты оказался и в этих трёх, заработав сколько-то, и достиг всег остальных, заработав 0.
-INF можно, но некрасиво.
null самое то.

Ответы>>713931

66 Кб, 669x506

11 Апр, 17:54 #174 #713920

Оффтопик конечно, но почему автор компиля J забил на ворнинги?

Ответы>>713933

11 Апр, 18:05 #175 #713931

>>713913
На олимпиадах красота никого не интересует... Что нулями некорректно, я отлично понимаю, просто сказал два самых частых решения. Ещё иногда -1 используется, вместо null.

sage 11 Апр, 18:06 #176 #713933

>>713920
Ты серьёзно сел разбираться с этим говном?

11 Апр, 19:04 #177 #713976

Ребята, вы у телочек пользуетесь популярностью?

Ответы>>713979>>713985

sage 11 Апр, 19:09 #178 #713979

>>713976
нет

Ответы>>714046

11 Апр, 19:14 #179 #713985

>>713976
Семь лет и 30 килограмм назад у меня были шансы.

Ответы>>714046

11 Апр, 20:29 #180 #714046

>>713979
>>713985
Короткевич с Бардашевичем так то крутыми выглядят , особенно с наградами в руках, телки любят таких

Ответы>>714206

11 Апр, 22:41 #181 #714206

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

11 Апр, 23:11 #182 #714242

>>713875
>>713878
Спасибо огромное, но не объясните ли вы, почему этот алгоритм не вырождается в обычную жадность? Разве мы не локально для каждого прыжка выбираем самый выгодный ход?

Ответы>>714243

11 Апр, 23:13 #183 #714243

>>714242
А ты условие объясни сначала. Мы из любой клетки можем начинать или как, ограничения какие, это всё важно.

Ответы>>714246

334 Кб, 1366x768

11 Апр, 23:16 #184 #714246

>>714243

Ответы>>714252

11 Апр, 23:24 #185 #714252

>>714246
Интуитивно можно пояснить, что алгоритм не вырождается в жадность, потому что при количество_ходов->∞ самая выгодная стратегия это кратчайшим путём добраться до максимально выгодной клетки и стоять там. При уменьшении количества ходов сначала решение может перейти в поход до самой выгодной клетки по самому выгодному пути, при дальнейшем уменьшении уже вообще непонятно что будет, всё ближе и ближе к результатам жадного алгоритма. Надеюсь, стало чуть более понятно, я имею опыт только таких полуинтуитивных догадок, почему в одной задаче жадник, а в другой динамика.

Закрой ты уже доки по J, в самом деле, и забудь о нём навсегда.

Ответы>>714254

11 Апр, 23:27 #186 #714254

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

Ответы>>714256

11 Апр, 23:30 #187 #714256

>>714254
О, это уже намного проще пояснить. Сначала, очевидный факт, что решение для N шагов зависит только от решения для N-1 шагов. Дальше ты доказываешь корректность перехода так: во-первых, такой переход не ухудшает ответ, во-вторых, лучше сделать нельзя, следовательно, он оптимальный.

Это совсем кратко, но в общем это схема типичного доказательства перехода.

он отвратителен, его синтаксис не для людей

Ответы>>714259

11 Апр, 23:32 #188 #714259

>>714256
Все, понял. Сотни нефти тебе

А мне доставляет

Ответы>>714261

11 Апр, 23:38 #189 #714261

>>714259
Для хардкорной практики придумывания и доказательства динамики есть прекрасная задача "Казино": всерос 2005, финал, день 1, задача С; №11 на informatics.mccme.ru.

Ответы>>714276

11 Апр, 23:54 #190 #714276

>>714261
Ага, гляну. А еще такой вопрос. Мне для следующей итерации, какую клетку считать новой стартовой? Неужели просто ту, на которой я отхвачу максимум очков в предыдущей итерации?

Ответы>>714295

12 Апр, 00:11 #191 #714295

>>714276
Ты не понял сути. В ДП ты идёшь по всем путям одновременно, шаг за шагом.
Стартовыми будут все клетки полученные на предыдущей итерации.

Ответы>>714299

12 Апр, 00:14 #192 #714299

>>714295
Да, я уже написал. Каждый раз загоняю в вектор возможные стартовые клетки и от них стартую. Ва на тесте 8 - это на что похоже? Переменные, где может быть переполнение, вроде уже проверил

Ответы>>714328

12 Апр, 00:53 #193 #714328

>>714299
Зачем ты их загоняешь куда-то?? У тебя есть массив динамики, сначала ты инициализируешь позиции перед первым ходом как надо, например, в нужные клетки ставишь 0, в остальные -INF. Тогда при пересчёте ты вообще не паришься, пути из неправильных клеток всё равно дадут отрицательные значения и в ответ не попадут. Только тогда надо учесть, что все состояния динамики на каждый ход надо тоже сначала поставить -INF.

Ответы>>714335

12 Апр, 01:05 #194 #714335

>>714328
Действительно. Получил AC. Надо, короче, нарешивать динамику, а то ни один нормальный контест без нее не обходится

12 Апр, 22:40 #195 #715014

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

Ответы>>715107>>715114>>715181>>715209

12 Апр, 23:37 #196 #715107

>>715014
https://en.wikipedia.org/wiki/Rotating_calipers

Ответы>>715200>>715210

12 Апр, 23:44 #197 #715114

>>715014
Берем две(или три если точки трехмерные) оси (90 град одна относительно другой), проецируем на них все точки. Ищем на осях крайние точки - это будет потенциальные длинейшие диагонали.

За какое время такой алгоритм? Линейное?

Ответы>>715121

12 Апр, 23:49 #198 #715121

>>715114
А если не будут?

Ответы>>715126

12 Апр, 23:52 #199 #715126

>>715121
Может и не будут.
Наверно пару осей нужно взять из первой и средней грани предварительно проверив их на сонаправленость.

Ответы>>715129

12 Апр, 23:54 #200 #715129

>>715126
А не, средняя не нужна, перпендикуляр от первой норм будет.

Ответы>>715131

12 Апр, 23:55 #201 #715131

>>715129
Что ты называешь первой гранью?

Ответы>>715134

12 Апр, 23:57 #202 #715134

>>715131
У тебя же полигон точками задан?
Первая грань - vect (p[0] - p[1])

Ответы>>715155

92 Кб, 1154x876

13 Апр, 00:10 #203 #715155

>>715134
Ну вот контрпример на оба случая. Если A и B это p[0] и p[1], то проверка ничем не будет отличаться от первого варианта что ты предложил.

Ответы>>715175

13 Апр, 00:22 #204 #715175

>>715155
Засада. Предлагаю вбить костылей и добавить еще две оси по 45 град. к первым. Инфа 146% этого точно должно хватить!

Хотя может лучше из рандомной грани оси брать. Полик выпуклый - значит примерно на 1/4 граней приходится поворот на 90 град. Значит оптимально, брать перую, n*1/4 и их перпедикуляры.

13 Апр, 00:25 #205 #715181

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

Ответы>>715185>>715197

13 Апр, 00:28 #206 #715185

>>715181
Но искать придется для каждой вершины же.

3 Кб, 400x400

13 Апр, 00:43 #207 #715197

>>715181

Ответы>>715198

59 Кб, 807x873

13 Апр, 00:43 #208 #715198

>>715197
Опередил.

13 Апр, 00:45 #209 #715200

Короче, я уже ответил в >>715107
Там асимптотика O(n). Зачем изобретать велосипед?

Ответы>>715208

13 Апр, 00:58 #210 #715208

>>715200
>Зачем изобретать велосипед?
Интересно же. Потом когда кора одеревенеет, тогда и можно сразу в гугол.

13 Апр, 00:59 #211 #715209

>>715014
Берём любую вершину, ищем для неё противоположную. Дальше, из очевидных соображений, если мы первую вершину сдвинем на 1 по часовой (то есть возьмём следующую вершину), то для этой вершины ответом будет являться либо уже найденная противоположная, либо эту противоположную надо будет так же сдвигать по часовой стрелке. Таким образом, если у нас есть список вершин в порядке обхода по часовой стрелке, то нахождение диагонали занимает линейное время, так как первая вершина пройдёт полный оборот, и противоположная ей суммарно пройдёт тоже ровно 1 оборот.

Обход по часовой стрелке строится за O(NlogN) построением выпуклой оболочки, например, хотя может оказаться, что это пушка по воробьям и тут можно проще.

Ответы>>715210

13 Апр, 01:04 #212 #715210

>>715209
Насколько я понимаю, я описал что-то похожее на >>715107 , ну, чукча не читатель.

2440 Кб, 2295x3327

16 Апр, 04:17 #213 #718177

>>710693
Напоминаю, что уже идёт раунд 1А Google Code Jam.

16 Апр, 06:50 #214 #718195

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

Ответы>>718730

16 Апр, 06:54 #215 #718197

Во второй довольно быстро понял, как найти диагональ, но после этого застрял.
Мне казалось, что надо восстановить сетку полностью.
Где-то час я ломал голову как это сделать. Пытался рекурсией - убираем первый столбец и первую строку, и решаем меньшую задачу. Но соснул на этом пути.

Ответы>>718356

16 Апр, 14:07 #216 #718356

>>718197
Тоже не прошёл, решил всё кроме Clarge, потом просто смотрел, как с 700 места медленно съезжаю вниз.

Ответы>>718730

16 Апр, 21:12 #217 #718730

>>718195
>>718356
Приглашение на собеседование то получите?

Ответы>>718754

16 Апр, 21:38 #218 #718754

>>718730
Ну хватит уже.jpg

17 Апр, 00:06 #219 #718829

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

Ответы>>718843

17 Апр, 00:20 #220 #718843

>>718829
Занимаюсь олимпиадной прогой 5 лет, по сути, так и попал в программирование. Мне это помогло научиться программировать, искать баги, писать код нормально и понятно (потому что как раз на олимпиадках пишешь код настолько блевотно, что больше никогда так делать не хочется, и понимаешь, что никто это не поймёт даже через 5 минут). Алгоритмы дали понимание оптимизации программ, использование оптимальных структур, понимание вообще как это работает в глубине, желание сделать покрасивее и в то же время быстро рабочим. В целом, ящитаю несколько лет олимпиадной проги намного полезнее нескольких лет фронтенда, ну только если ты на фронтенде не собираешься сидеть всю жизнь.

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

Ответы>>718969>>718970

17 Апр, 10:27 #221 #718969

>>718843
+++++

17 Апр, 10:31 #222 #718970

>>718843
Вот проблема только лежит в переходе между началом и дальнейшими действиями.

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

Ответы>>718974

17 Апр, 10:36 #223 #718974

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

Ответы>>718977

17 Апр, 10:40 #224 #718977

>>718974
Допустим я познакомился с крестами только для олимпиад. Я знаю синтаксис, знаю стл. ООП мне нахуй не нужен был до этого. Теперь я хочу познать ооп, прочитал я пару глав книжки. Что-то понял. Но как мне это закрепить на практике? Один раз писал условный класс time, но это же, писец, скучно. Ничего интереснее не найти?

Ответы>>718983

17 Апр, 10:48 #225 #718983

>>718977
Что там в ООП учить-то. Если очень хочешь, то придумай себе проект какой-нибудь, например, обработка русского текста.

Я на ООП никогда внимание не обращал, интересовался новыми фичами, а теперь мои кресты никому и не нужны, на работе почти всегда на питоне пишу, иногда шарп ещё.

Ответы>>718990

17 Апр, 11:06 #226 #718990

>>718983
А как ты на работу попал?

Ответы>>718995

17 Апр, 11:10 #227 #718995

>>718990
hh,ru

Ответы>>718997

17 Апр, 11:11 #228 #718997

>>718995
А скиллы для собеседования где взял. Писал проект какой-нибудь, например, обработку русского текста?

Ответы>>719014

17 Апр, 11:43 #229 #719014

>>718997
Нет, только олимпиадная прога, просто я сейчас в безопасности работаю.

23 Апр, 22:48 #230 #724912

Вы что, сдохли тут все?

Ответы>>725170

24 Апр, 09:59 #231 #725170

>>724912
Все на gcj уехали

Ответы>>725339>>725827

24 Апр, 14:25 #232 #725339

>>725170
Но финал же только через 3 месяца...

Ответы>>725827

24 Апр, 21:33 #233 #725827

>>725170
>>725339
Привезите мне футболку, хочу ходить в ней летом по своему городу как король

sage 24 Апр, 23:41 #234 #725956

Кароч тред официально мертворождённый, прошёл 2 раунд VK Cup и ни одного нового сообщения.

belkka 25 Апр, 00:20 #235 #725985

>>706979
откуда задача?

Ответы>>725995

25 Апр, 00:45 #236 #725995

>>725985
Всерос 2013.

25 Апр, 11:25 #237 #726265

>Что почитать?
И что, обязательно читать теорию от корки до корки, прежде чем лезть в программирование?

Ответы>>726266>>726274

25 Апр, 11:28 #238 #726266

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

25 Апр, 11:39 #239 #726274

>>726265
Все не нужно, в олимпиадках используется подмножество алгоритмов, то что легко и быстро написать. Но что-то нужно посмотреть обязательно, ты не можешь в одиночку придумать все что придумало человечество за 60+ лет, кем бы ты там небыл.

25 Апр, 12:35 #240 #726314

Сколько задач нужно решить на тимусе, чтобы можно было уже пробовать себя на кодефорсес, чтобы рейтинг сразу в парашу не скатить? Вообще, стоит ли прорешивать тимус?

Ответы>>726316>>784415

25 Апр, 12:38 #241 #726316

>>726314
Тимус стоит прорешивать однозначно. Думаю, сотка задач позволит претендовать на эксперта

Ответы>>726317>>726330

25 Апр, 12:46 #242 #726317

>>726316
Я прорешал сотку снизу по сложности. Теперь я эксперт?

Ответы>>726321>>726330

25 Апр, 13:09 #243 #726321

>>726317
На всеросе не сильно соснёшь. А вот кодефорсес пока отложи.

25 Апр, 13:22 #244 #726330

>>726316
>Тимус стоит прорешивать однозначно
Спасибо, значит, буду прорешивать.
>>726317
>Я прорешал сотку снизу по сложности
Давно тренируешься?

Ответы>>726340

25 Апр, 13:30 #245 #726340

>>726330
>Давно тренируешься?
Ну сотку это я переборщил. Где-то 60.
Перед вузом пару месяцев поигрался. На самом деле, на этом уровне почти нет серьезных алгоритмов. В основном матеша и смекалка. Когда встретился с победителями/призерами всероса, потерял мотивацию продолжать.

Ответы>>726346>>726443

25 Апр, 13:39 #246 #726346

>>726340
Потерял по какой причине?

Ответы>>726353

25 Апр, 13:52 #247 #726353

>>726346
Недосягаемый уровень. У людей 5 лет форы во всяких СУНЦах и физмат-лицеях против моей гуманитарной гимназии.

Ответы>>726400

25 Апр, 14:37 #248 #726400

>>726353
А как же Ренат Муллаханов, вечная ему память, из обычной школы, на 1 курсе засел за тренировки, на 3 курсе взял золото финала ЧМ.

Ответы>>726407>>726690>>726734

25 Апр, 14:43 #249 #726407

>>726400
Талант, имхо

25 Апр, 15:00 #250 #726426

>>706304 (OP)
> че почитать
e-maxx же, нет?

25 Апр, 15:18 #251 #726443

>>726340
> В основном матеша и смекалка. Когда встретился с победителями/призерами всероса, потерял мотивацию продолжать.
на всеросе можно взять диплом, не написав алгоритма сложнее бинпоиска, атвичяю. одноклассник так и сделал

Ответы>>726448>>726945

25 Апр, 15:20 #252 #726448

>>726443
>>726443
>одноклассник так и сделал
В каком году?

Ответы>>726454

25 Апр, 15:22 #253 #726454

>>726448
в этом

Ответы>>726554

25 Апр, 16:50 #254 #726554

>>726454
Он сильно задрачивался?

Ответы>>726617

25 Апр, 17:50 #255 #726617

>>726554
ваще нет.

25 Апр, 18:51 #256 #726690

>>726400
Ебать охуенный чувак был. Просто взял и опустил в парашу мамкиных корзиноидов, которых дрочили со школьного возраста.
До сих пор бомблю со всяких "одаренных детей", у которых на проверке оказывается мамка/папка либо сорт оф ученые/преподы, либо бохатые и наняли корзине репетиторов.
В то время как плебс продолжает в неведеньи кушать убогую школьную программу.

Ответы>>726727

25 Апр, 19:24 #257 #726727

>>726690
> а проверке оказывается мамка/папка либо сорт оф ученые/преподы, либо бохатые и наняли корзине репетиторов.
такие одаренности далеко всё равно не идут. а если идут, то шли бы и без мамок-папок-репетиторов

Ответы>>726730>>726747

25 Апр, 19:26 #258 #726730

>>726727
>такие одаренности далеко всё равно не идут
Верно.
>а если идут, то шли бы и без мамок-папок-репетиторов
Неверно.

Ответы>>726797

25 Апр, 19:29 #259 #726734

>>726400
>Ренат Муллаханов
https://www.fl.ru/users/mrk84/

25 Апр, 19:36 #260 #726747

>>726727
>такие одаренности далеко всё равно не идут
На чугунной жопе как раз и идут. Думаешь, все спортивные программисты гении что ли? В основном они стали такими благодаря долгой задрочке, и под присмотром наставников.
>то шли бы и без мамок-папок-репетиторов
Увы, но такое бывает редко. "Маменькиных сынков" больше на порядок. Каким бы ты не был талантом, но без ресурсов и вовремя преподнесённых знаний ты пролетаешь.

Ответы>>726797

25 Апр, 19:54 #261 #726797

>>726747
> без ресурсов
"ресурсы" и "мамка/папка либо сорт оф ученые/преподы, либо бохатые и наняли корзине репетиторов" -- разные вещи. некоторым хватает просто некоторой поддержки, а не последнего

> Думаешь, все спортивные программисты гении что ли?
топовые -- да. а нетоповые на то и нетоповые, сколько бы их мамки и преподы ни надрачивали, они не оч много могут

>>726730
> неверно
имелось в виду "без таких мамок, о которых говорил ты", см. выше

Ответы>>726847

25 Апр, 20:06 #262 #726822

Теперь это памяти Рената М. тред

Ответы>>726889

25 Апр, 20:15 #263 #726847

>>726797
Ну всё, ты прав, ты прав, осади уже.
>сколько бы их мамки и преподы ни надрачивали, они не оч много могут
Впрочем, надо ли? Поиграться для души/мозгов и задрачивать до посинения ради прокачки ЧСВ или пристройки своей жопы в говновуз - немного разные вещи.

Ответы>>726900

25 Апр, 20:54 #264 #726889

>>726822
А что с ним? На кфе так и не сказали, чому он откинулся

Ответы>>726899>>726901

25 Апр, 21:03 #265 #726899

>>726889
Что-то с давлением было.

25 Апр, 21:04 #266 #726900

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

Ответы>>726906

25 Апр, 21:04 #267 #726901

>>726889
Рак жопы.

25 Апр, 21:10 #268 #726906

>>726900
Меня вот моя мамка-швея заставляла только ходить в церковь. И гулять в день как минимум 2 часа. Приходилось тупо стоять у подъезда, чтобы потом посидеть за компом, а то шнур забирала. А когда она уебывала на работу, со мной оставалась бабка, которая бухала до состояния говнины и валялась обоссанной в туалете.
А теперь сравни с родителями Короткевича, программистами, которые обучали его с самого детства.

Ответы>>726914>>726989

25 Апр, 21:19 #269 #726914

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

Ответы>>726925

25 Апр, 21:29 #270 #726925

>>726914
Увы, но в школьном возрасте подрастающий член общества просто не знает ещё, как жить, и как можно жить иначе. У него тупо нет опыта, знаний, кругозора. Всё зависит от окружения.
Так что возвращайся в /b/, школьник.

Ответы>>726941

25 Апр, 21:45 #271 #726941

>>726925
верно говоришь

25 Апр, 21:47 #272 #726945

>>726443
Я примерно так в 13 призёром стал, правда, вместо алгоритмов пришлось из сообразительности все соки выжимать.

Ответы>>726980

25 Апр, 22:22 #273 #726980

>>726945
так я и говорил, что алгоритмов чувак не очень писал

25 Апр, 22:29 #274 #726989

>>726906
> Приходилось тупо стоять у подъезда
ты идиот чтоле? по крайней мере гулять много интереснее, чем стоять у подъезда.

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

26 Апр, 10:32 #275 #727305

Можно ли обойти связный неорграф без циклов, то есть просто дерево, но без перекрашивания вершин?

Ответы>>727307

26 Апр, 10:33 #276 #727307

>>727305
Обойти, конечно, рекурсивным дфсом

28 Апр, 19:13 #277 #729739

>>706979
Понимаю, что поздно, только щас заметил тред.

Задача дико тупая, не слушай тех, кто сыпет какими-то заумными словами.
У тебя есть граф, вершины это команды, ребро есть если был матч. У тебя у каждой вершины степень ровно 2 по условию. Тогда граф разбивается на циклы (это вроде не очень сложное утверждение например, можно просто начать идти от какой-то вершины по ребрам, по одному ребру пришел, по другому вышел, так как вершин N, рано или поздно ты попадешь в какую-то вершину, где ты уже был. Это может быть только первая вершина с которой ты начал, иначе ты получил вершину степени 3 - ты в нее вошел, вышел, а сейчас еще раз пришел)
Очевидно, что из каждого цикла длины k можно взять не более k / 2 команд. При этом, k / 2 можно взять - просто берешь через одну.
А циклы это компоненты связности. Разбиваешь dfs-ом граф на компоненты связности, считаешь сумму (размер очередной компоненты / 2), если она хотя бы К - то все заебись

Ответы>>729740>>729743

28 Апр, 19:14 #278 #729740

>>729739
Да, деление везде целочисленное.

Алсо, двукратный призер всероса ИТТ, сейчас занимаюсь АСМ-ом в вузике хоть и не столь активно дрочу, как некоторые, задавайте свои ответы

Ответы>>729742

28 Апр, 19:21 #279 #729742

>>729740
Какой вуз? Регион какой хотя бы?

Ответы>>729769

28 Апр, 19:24 #280 #729743

>>729739
Так ровно это же выше и говорили

Ответы>>729769

28 Апр, 19:41 #281 #729769

>>729743
Кек, проебался, увидел только пост с каким-то алгоритмом
>>729742
ДС2

28 Апр, 19:52 #282 #729779

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

Ответы>>729797

28 Апр, 20:19 #283 #729797

>>729779
Берешь, читаешь какую-нибудь книжку/курсы (проси совета в соответствующем треде), параллельно решай задачи из первого блока отсюда, чтобы освоить основы http://informatics.mccme.ru/

Далеко копать в язык не надо (в смысле про всякие слова уровня ООП и прочее), если надо чисто для олимпиадок
На тимусе можешь еще порешать тупенькие задачки.

29 Апр, 22:29 #284 #730826

https://www.youtube.com/watch?v=gNRgvF9x12w&index=15&list=PLtb_PNVHdsV4qZgyqMFC6Tq2wsA0CybJB

Ответы>>731065>>731080>>731153

30 Апр, 11:02 #285 #731065

>>730826
Такой сильной антирекламы я давненько не видел. Если бы не возможность удаленки и миграцию, я бы давно уже дропнул эту хуйню нахуй, но я слишком тупой для сложных вещей и не умею наебывать на даллары.

Ответы>>731067

119 Кб, 731x710

207 Кб, 1253x698

41 Кб, 685x689

44 Кб, 686x701

30 Апр, 11:07 #286 #731067

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

15 Кб, 300x300

60 Кб, 413x604

20 Кб, 320x240

16 Кб, 300x300

30 Апр, 11:24 #287 #731080

>>730826
БЛЯЯЯЯЯЯЯЯЯЯ ПХАХАХАХАХАХАХА ЕБАТЬ УНТЕРМЕНШИ ГДЕ ОНИ ИХ НАБРАЛИ?
ЫТА ВОБЩЕ ЛЕГАЛЬНО???

Ответы>>731083

30 Апр, 11:25 #288 #731083

>>731080
Олимпиадоилита и байтослесари как они есть, не то что эти тупые хипсторы!

Ответы>>731086

30 Апр, 11:30 #289 #731086

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

Ответы>>731090

431 Кб, 848x439

395 Кб, 680x639

30 Апр, 11:35 #290 #731090

>>731086
лол

853 Кб, 866x676

78 Кб, 429x410

30 Апр, 11:40 #291 #731093

39 Кб, 685x689

18 Кб, 183x250

30 Апр, 11:55 #292 #731101

Ответы>>731115>>731138

30 Апр, 12:24 #293 #731115

>>731101
Вообще-то Денис очень талантливый, и многие задачки, где куча текста в виде сказки или фэнтези придумал именно он. Бронзовая медаль на ЧМ асм айсиписи

Ответы>>731122

30 Апр, 12:28 #294 #731122

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

39 Кб, 685x689

35 Кб, 600x600

30 Апр, 13:03 #295 #731138

>>731101

30 Апр, 13:26 #296 #731153

>>730826
Заметили, что достаточно много ребят и топа олимпиадников остались в рашке?

Ответы>>731457

30 Апр, 18:43 #297 #731362

https://www.youtube.com/watch?v=27F46WPVJBs
Второй раунд коде джема уже через 17 минут.

30 Апр, 18:46 #298 #731368

Почему они все такие всратые, пиздец?

30 Апр, 19:27 #299 #731417

Есть A

30 Апр, 20:07 #300 #731457

>>731153
Это пока. Кто знает, что будет дальше.

30 Апр, 20:30 #301 #731460

ИДЕ повисла? Нет времени ждать, быстрее перезапустить! Я наверняка сохранил код, который писал последние полчаса!
Дебил ёбаный.

Ответы>>731468

30 Апр, 20:41 #302 #731468

>>731460
Никогда еще иде не висла. Ты там кучу переполнял чтоле?

Ответы>>731469

30 Апр, 20:43 #303 #731469

>>731468
Ну, ИДЕ это громкое слово в данном случае. Я пишу прямо в Groovy console. Её легко повесить.

30 Апр, 23:47 #304 #731628

>>706325
хехе, творение знакомых засветилось

02 Май, 12:41 #305 #732383

Ваши ставочки на последние два часа Чемпионата Урала?

Ответы>>732398

02 Май, 12:56 #306 #732396

http://acm.timus.ru/monitor.aspx?id=384

02 Май, 12:58 #307 #732398

>>732383
Я болею за команду Ural FU : UF larU, но они не пробьются. Думаю, что на первое место выйдут Ural FU: Dandelion (Меркурьев, Сивухин, Данилюк).

Ответы>>732401>>732414

02 Май, 13:00 #308 #732401

>>732398
Знаю из твоей команды Чаплыгина. Классный парень, но они слабоваты

Ответы>>732402

02 Май, 13:01 #309 #732402

>>732401
Он из моего города, потому и болею за них.

02 Май, 13:23 #310 #732414

>>732398
Что-то Данделионы посасывают

Ответы>>732437

02 Май, 13:38 #311 #732437

>>732414
Они по польской системе, будут сдавать кучу решений в самом конце.

Ответы>>732528

02 Май, 15:40 #312 #732528

>>732437
Много насдавали?

Ответы>>732555

02 Май, 16:10 #313 #732555

>>732528
не фартануло, но все равно крутые

02 Май, 21:48 #314 #732798

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

Ответы>>732800>>733065

02 Май, 21:50 #315 #732800

>>732798
А ты возьми и почитай

03 Май, 10:49 #316 #733065

>>732798
Язык программирования уже знаешь какой-нибудь?

Ответы>>733144>>733265

sage 03 Май, 13:03 #317 #733144

>>733065
Тут ещё и язык нужен?? О_о

03 Май, 13:08 #318 #733148

>>706304 (OP)
>Решишь 500 задач на тимусе - будешь гарантированно красным на кфе
Откуда такая инфа пошла?

726 Кб, 1200x3160

03 Май, 13:09 #319 #733151

03 Май, 16:52 #320 #733265

>>733065
Изучаю С++

Ответы>>733337

03 Май, 18:42 #321 #733337

>>733265
Как ты его изучаешь?

Ответы>>733390

03 Май, 19:45 #322 #733390

>>733337
По книге Стенли Б. Липпмана, Жози Лажойе, Барбары Э. Му "Язык программирования C++. Базовый курс". До этого опытов с программированием почти не имел

Ответы>>733393

03 Май, 19:46 #323 #733393

>>733390
Ты школьник?

Ответы>>733399

03 Май, 19:49 #324 #733399

>>733393
первокурсник

06 Май, 03:38 #325 #735642

>> Для проведения эксперимента надо выбрать из N имеющихся приборов только три. Для этого выполняют следующую операцию - если в группе приборов больше трех, то их нумеруют и выбирают одну из групп: с четными или нечетными номерами. Операцию повторяют до тех пор, пока в группе не останется три или менее приборов. Если их остается ровно три, то они и берутся для эксперимента.Требуется написать программу, которая подсчитает количество способов такого выбора приборов.Как сделать это за 1 секунду при 1 <= N <= 2147483647. Не могу уложиться в эти условия.

Ответы>>735737>>736219

06 Май, 10:18 #326 #735737

>>735642
http://ideone.com/iAPf6W

85 Кб, 941x590

06 Май, 13:05 #327 #735863

Ребята помогите тупому с задачкой пожалуйста

Ответы>>735933

06 Май, 14:16 #328 #735933

>>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]?)$

Ответы>>735937>>735940

06 Май, 14:22 #329 #735937

>>735933
Спасибо, но мы на курсе не дошли до такого, надо как то через циклы if for while getline и функцию stoi

Ответы>>735947>>735954

06 Май, 14:23 #330 #735940

>>735933
Буду благодарен если напишешь примерно, что у тебя в коде написано, чтобы я погуглил

Ответы>>737612

06 Май, 14:30 #331 #735947

>>735937
Ты язык не написал.

Ответы>>735956

06 Май, 14:33 #332 #735954

>>735937
Хуевый у тебя второй курс
Мимо-МФТИшник

Ответы>>735956

06 Май, 14:36 #333 #735956

>>735947
>>735954
Прохожу курс Густокашина по С++ на степике

Ответы>>735996

06 Май, 15:20 #334 #735996

>>735956
А олимпиадное программирование тут причём? http://stackoverflow.com/a/10200328

Ответы>>736104>>736105

06 Май, 17:40 #335 #736104

>>735996
Да потому что эта задачка вполне подходит, я на тимусе решал, там есть похожие по сути.

06 Май, 17:44 #336 #736105

>>735996
Густокашин сам крутой олимпиадник, вот и курсе своем дает задачки такие

06 Май, 19:35 #337 #736219

>>735642
Вот оптимизированный вариант: https://ideone.com/ROocYY

08 Май, 14:53 #338 #737611

Вот это норм олимпиадка, не то что ваши днище-ацмы
https://meduza.io/feature/2016/05/03/my-nachinaem-nashe-mochilovo

Ответы>>737615>>737622

08 Май, 14:55 #339 #737612

>>735940
Нынешние студенты не знают про регулярки? Значит я за свое будущее спокоен.

Ответы>>737620

08 Май, 15:01 #340 #737615

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

Ответы>>737619

08 Май, 15:09 #341 #737619

>>737615
>а тут какая-то закрытая система

Ответы>>737623

08 Май, 15:11 #342 #737620

>>737612
Ты дебил блять какие студенты, месяц назад начал проходить курс, до этого о проге не слышал даже

08 Май, 15:14 #343 #737622

>>737611
CTF ни чем не круче ACM

Ответы>>737624

08 Май, 15:14 #344 #737623

>>737619
Блджад, enter случайно отправил.
Короче, по моему скромному мнению, даже школьные олимпиадки это отчасти закрытая система. Потому что у ололомпиадников есть свои "клубы", есть тренера, короче мафия задротов, и типа всеобщая олимпиада сводится к эстафете "между своими".
Бомбит например с того факта, что в обоссаном ацм победителем уже хуй сколько раз был летмо, хотя по мне говношарага говношарагой. Подебителей надрачивают тренерки, причем только из числа отборных задротов, а все остальные желающие сосут хуй.

Ответы>>737625>>739327

08 Май, 15:14 #345 #737624

>>737622
>ни чем
Иди интегралы под водовку решай, второкур.

08 Май, 15:16 #346 #737625

>>737623
В итмо на тренировки могут приходить все желающие, всему научат. Я сам, как школьник, тренируюсь у Маврина, просто в начале учебного года кинул анкетку и все

Ответы>>737629

08 Май, 15:30 #347 #737629

>>737625
>как школьник
Ты собираешься поступать по результатам олимпиадки?

Ответы>>737639

08 Май, 16:10 #348 #737639

>>737629
Да

10 Май, 15:58 #349 #739327

>>737623
>ИТМО
Не надо тут, два года назад СПбГУ затащил, например

Ответы>>739630

10 Май, 19:42 #350 #739630

>>739327
Да много годных универов, ИТМО вывозит еще за счет того, что туда больше всего задротов олимпиадников съзжается, причем не только из Рашки. Самарский вуз сильный, УрФУ тоже, ПермГУ тоже золото брали

Ответы>>739631

10 Май, 19:45 #351 #739631

>>739630
Ну да, только в тот же СПбАУ перевелся на первый курс со второго ИТМОшник, а еще перешел (в прошлом году) вот как раз победитель межнара из СПбГУ.
Так что, возможно, это не надолго, хех

Ответы>>739632

10 Май, 19:47 #352 #739632

>>739631
Лол, в ау вообще не особо приветствуют занятия асмом, потому что отнимает много времени и сил, а программа там и без того сильная.

Мимо имею друзей и на кт, и в ау, и в спбгу, и в урфу и в пермгу

Ответы>>739633>>739646

10 Май, 19:55 #353 #739633

>>739632
Ты уже закончил универ?

Ответы>>739634

10 Май, 19:58 #354 #739634

>>739633
Еще не начинал

10 Май, 20:07 #355 #739646

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

11 Май, 20:14 #356 #740633

А тут у всех вас есть кружки, тренера, команды? Есть такие кто сам в одиночку с помощью интернета превозмогает?

Ответы>>740641

11 Май, 20:29 #357 #740641

>>740633
На кфе видел посты таких. Всякие I_Love_Tanya_Romanova

Ответы>>740659>>745154

11 Май, 20:43 #358 #740659

>>740641
>I_Love_Tanya_Romanova
Почитал его блог, какой- то монстр просто.

Ответы>>745339

11 Май, 21:09 #359 #740698

Ало, здравствуйте, это тред специальных олимпиад?

Ответы>>740726

11 Май, 21:25 #360 #740726

>>740698
Да, вы пишите на Ruby?

Ответы>>740838

11 Май, 22:45 #361 #740838

>>740726
Гхм... нет. Вы извините, но, может быть, я номером ошибся? Это точно тред специальных олимпиад, а не клуб гей-знакомств?

15 Май, 13:00 #362 #744073

Ну что, кто на ЯндексАлгоритм зарегался? Как оцениваете шансы? Трудно ли попасть в топ-512?

Ответы>>744287

15 Май, 17:09 #363 #744287

>>744073
Впервые услышал про него. Попробую, наверное.

15 Май, 18:02 #364 #744329

Посмотрел разминочный раунд и охренел от сложности задач на 1.5 часа времени.

Ответы>>744333>>744821>>745228

15 Май, 18:08 #365 #744333

>>744329
А чем ты на работе занимаешься?

16 Май, 07:26 #366 #744821

>>744329
а чем они там сложные?

16 Май, 18:09 #367 #745154

>>740641
Он из ЛНУ, чувак в олимпиадках с восьмого класса (сейчас он на шестом курсе). Потом в ЛНУ учился, тренер - Василь Білецький, он тоже брал золото ACM в 2008 году.
Так что там не интернетом, а благодаря хорошей тусовке в том числе. Хотя решал он дофига, спорить не буду

Ответы>>745280

16 Май, 19:23 #368 #745228

>>744329
Ты про яндекс.алгоритм? Последние тяжелые. А первые то вообще херня.

Ответы>>745261

16 Май, 19:54 #369 #745261

>>745228
Ну вот шашматы, например. Там целую игру надо закодить с перебором вариантов. На все это дается 1:40 времени. Может, конечно, вы тут все чемпионы по скоростному набору кода, но мне нужно полдня чтобы такое закодить и отладить. Ты пробовал эту задачу делать? Сколько времени потратил?

Ответы>>745268

16 Май, 20:02 #370 #745268

>>745261
Что там было? Сейчас только какую-то хуйню "A+B" выводит, не вижу нигде шашмат.

Ответы>>745271

16 Май, 20:03 #371 #745271

>>745268
https://contest.yandex.ru/algorithm2016/contest/2497/problems/C/

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

Игра шашматы происходит на стандартной доске 8 × 8: вертикали пронумерованы буквами от a до h, горизонтали — числами от 1 до 8, поле a1 — чёрное, каждое чёрное поле может граничить по стороне только с белыми, и наоборот.

Игроки ходят по очереди. У белых одна фигура — шахматный конь, у чёрных — обычная шашка. Фигуры делают ходы в соответствии с правилами своих игр. А именно, шашка изначально располагается на чёрном поле и может передвигаться только по чёрным полям, уменьшая номер горизонтали на 1, номер же вертикали может как увеличиться на 1, так и уменьшиться; разумеется, выход за края доски запрещён. Конь ходит на одну клетку в некотором выбранном направлении (горизонтальном или вертикальном) и на две в перпендикулярном ему; при этом начальная и конечная клетки хода должны находиться на доске.

Правила, по которым определяется победитель, таковы:

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

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

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

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

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

Ответы>>745303>>745533

16 Май, 20:21 #372 #745280

>>745154
>Так что там не интернетом, а благодаря хорошей тусовке в том числе
Двачую. Если не связи со всякими ололо-тренерами и прочей петушнёй, то хотя бы иметь товарища, который подскажет, что и как учить, какую литературу читать. Я в 8 классе в одиночку пытался решать задачи и обломался на них по полной, без соответствующих знаний было СЛОЖНА и страшно.

16 Май, 20:47 #373 #745303

>>745271
Я сделал первые две за 8 минут, и лёг спать, так как там только одну достаточно, чтобы пройти.
для тренировок есть кодфорсес.
Шашматы -- просто написать перебор. Не так долго и писать, ведь всего две фигуры. Наложить ограничения. Делать проверку на победу. запихать это всё в рекурсию. Посмотреть на дерево. Вывести ответ.

16 Май, 21:35 #374 #745339

>>740659
А что там такого-то?
http://codeforces.com/blog/entry/7162
Чувак не знает про передачу параметров по ссылке.
http://codeforces.com/blog/entry/13207
Чувак не знает про ненормализованные даблы и не в состоянии нагуглить.

Остальное - приглашения на какие-то конкурсы.

Ответы>>745654

16 Май, 21:41 #375 #745343

https://mitpress.mit.edu/sites/default/files/Chapter 26.pdf
26-3
Это CLRS.
Скиньте пожалуйста пример решения этой или концептуально похожей задачи. Ну или на пальцах поясните, я обучаемый.

Ответы>>745567

17 Май, 06:44 #376 #745533

>>745271
Ща попробую.

Ответы>>745541

17 Май, 07:30 #377 #745541

>>745533
Ну вот что получилось. Прогнать тесты не могу потому что не зареган. На это ушло около 45 минут.
https://ideone.com/Sra0zX

Ответы>>745761>>745766

17 Май, 08:34 #378 #745567

>>745343
Это не то, что тебе нужно. Я тебе уже в ньюфаг треде намекал, что тебе надо собрать ранец
https://ru.wikipedia.org/wiki/Задача_о_ранце

Ответы>>746065

17 Май, 11:27 #379 #745654

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

17 Май, 13:37 #380 #745761

>>745541
Это вместе с отладкой, или ты просто написал и все?

Ответы>>745769

17 Май, 13:39 #381 #745764

Хотел послать твое решение, но там груви не принимается.

17 Май, 13:44 #382 #745766

>>745541
https://ideone.com/3P69JN
e4 e3 white -> white wins
неправильно, должно быть блэк

Собственно, о чем я и говорил. 45 минут ушло на написание этого, потом еще час на отладку, вот и закончилось время. А это только третья задача.

Ответы>>745811

17 Май, 13:46 #383 #745769

>>745761
Написал и всё, проверил что запускается. Не имею возможности потестить.

17 Май, 14:27 #384 #745811

>>745766
Ну вообще у меня на диске пылится готовое решение для https://www.e-olymp.com/ru/problems/32
Так что в контесте я бы взял его за основу и поменял только минимум - разницу между пешкой и шашкой. Получилось бы быстрее.
И насчёт часа на отладку ты загнул. Так редко бывает с олимпиадными задачками при грамотном подходе к дебагу.

17 Май, 19:07 #385 #746065

>>745567
Во-первых, перестань меня преследовать.
Во-вторых, Кормен лучше знает что нужно, а что ненужно
В-третьих, ты нихера не условия задачи.

Собственно, с третьего пункта мне нужно было и начинать.

Ответы>>746185

17 Май, 21:11 #386 #746185

>>746065
Ну давай, расскажи мне как в твоей жизни встала задача поиска максимального паросочетания в двудольном графе.

Ответы>>746236>>746239

17 Май, 21:44 #387 #746236

>>746185
Приходит такой прафесар и говорит, кароч)) вот вам задача, кто не решит - тому пизда.

17 Май, 21:45 #388 #746239

>>746185
Альзо, если двудольный граф это bipartite graph, то ты опять пальцев в жопу.
При всем уважении, не мучай себя.

19 Май, 16:24 #389 #747688

Ну что тут есть олимпиадники с Пхукета?

Ответы>>747692

19 Май, 16:32 #390 #747692

>>747688
Не удивлюсь, что Бардашевич двачует. Правда, явно не тут. Ближе к желтым колобкам

Ответы>>747792

19 Май, 18:34 #391 #747792

>>747692
Лол, а что так?

21 Май, 18:41 #392 #749539

>>749520
Сначала на листочек выписывается строка. Игроки ходят по очереди и на каждом ходе можно стереть один символ из начала или конца строки. Побеждает игрок, перед ходом которого строка была палиндромом. Палиндромом называется строка, которая читается одинаково слева направо и справа налево.
Определите, какой игрок победит при оптимальной стратегии обоих игроков.

620 Кб, 2091x317

21 Май, 19:36 #393 #749623

Ответы>>749628>>749633

21 Май, 19:39 #394 #749628

>>749623
Что за сложный мемес?

21 Май, 19:42 #395 #749633

>>749623
Так это тренер.

22 Май, 20:02 #396 #750634

Ребяты. У меня есть 30 задач на тимусе, и целое лето впереди. Но я сам безвольное хуйло. Никто не хочет со мной в соревновательной, менторской или иной форме порешать это дело?

Ответы>>751251>>751622>>751884

23 Май, 10:24 #397 #751251

>>750634
> соревновательной
чуваки с codeforces или topcoder очень хотят. если дрочишь на рейтинг, то добро пожаловать туда. мне более-менее помогало(это единственное место кроме олимпиадок, где я решал задачи). правда призером всероса так и не стал

Ответы>>751496>>751628

23 Май, 15:42 #398 #751496

>>751251
Контесты проходят не достаточно часто, чтобы быть постоянной тренировкой

Ответы>>751919

726 Кб, 1200x3160

23 Май, 17:22 #399 #751622

>>750634
у меня 25 задач на тимусе и я вообще не шарю, держи гайд от великого мастера

Ответы>>751629

23 Май, 17:27 #400 #751628

>>751251
>правда призером всероса так и не стал
Чем сейчас занимаешься? Куда поступил/будешь поступать?

Ответы>>751911

23 Май, 17:27 #401 #751629

>>751622
Да, спасибо. Но это я уже раз четвертый читаю.

Ответы>>751669

23 Май, 17:54 #402 #751669

>>751629
Знаешь Мишу?

Ответы>>751674

23 Май, 17:57 #403 #751674

>>751669
Рубинчика? Увы, нет

Ответы>>784436

23 Май, 20:42 #404 #751884

>>750634
А ты как занимаешься? Какой язык выучил?

Ответы>>751912

23 Май, 21:04 #405 #751911

>>751628
> Чем сейчас занимаешься?
страдаю хуйнёй, cf пишу, ну и соревнования типа codejam, rcc

> Куда поступил/будешь поступать?
видимо, в итмо(олимпиадки 1 уровня есть). хотелось бы в мгу ибо корочка пижже, но егэ сдать хорошо если на подтвержение в итмо смогу

23 Май, 21:05 #406 #751912

>>751884
Самый жесткий буст получил в школе. Нам преподавала сестра одного из чемпионов ACM в прошлом, менее успешная. Это было в 8 классе. Потом на кружке при ИТМО пересел на кресты, с тех пор только стал более уверенным

23 Май, 21:10 #407 #751919

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

Ответы>>751924

23 Май, 21:14 #408 #751924

>>751919
М-м-максимум уныло. И слишком велик соблазн подсмотреть тесты, почитать разбор или чужое решение.

Ответы>>751935

23 Май, 21:18 #409 #751935

>>751924
не было такого. ваще есть 3 случая:
1) эта фигня для самолюбования а ты показываешь что ты слабый -> провал
2) эта фигня просто чтобы порешать интересные таски -> нафиг читерить если цель -- решить?
3) остальное -> нафиг ваще решать?

Ответы>>751942

23 Май, 21:21 #410 #751942

>>751935
Попеременно испытываю все три предпосылки

Ответы>>751949

23 Май, 21:24 #411 #751949

>>751942
ок, тогда как может возникнуть желание считерить? в любом случае оно нерационально

Ответы>>751997

23 Май, 21:44 #412 #751997

>>751949
Наверное, акцептед доставляет больше чем весь процесс. Или это временное, или мне не место в олимпиадном движении

Ответы>>752015

23 Май, 21:48 #413 #752007

https://www.hackerrank.com/ Олимпиач, что скажешь про эту помйку?Для новичка порешать задачки пойдет?

23 Май, 21:55 #414 #752015

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

31 Май, 02:31 #415 #758124

Есть два прямоугольника, один размера a x b, другой размера c x d, напишите функцию, которая будет возвращать true если второй прямоугольник можно поместить внутри первого, иначе false.

114 Кб, 720x960

31 Май, 06:57 #416 #758150

Немножко пищи для ума страждущим:

Есть массив уникальных дат месяца, отсортированный по возрастанию, на которые вам требуется купить билет t[0..30], где t = [1..30]. И есть следующие типы билетов:
1) Билет на 1 день за 2 рубля;
2) Билет на 7 дней за 7 рублей;
3) Билет на 30 дней за 25 рублёй.

Напишите программу, которая поможет пидорахе сэкономить на проезд в текущем стабильном положении в стране.

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

Пример [1, 2, 4, 5, 7, 29, 30] = 11.

Ответы>>759132>>760520>>760540

01 Июн, 11:28 #417 #759132

>>758150
Что с этим столбом? Он вкусняшкой обмазан?

Ответы>>759150

01 Июн, 12:07 #418 #759150

>>759132
Жить захочешь и не так раскорячишься такие вкусняшки найдешь.

03 Июн, 09:54 #419 #760520

>>758150
Очевидная динамика очевидна.

03 Июн, 11:00 #420 #760540

>>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) рубля(-ей)

Осталось выделить последовательности

Ответы>>760596

03 Июн, 13:40 #421 #760596

>>760540
Дэбил, зачем пытаешься жадник придумать. Много таких по весне оттаяло, в этой задаче думать вообще не надо, пишешь динамику и всё. Уметь отличать задачи на жадник от задач на динамику – крайне важный скилл.

Ответы>>760609>>760615

03 Июн, 13:56 #422 #760609

>>760596
Мсье, а как вы определили, что тут лучше динамическим программированием решить?

Ответы>>760611

03 Июн, 13:58 #423 #760611

>>760609
Определил из того, что задача стандартная и обычной линейной динамикой решается в два счёта.

Ответы>>760616

03 Июн, 14:05 #424 #760615

>>760596
>Уметь отличать задачи на жадник от задач на динамику – крайне важный скилл.
Подкинь чтива на этот счёт.

Ответы>>760619

03 Июн, 14:06 #425 #760616

>>760611
реши

Ответы>>760617

03 Июн, 14:08 #426 #760617

>>760616
Решил

Ответы>>760618

03 Июн, 14:09 #427 #760618

>>760617
покеж

Ответы>>760627

03 Июн, 14:11 #428 #760619

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

Ответы>>760665

03 Июн, 14:21 #429 #760627

>>760618
Нечего показывать, мне решение и так очевидно.
Могу на пальцах: мы по каждому дню от него вперёд проставляем оптимальные варианты. Пусть сегодня 0 день, тогда мы смотрим, есть ли поездки в день 1. Если есть, то ставим на 1 день 2 рубля, иначе 0. Смотрим на поездки с 1 по 7, если есть, то ставим в 7 7 рублей, иначе 0. Дальше принцип понятен, думаю, когда я говорю "ставим", то имею в виду взятие минимума из нашего промежуточного варианта и того, который уже для этого дня есть. Изначально 0 дню ставим 0, остальным INF.
По тесту из условия, на 0 дне в 7 ячейку проставится 7, дальше эта семёрка будет ползти до 28 дня, откуда два раза прибавится 2.

Ответы>>760628>>771373

03 Июн, 14:22 #430 #760628

>>760627
Чтобы решение было за линию, наличие поездок на промежутке проверяется с помощью префиксных сумм.

1639 Кб, Webm

03 Июн, 14:31 #431 #760629

03 Июн, 15:49 #432 #760665

>>760619
Под жадником это имеется ввиду?
https://ru.wikipedia.org/wiki/Жадный_алгоритм

Ответы>>760759

03 Июн, 17:51 #433 #760759

>>760665
Не, вроде вот этот
https://otvet.mail.ru/question/3504695

71 Кб, 900x355

16 Июн, 21:30 #434 #771373

>>760627
Что-то как-то сложны ты на 2-х пальцах объясняешься.
Вот что у меня вышло:
https://github.com/arbitrary-dev/problem/blob/master/ticket/src/main/java/com/problem/ticket/Ticket.java

Ответы>>773854>>773857

16 Июн, 23:51 #435 #771543

Сосаны, с каких лет лучше начинать готовиться к олимпиаде?

Ответы>>771699>>774003

17 Июн, 05:34 #436 #771699

>>771543
К жизни лучше подготовься, придурок.

Ответы>>771981

17 Июн, 14:19 #437 #771981

>>771699
Успокойся, сопи в две дырки ровно

19 Июн, 05:33 #438 #773854

>>771373
Ок, просто мне больше нравится решать задачи более общими методами. Вот тут ты напрямую пользуешься тем, что один из билетов всего на 1 день, а другой сразу на 30, то есть на весь промежуток. Давай тогда дадим тебе промежуток в 100000 дней и 10 каких-нибудь случайных чисел как длительности билетов. Тогда ты придёшь ровно к тому же, что я и написал, иначе пальцы отвалятся случаи разбирать.

19 Июн, 05:57 #439 #773857

>>771373
http://paste.ofcode.org/8ErWwmMWpEa9JJksEAbhHp вот, в общем, короткое и более мощное решение.

19 Июн, 06:12 #440 #773859

>>706304 (OP)
Секунду, так писать на 1С?

19 Июн, 10:53 #441 #774003

>>771543
после 6 класса

21 Июн, 12:54 #442 #775884

http://acm.timus.ru/problem.aspx?num=1406 хелпп

Ответы>>778212>>778557

23 Июн, 18:17 #443 #778212

>>775884
У тебя сколько задач решенных?

Ответы>>779409

54 Кб, 536x757

23 Июн, 21:55 #444 #778407

Как решать?

Ответы>>778520

24 Июн, 02:05 #445 #778520

>>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.

Ответы>>778522

24 Июн, 02:07 #446 #778522

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

Ответы>>778525

24 Июн, 02:18 #447 #778525

>>778522
В пузырьке не соседние свапаются.

Ответы>>778537>>778538

24 Июн, 02:36 #448 #778537

>>778525
Ты хоть раз пузырёк писал?

24 Июн, 02:36 #449 #778538

>>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

Ответы>>778544

24 Июн, 03:01 #450 #778544

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

Ответы>>778546

24 Июн, 03:09 #451 #778546

>>778544
Вопрос в другом: зачем ты вообще писал сортировку?

Ответы>>778547

24 Июн, 03:10 #452 #778547

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

Ответы>>778548

24 Июн, 03:12 #453 #778548

>>778547
Помню полулегенду, что Гена пишет qsort на паскале за 40 секунд.

Ответы>>778549

24 Июн, 03:13 #454 #778549

>>778548
Знаю девочку, которая знает Гену лично. Замеряли они это дело как-то. Там было что-то чуть больше двух минут, если мне память не изменяет

Ответы>>778550

24 Июн, 03:15 #455 #778550

>>778549
Зря ему про плюсы рассказали, мог бы в книгу рекордов Гинесса попасть.

24 Июн, 04:27 #456 #778557

>>775884
https://ideone.com/Ut6YQW

Ответы>>778998>>779410

24 Июн, 20:49 #457 #778998

>>778557
как ты перешел на язык Груви и почему?

Ответы>>779334

25 Июн, 11:01 #458 #779334

>>778998
На работе заставили выучить. Там был джава проект, но нужно было и скрипты писать. Нравится что есть опциональная типизация.

25 Июн, 14:14 #459 #779409

>>778212
0
мне на пересдачу дают одну из них я сижу туплю.
вру одна решена Козла пустили в Огород
так же есть пак решении на эти задачи?

25 Июн, 14:14 #460 #779410

>>778557
это блять что такое?

25 Июн, 17:53 #461 #779632

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

Ответы>>779636

25 Июн, 17:54 #462 #779636

>>779632
Как это, обычно как раз наоборот, в задачке абсолютно чётко сказано, что от тебя хотят, с ограничениями и примерами. А вот что бывает в типичных ТЗ...

25 Июн, 18:02 #463 #779643

А если допустим 1000 таких задачек решить и на github выложить, то работу можно так найти?

Ответы>>779646>>779647

25 Июн, 18:04 #464 #779646

>>779643
Нуу, нет, но большой рейтинг на кодфорсах или топкодере это плюс на собеседовании во всякие яндексы.

Ответы>>779647>>779654

25 Июн, 18:05 #465 #779647

>>779643
>>779646
Вот вакансия, где пишут про олимпиадки, например http://www.aimtech.com/vacancies/C++ Developer/

25 Июн, 18:08 #466 #779649

>>710693
Мне бы хоть три штуки из предыдущих google code jam решить, дак я и одну задачку не потяну.
https://code.google.com/codejam/contest/32004/dashboard
Её за два часа решают, я за два часа даже не разберусь что нужно от меня.

25 Июн, 18:19 #467 #779654

>>779646
Буду старые задачки google code jam решать и github выкладывать

Ответы>>779656

25 Июн, 18:22 #468 #779656

>>779654
Попробуй, конечно, но рейтинг намного более важен.

Ответы>>779658>>779659

25 Июн, 18:27 #469 #779658

>>779656
Фигасе из Россси только 255 человек в гугл код джам участвовали. Вообще программистов нету.

Ответы>>779660>>781220

25 Июн, 18:29 #470 #779659

>>779656
Мне любая работа программистом пойдет. Лишь бы задачи поставленные решать, в топ 500 мне хоть тресни не войти.

25 Июн, 18:29 #471 #779660

>>779658
Как посчитал? Если учесть, что на квалах в этом году было больше 27 тысяч человек, то 255 как-то мало звучит.

Ответы>>779665>>779666

25 Июн, 18:43 #472 #779665

>>779660
https://www.go-hero.net/jam/16/languages/Python#problems
254 contestants может я конечно что то не правильно понимаю

Ответы>>779671

25 Июн, 18:44 #473 #779666

>>779660
А, это только 255 питонистов, остальных больше.

Ответы>>779671

25 Июн, 18:51 #474 #779671

>>779666
>>779665
> 988
https://www.go-hero.net/jam/16/regions

Ответы>>781230

27 Июн, 15:03 #475 #781220

>>779658
Просто если бы участвовал на 1 человек больше, то было бы переполнение и счёт пошёл бы снова с нуля.

27 Июн, 15:26 #476 #781230

>>779671
> https://www.go-hero.net/jam/16/name/Louise.de.La.Valliere
Ахуеть. Помогите найти этого психа. Хочу на гитхаб его посмотреть.

29 Июн, 19:10 #477 #783371

Вы юзаете std::thread в своих задачках?

Ответы>>783912>>785671

74 Кб, 703x761

29 Июн, 21:01 #478 #783524

Как решать?

Ответы>>783688

29 Июн, 22:37 #479 #783688

>>783524
http://e-maxx.ru/algo/bipartite_checking

30 Июн, 04:02 #480 #783912

>>783371
нет. Даже не знаю, что это

Ответы>>783913

30 Июн, 04:05 #481 #783913

>>783912
И как успехи?

Ответы>>783914

30 Июн, 04:08 #482 #783914

>>783913
Уверенный первый див пруфов не будет

30 Июн, 18:08 #483 #784402

>>706313
считываешь все запросы сначала, а потом одним проходиком отвечаешь на все

30 Июн, 18:23 #484 #784415

>>726314
решай задачи прошлых контестов на кф. Там и разборы есть

30 Июн, 18:38 #485 #784436

>>751674
Еще Копелович есть, он классный

Ответы>>784459

30 Июн, 18:56 #486 #784459

>>784436
Копелиович. У Рубинчика одноклассник асmщик учился с Копелиовичем, потом его вроде отчислили.

30 Июн, 18:58 #487 #784463

Вот смотрю я задачи на тимусе и вижу как растет сложность с годами, див2А сложнее чуть ли не половины задач тимуса

Ответы>>784725

30 Июн, 22:40 #488 #784725

>>784463
Сколько задач на тимусе у тебя?

Ответы>>785379

01 Июл, 19:16 #489 #785379

>>784725
39

Ответы>>785632

02 Июл, 02:25 #490 #785632

>>785379
Но это даже не близко к половине

02 Июл, 07:34 #491 #785671

>>783371
Есть очень мало контестов, типа Distributed Google Code Jam, где он может пригодиться. В остальных случаях процессорное время считается, очевидно, как сумма всех тредов, так что оверхед на управление тредами только навредит.

02 Июл, 21:16 #492 #786159

Алгоритмотреда нет, спрошу здесь.

Вот есть следующая задача.
Дана плоскость, есть несколько точек на ней (до 500), с не очень большими координатами (от 0 до 50, вещественные). Надо найти для каждой пары точек кратчайший путь между ними.
Плоскость (можно рассматривать только квадрат 50х50) поделена на единичные квадраты, каждому квадрату сопоставлен какой-то вес. Соответственно, длины всех отрезков внутри квадрата домножаются на его вес.
Не обязательно точное решение (я не уверен, что оно есть), но очень хорошее приближение желательно, да и чтобы работало быстро.

Я пробовал сделать следующее: покрыть большой квадрат сеткой, построить граф на этом, соединить исходные точки с ближайшими вершинами сетки и запустить 500 раз (количество точек) Дейкстру (которая с кучей)
Но это работает медленно при сколько-нибудь большом размере сетки, да и хочется таки сделать более хорошее приближение. Всякие A-star для увеличения скорости тут разумеется не подходят - мне надо от точки искать расстояние до всех, а не до одной, то есть все равно почти весь граф придется обойти

Ответы>>786249

02 Июл, 22:17 #493 #786249

>>786159
Какой ты ещё граф делал? Судя по твоему условию, тут всё намного хитрее. То есть минимальное расстояние не факт, что прямая, так как разные веса у секторов. Я всё правильно понял? Тогда физическая аналогия -- свет в материале с разной проницаемостью. То есть минимальное расстояние до заданной точки выражается через тригонометрию. И перебором по всем точкам O(n^2). Можно ли быстрее? Надо думать. Ещё такой вопрос -- какой вес на грани квадрата? То есть из одного сектора перпендикулярно дохожу до другого, а дальше двигаюсь вдоль грани: какой в итоге вес?

Ответы>>786257>>786262

02 Июл, 22:21 #494 #786257

>>786249
Да, конечно не прямая, иначе в чем задача, лол. Но, тем не менее, это какая-то ломаная с не очень большим числом отрезков
Считаем, что по грани совсем вдоль нельзя идти - либо ты с одной стороны (на eps), либо с другой.

А как выражается через тригонометрию, я не понимаю вот чего-то. Ну то есть явное аналитическое уравнение у меня не получилось написать. Для случая если надо перебраться в какую-то точку в соседнем квадрате понятно как считать еще (да и то, если оптимальныей путь не идет как-то в обход), а в общем случае хуй поймет.

Ответы>>786262

02 Июл, 22:23 #495 #786262

>>786249
>>786257
>какой граф
Эм, ну в смысле? Я ж сказал: покрываю все мелкой сеткой с небольшим шагом (например, 1/3, если меньше, то дольше работает), вершины - узлы сетки и исходные точки, ребра - отрезки между соседними точками сетки (по всем 8 направлениям), веса считаются легко

Ответы>>786278

02 Июл, 22:31 #496 #786278

>>786262
А, понял про граф. Но погрешность же большая.

Ответы>>786341

02 Июл, 23:02 #497 #786341

>>786278
Ну так да, я и говорю, что хочется как-то оптимальнее. А не очень понятно как, не увеличивая плотность сетки

Ответы>>786479

03 Июл, 03:22 #498 #786479

>>786341
Расскажи подробнее про требуемую точность и производительность.
Сколько есть времени на анализ плоскости, и сколько раз после этого надо определять расстояния между точками на ней?

Я бы увеличил количество точек, но оставил только точки в фиксированных позициях на границах квадратов.
Предрассчитываем таблицу расстояний между точками с фиксированными позициями на сторонах квадрата, чтобы потом забыть про тригонометрию. Цена ребра равна соотв. расстоянию на коэффициент квадрата.
Дальше группируешь квадраты в блоки 4x4, строишь для каждого блока матрицу расстояний между всеми его внешними точками (можешь начать с расстояний между внутренними точками квадратов 2x2, потом между их внешними точками, а потом объединить четыре 2x2 в один 4x4 и повторить процесс). Можно придумать оптимизации исходя из геометрического смысла. Например путь из (0.1, 0.1) в (2.1, 0.1) точно не проходит через (1.1, 0.9).
Как пользоваться этим я думаю понятно. Но не забывай, что кратчайший путь между точками внутри блока может выходить за пределы блока.

04 Июл, 19:09 #499 #787900

АХТУНГ ВСЕМ ЗАДРОТАМ У ВАС УНИКАЛЬНЫЙ ШАНС ПРИМЕНИТЬ СВОИ ЗНАНИЯ НА ПРАКТИКЕ
Есть 1 взвешенный, неориентированный граф. Он разделён на 2 подграфа так что все его вершины входят в один из двух подграфов. При этом оба эти подграфа состоят только из одной компоненты связанности. У этого графа веса имеют не вершины, а рёбра. Ценой графа называется сумма весов всех ребер которые соединяют 2 подграфа. Разрешается переносить любую вершину подграфа в другой подграф кроме некоторых закреплёных. Закреплёные вершины всегда соединенны рёбами только с вершинами своего подграфа и названы заранее. Задача минимизировать цену графа так чтобы количество вершин принадлежащих каждому подграфу осталось неизменным и подграфы остались состоять из одной компоненты связанности.

Ответы>>787981>>787988>>788264>>791373

04 Июл, 20:33 #500 #787981

>>787900
Ограничения на размер графа?

04 Июл, 20:42 #501 #787988

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

Ответы>>788176

05 Июл, 01:38 #502 #788176

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

Ответы>>788407

05 Июл, 06:08 #503 #788264

>>787900
Щас подумал про закреплёные вершины. Они не нужны исли в клнце просто одну проверкц добавить. Может так задача проще станет? Почитал про разрез. Мне его минимального веса надо и размеры подграфов не должны поменяться. Тогда нужно найти минимальный разрез такой алгоритм ведь есть? пока он не будет делить граф правильно искать следующий за ним по размеру разрез. Такое возможно?

Ответы>>788407

05 Июл, 11:59 #504 #788407

>>788264
Ну ты сам подумай, что сказал. Фактически ты перебираешь разрезы, а их экспонента (все возможные разбиения на два множества, 2^V)
>>788176
Ну от твоего частного случая до общего уже очень близко. Если подставим кратные рёбра, то получим дискретный случай.

05 Июл, 13:24 #505 #788449

Ахтунг, ты слишком неопределённо поставил задачу. В общем случае она NP-сложная. Если соединить фиксированные вершины каждого подграфа рёбрами бесконечного веса со своей вершиной (чтобы гарантировать, что фиксированные вершины окажутся в разных подграфах), а также добавить две вершины, соединённые со всеми остальными рёбрами нулевого веса (это возможный частный случай входных данных, при котором связность подграфов гарантирована), то получаем задачу о fixed balance edge cut, которая известна NP-сложностью.
Но если знать, например, что вершин не больше сотни, или что максимальная степень графа невысокая, или что он разреженный, или что он планарный, или что требуется приближённое решение, то можно подумать об оптимизациях.
Есть ли у задачи физический смысл, типа раскидывания компонентов по сторонам платы, или серверов по датацентрам?

Ответы>>788646>>791372

05 Июл, 17:10 #506 #788646

>>788449
>что вершин не больше сотни
2к максимум. У каждой вершины от 2 до 6 рёбер.
>требуется приближённое решение
Ну в крайнем случае можно и приближённое. Или сделать вес всех рёбер 1.
>Есть ли у задачи физический смысл
Его в некоторых случаях нужно будет в игре применять. Один из них минимизация длины линии фронта или раздел границы после войны. Какой алгоритм там теперь я не знаю, но он либо оставляет какие-то полуострова врезающееся в чужую территорию там где были прорывы, либо анклавы там где были котлы.

Ответы>>789363

05 Июл, 21:19 #507 #788906

http://acm.timus.ru/status.aspx?author=41395
смотрите с какой скоростью пацан решал задачки, причем сложные

Ответы>>788969

05 Июл, 21:55 #508 #788969

>>788906
Хм, это контест с Петрозаводских сборов. Либо он в числе его авторов, либо он был участником на сборах, а потом досдал задачи, в чем проблема?

7 Кб, 528x457

06 Июл, 08:31 #509 #789363

>>788646
Дуги и вершины нарисованы в фиксированных позициях на плоскости, и должны остаться на тех же местах после проведения разреза? Если да, то это важное ограничение.
Оптимальным разбиением пикрелейтеда может быть {A, B, C} и {D, E}, но ты не сможешь провести так границу не пересекая лишних дуг.

Ответы>>791283

08 Июл, 10:36 #510 #791283

>>789363
Лол, как ты до такого варианта вообще дошёл? У нас тут на граф задача, а не на геометрию.
Твоя геометрия решается за что-то около (V^2)*E то есть не больше чем V^4 в общем случае тупым перебором с сортировкой по полярному углу.

Ответы>>791372

08 Июл, 12:59 #511 #791372

>>791283
>Его в некоторых случаях нужно будет в игре применять. Один из них минимизация длины линии фронта или раздел границы после войны.
>У нас тут на граф задача, а не на геометрию.
Не факт. Возможно >>788449 просто неправильно понял какую задачу ему надо решить.

Ответы>>791373>>792101

08 Июл, 13:00 #512 #791373

>>791372
fix: Возможно >>787900 просто неправильно понял какую задачу ему надо решить.

Ответы>>792101

09 Июл, 12:53 #513 #792101

>>791372
>>791373
Да, если это игра, то звучит разумно. Просто надо уточнять такие детали, на плоскости задача, можно сказать, давно известна и решается просто. В общем случае это объект научного исследования.

алсо, запилил перекат >>792098 (OP)

Тред утонул или удален.
Это копия, сохраненная 25 июля 2016 года.

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

Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.

« /pr/В начало тредаВеб-версияНастройки/a//b//mu//s//vg/Все доски

Пользуетесь скринридером — пишите, что можно улучшить.
Host-Food.ru — надёжный хостинг от 12 руб/мес | Free DNS
Зеркала М.Двача: m2ch.hk, m2ch.lib, m2chfapiswfw2wcakptqp4o6ltgchvjuxfab7urxlduraomtlnhw5xad.onion