Знания для спортивного программирования

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

Что еще?

LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Пофигу.

Вот пример:
en.wikipedia.org/wiki/Gennady_Korotkevich — дважды чемпион мира по ACM, занимал topcoder 1 и 2 места в течении многих лет. Пишет на Tubro Pascal в Far Editor (часть Far Manager).

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

Наверное его команда сейчас на C++ пишет. Но на чемпионатах он писал на паскале.

Странный вопрос. Для успешного результата, если плаваешь в алгоритмах нужно знать язык на зубок, ты не должен думать как писать на языке во время олимпиады, а думать как ты реализуешь и с какой скоростью. Если серьёзного уровня олимпиада, то будут задачи, чтобы ты лажанул, используя STL/boost (десятки миллонов аллоков в секунду) вместо того, чтобы использовать простые конструкции на С. Не забывай что организаторы могут дать (и дадут) ограничение на выполнение кода, причём на некоторых задачах такое, чтобы выполнилось впритык, чтобы отсеять многих. Язык как средство нужно знать не только на зубок, нужно понимать, как оно будет скомпилировано и т.п. Для городских и областных олимпиад, это, конечно же, не нужно, не тот уровень.

Другими словами, олимпиада по умению проходить олимпиады. Цель — просто отсеять, и сделать из этого событие.

В любой реальной задаче всегда есть конкретика. Вплоть до того, что дешевле тупо поднять количество памяти железно, чем пытаться выкрутиться в софте. Пример — роутеры. Каждый китаец просто видит целью жизни сэкономить пару центов на ROM, чтобы потом просадить сотни миллионов на маркетинг — который только ускорит отказы от бренда, потому как в ROM ни полбайта не добавится. Правильный победитель — тот, кто уволит «каждого» продажного китайца из руководства. Не тот, кто будет пытаться выпускать бажные прошивки, так никогда и не выпустив рабочей — но выпустит десяток новых моделей (на уже убитый рынок).

Вечный вопрос Азимова: «Why do they call them Olympics?»

Софт пишется один раз, а железо покупается для каждого изделия. Логично, что экономят на железе по максимуму.
Это для уникальной хренотени на спутнике одно изделие, но там другие ограничения вес и объем.

Очень распространённое заблуждение. При переплате 3 центов за деталь и серии в 10 000 000 устройств, ты «экономишь» 300 000 зелени. Но задерживаешь выпуск устройств на пару месяцев, тратя их на разработку и тестирование (со всеми накладными расходами, включая вышестоящую иерархию, налоги) — а на выходе получаешь 10млн устройств, которые БУДУТ проданы... и все вернутся по гарантии. В лучшем случае их перешьют на каком-то этапе продаж.

Если бы прошивка помогла, это полбеды. Но она НЕ поможет, поскольку костыльная прошивка будет ещё более глючной. А на следующую производитель откажется дать денег — ведь устройства он уже «продал», бабло поделили.

Что на самом деле: устройства не проданы, они только попали в розницу. Вал отказов гарантирует попытки продавцов быстро сбагрить дерьмо, в основном за счёт снижения цены процентов на 30. Я напомню, на маркетинг УЖЕ потратились, вся раскрутка давно прошла. И производитель, считая что модель сдохла своей смертью, выпускает НОВУЮ — то же дерьмо, в новом корпусе, ичсх на новой комплектухе — чтобы сэкономить ещё 1 цент (и заново провести разработку).

Что нужно было сделать: взять нормальную деталь, и выпускать серию за серией те же самые устройства, не вкладываясь в маркетинг. Но удерживая цену, явно с прибылью повыше 3 центов. Продажи будут уже не 10млн, а 250млн устройств, и уже тогда выпускать новую серию — ещё лучше, и с наценкой чуть выше.

Японцы первыми эту тему прохавали. Правда было это давно, уже успели подзабыть.

Вот только твоя сказка нынче уже не работает.

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

Я прекрасно знаю, как работает и то, и другое, и успешно. Но львиная доля так называемого «маркетинга» между крайностями — тупое просирание денег, с неизбежным ростом цен на эти услуги. Золотой середины в маркетинге нет.

Но может у тебя другой опыт, расскажи.

Золотая середина просто неустойчива.
Оптимум и равновесие- не всегда одна и та же точка.

1) Железо протухает. Через 3 года такого железа тупо нет у производителей.
2) Конкуренты предлагают аналоги быстрее и с новыми стандартами — производители железок тоже занимаются маркетингом.

От смены железок никуда не деться. Если хочешь держать долю рынка — нужна еще и линейка моделей с разной ценой. И вот контора уже влетает в 10-20 одновременно поддерживаемых устройств с разным железом.

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

Вот уж где точно лучшее враг хорошего, так это в железе. Есть хай-енд, за него надо бороться. А есть рабочие лошадки, которые должны побеждать числом и присутствием. Чем дольше и больше одна серия на рынке, тем больше и лучше под неё софт. А софт — это то что собственно работает на рынке, что выполняет задачи.

Чтобы держать долю рынка массовых устройств, нужна не смена модельного ряда раз в месяц, но стабильно узнаваемый бренд и БАЗОВАЯ модель. Именно базовая модель стимулирует продажи более дорогих.

На немассовых устройствах этот параметр куда более критичен. Люди гораздо охотнее купят устройство, про которое уже слышали, читали, видели. Стремление выделиться — на порядок менее слабый драйвер покупок в массовом секторе, нежели стремление не выделяться. А иметь что-то «как все, но лучше».

Этот рынок зачастую скрыт от «аналитеков», просто потому что работает без гиганстких вложений в рекламу. Он просто работает. Согласен, не везде, но львиная доля рынка железячных решений именно такая: ПОНЯТНАЯ железка с напылением премиума.

Сотни миллионов устройств и рассрочку могут себе позволить только редкие гиганты. Обычно это 10к — 100к устройств, и рассрочку никто не даст.

Софт больше не будет.
1) Он упрется или во флеш, или в производительность.
2) Нет смысла разрабатывать мегасофт, за который никто не платит. Редкая железка собирает абонплату, обычно все, что производитель имеет, идет с продаж. Поэтому надо, чтобы были новые железки с софтом, которого нет на старых.

Что-то как у всех обрекает бизнес на провал, так как есть 100500 китайцев дешевле. И они есть всегда. И они всегда дешевле. И ты так же неизвестен, как они.

Я так и сказал, две крайности: или делать нормально, или подделывать давай откровенное дерьмо, зато дёшево. И все кто пытается найти золотую середину — занимаются производством дорогого говна, а потом ещё вкладываются в продажи, не желая конкурировать по цене.

Любимая фишка — выйти за пределы крайности. Поскольку основной продукт сделали дорогим дерьмом, обязательно выпустить премиум-продукт, вдвое дороже. Он разумеется ещё более бажный — потому что за софт платили даже не как за дерьмо, а как за копипасту дерьма. А железо навернули лишь частично, установив мало совместимое железо.

Почему не продаётся ни тот, ни тот — уже объяснил. Базовая модель не входит ни в одну нишу, премиум несёт на себе всё дерьмо репутации базовой модели.

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

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

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

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

Вот не так уж постоянно, как новые модели зачастую на очень похожем железе. Стандарты вафли меняются очень медленно и предсказуемо. Настолько же медленно и предсказуемо меняется обратная совместимость.

И железо не производится моментально. Сначала новинку получает дорогое железо премиум-класса, и уже когда сбросят цену — пойдёт в базовый ширпотреб.

Отдельный сказ о прошивке. Что мешает ложить всё кроме бутлоадера на NAND-флешку, а бутявку — на одноразовый чип? Я откровенно не понимаю этого прикола со случайной порчей инфы на чипе, почему оно всё должно так предсказуемо дохнуть? Зато на флешку бы точно вставало овер дохрена прекрасного фриварного софта.

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

Ты не поверишь, оно так и лежит. Называется first-stage boot loader. Наглухо зашит в ROM проца.

Зато на флешку бы точно вставало овер дохрена прекрасного фриварного софта.

Нафига?

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

Что-то то, что ты пишешь никак не корелируется с

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

Какому проценту от

серии в 10 000 000 устройств

понадобится эта фича? Повезет если 0,1%. Остальные домохозяйки с трудом отличают IP адрес от почтового индекса. Смысл повышать себестоимость серии?

Очень распространённое заблуждение. При переплате 3 центов за деталь и серии в 10 000 000 устройств, ты «экономишь» 300 000 зелени. Но задерживаешь выпуск устройств на пару месяцев, тратя их на разработку и тестирование

С какого перепуга? Поставили NAND меньшего размера и все перестало работать?

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

С какого перепуга она будет костыльной?

P.S.: У тебя есть какой-то скрипт который генерирует бредопосты на заданую тему?

Другими словами, олимпиада по умению проходить олимпиады.

А ты думаешь IELTS — это экзамен по английскому? Нет, это экзамен по умению прохождения IELTS :)

И это отвратительно. Гос.бюрократия в действии — не могут проверить даже знания языка. В Украине она собственно такая же.

ну 8й раздел(как помню), а так же 27 и ясен 34, но не полностью... в зависимости от дисциплины зависит

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

Спортивное программирование — это что-то типа онанизма на время.

Спортивне програмування то і є програмування, а онанізм це весь цей ентерпрайз зі спрінгами і хадупами.

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

В одно время указание этого скилла в резюме даже снижало быть принятым на работу

Это когда такое было?

Да в принципе всегда такое было, только у тех, кто их пробовал и больше не хотел пробовать. В Киеве в районе 2002-2004 мне два раза отказали как раз из-за указания в резюме регалий, объяснив это тем, что горбатого только могила исправит.

В 2009м я спокойно монетизировал олимпиадки, стартовав не с июня, а с мидла сразу

Вот именно для июней они и существуют. Для июнь-HRов. Который нихера в мат.части не рубят, а хотят понтов.

Проще всего в Украине — тупо купить себе лычек. Например, провести крутейший хакатон, со шлюхами и шлюхами, красивыми словами и кучей селфи. Единственное что будет отличать этот хакатон — десятки разных номинаций, и тот факт... что самого хакатона не было. Просто собрались, сделали селфи, наклепали себе лычек — и вуаля!

Другими словами, это тупо ритуалы. Как вышиванка у политиков.

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

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

Так эти знания в этой стране негде конвертировать в деньги.

Ему говорят, что я вошел в айти с 800$/mo, вместо 100-150$/mo кризисно-июньских, а он «негде конвертировать в деньги»...

Ему говорят про 2009й, а он берет 2017. Чувак, перестань.

Ему говорят про 2009й

Где?

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

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

Только не говори, что ты не поменял привычек и подходы к решению задач с тех пор :)

Нет, я до сих пор считаю о-большое и о-маленькое. Не быдлокодер же!

Где считаете? :)
А все кто не считает, быдлокодеры? :)

Притом павлинные перья ВНУТРИ жопы. Код ведь никто из рынка шоу не увидит.

На українському ринку взагалі окрім знання Спрінга ніхто нічого не бачить, будь ти хоч кернельним хакером.

Кернельные хакеры берут по 4-5к и им нет смысла особо бегать по рынку

разве 4-5к это много?

В этом случае и нужно проводить олимпиаду по кернельному хаку. Но как ты сам заметил, хакеры не бегают по рынку, а потом организаторам не виден спрос. А вот ради ЧСВ — хакеры могли бы и поучаствовать, уж чего-чего, а х-ями меряться любят поболе политиков.

Схоже мої аналогії розуміть не тільки лише усі.
Я мав на увазі що це особливість укр. ринку, де не цінують нічого окрім самих примітивних знань, типу конкретної мови чи фреймворку. Саме тому з’являються вакансії типу «Senior Spring Developer». Під ядерним хакером я мав на увазі людину яка яка має знання набагато глибші ніж знання Spring/JEE/YOU_NAME_IT. Я маю на увазі фундаментальні знання від архітектури комп’ютера, мереж, ОС і до алгоритмів та структур даних.
Тому ваші пір’я та сраки не відносяться до всього світового ринку, а виключно до самих низів індустрії, типу наших лідерів ринку.

Знання ядра та того, що треба, щоб з ним працювати не є глибшими, аніж знання стосовно того, як побудувати розподілену ентерпрайз систему.

Я вважаю що знання архітектури машини та ОС є набагато фундаментальнішими ніж всі ці «ентерпрайз системи». Не можливо спроектувати щось поверх них не розуміючи як вони працюють. Більше того, як можна відлагодити вашу розподілену ентерпрайз систему не знаючи мереж? Як приклад.
Абстракції течуть, як казав один дядько.

Яндекси/гугли/майкрософти/амазони з вами не згодні.

Конкретные примеры, плиз.

Приклади того що кандидатів-спортсменів розглядають охочіше ніж аналогічних не спортсменів? Чи приклади того що на співбесіді дають задачі дуже схожі на ті ж що й на змаганнях? Обох прикладів достатньо в Інтернеті, починаючи від книжок типу Cracking The Coding Interview і закінчуючи блогами самих гуглерів. Можете тут запитати, тут є достатньо людей які там працюють. ІЩСХ, переважна більшість з них олімпіадники.

Ты так ничего и не понял.

www.quora.com/...​at-one-of-those-companies

В коментах переважно пишуть що то не обов’язкова умова, що звісно правда. Ніхто й не стверджував противне. Так що, схоже, ти щось не те собі придумав.

В коментах переважно пишуть що то не обов’язкова умова

Абсолютно ненужное условие:
— Competitive programming accolades on a resume mean literally zero—nothing—to me.
— Until I discovered Quora I had no clue that such a thing as competitive programming existed.
и т.д.

Так що, схоже, ти щось не те собі придумав.

Я говорю о том, как смотрят знающие люди на спортивщиков, если участвовал много лет в олимпиадах, то отношение будет даже скорее негативное, ибо происходит деформация, которая идёт в разрез с коммерческим программированием.

zero—nothing—to me.

Ну що ж. У кожного свій життєвий досвід і своє враження від індустрії.

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

Такое хорошо в маркетинге. Сумел выпендриться — молодец. А вот в командной работе выпендрёж дорого обходится. В частности, по срокам исполнения.

Только в случае когда САМИ проводят свою олимпиаду. Но они давно прохавали тему и заменили конкурсы за свой счёт — сертификациями за счёт кандидата. То же дерьмо, но профит.

Ещё бы яндексы/гуглы/майкрософты научились код писать. И документацию к своим апи.

Время вторично, главный критерий — количество успешно решённых задач. В вашей аналогии — это ппц какой челленж, учитывая что задач обычно 8, а часов всего 5.

Жаль не могу вам дать одну из своих.

Кормена читай

Понять, что написано в:

www.lulu.com/...​ack/product-21059906.html
cses.fi/book.html
(ну или аналогичные handbook’s от codeforces, topcoder).

Плюс алгоритмы-алгоритмы и еще раз алгоритмы. Например (но не только):
www.uoitc.edu.iq/...​e_exam/DataStructures.pdf

И много практики.

Из того, что нужно знать из c++...
Обычно базового + STL должно хватать. Но знать не просто, а с точки зрения, что и когда эффективней использовать. Очень многие вообще пишут на С...

PS: еще -
Полезный список: github.com/...​e-competitive-programming
Полезные для «спортсменов» алгоритмы: codeforces.com/blog/entry/13529

Кроме базовых конструкций, нужно уметь в STL без гугла, чтобы свои списки/хеш-таблицы не сочинять. Ещё PriorityQueue (если она там есть).

А вообще ты не с той стороны заходишь: найди любую площадку с задачами (например uva.onlinejudge.org), реши штук 100 на разные темы — там и увидишь, что надо а что нет.

Для начинающих неплох hackerrank.com — там есть Editorial — если заткнулся, можно посмотреть, почитать, разобраться. Заодно решения других участников посмотреть. От простого к сложному.

Математику учи. Базовые штуки языка для решения олимпиадных задач можно за вечер понять.

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

Ага. STL с алгоритмами и функторами за 21 час. А без нее там делать нечего.

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

А в Паскале есть STL?

Достаточно знать лишь базовый C.

Подписаться на комментарии