Компания
366,79
рейтинг
4 августа 2014 в 13:51

Разработка → Разбор финальных задач Яндекс.Алгоритма 2014

1 августа в офисе Яндекса, открывшемся недавно в Берлине, состоялся финал нашего чемпионата по программированию. И его победителем снова стал известный всем, кто интересуется спортивным программированием, Геннадий Короткевич.

Задания для Алгоритма готовила международная команда. В нее вошли программисты из России, Беларуси, Польши и США. Это специалисты МГУ имени М.В. Ломоносова, Университета Карнеги-Меллон, сотрудники Яндекса и Google. В Яндексе задачи составляли разработчики минского и киевского офиса, а потом проверяли их на своих коллегах. Один из составителей в прошлом году сам был финалистом Алгоритма. Специально для Хабрахабра мы разобрали с авторами все задачи. Кстати, несмотря на то, что соревнование завершено, вы можете попробовать себя в вирутальном контесте.



На победу претендовали многие финалисты. Среди них были победители и призеры АСМ ICPC и TopCoder Open, разработчики Google и Facebook. В финальном раунде сражались призёры Алгоритма-2013 Евгений Капун и Ши Бисюнь, чемпион АСМ ICPC Михаил Кевер, а также один из самых титулованных спортивных программистов мира Пётр Митричев. В этом году побороться за приз решил также Макото Соэдзимо — составитель заданий для Алгоритма-2013 и администратор TopCoder Open.

Борьба за первое место разгорелась между Геннадием Короткевичем и Хосакой Кадзухиро из Токийского университета. Лучший результат — четыре задачи при 66 минутах штрафного времени — показал Короткевич, подтвердив титул чемпиона. Кадзухиро решил столько же задач, но набрал больше штрафного времени (90 минут) и занял второе место. Третье место завоевал Ван Циньши из университета Цинхуа: он решил четыре задачи при 125 минутах штрафа.

Задача A. 1024 Stack Edition


Ограничение по времени: 1 second
Ограничение по памяти: 512 mebibytes

Недавно девочка Ксюша купила в онлайн магазине приложение «1024 Stack Edition» — пошаговую аркаду. Как можно догадаться из названия, игра разворачивается вокруг некоторого стека, наполненного степенями двойки. По правилам игры, на каждом ходу игрок может выполнить одно из трех действий над стеком:

  • Добавить случайное число в конец стека.
  • Убрать последнее число из стека.
  • Если два последних числа равны, то заменить их на их сумму.

Если игрок выбирает добавить случайное число в стек, то с шансом p в стек добавится число 1 и с шансом 1-p добавится число 2. Если игрок выбирает убрать последнее число из стека, он платит штраф в 1 монету. Обратите внимание, что все остальные операции, кроме удаления последнего элемента из стека, не приводят к уплате штрафа. Для того чтобы выиграть, игроку необходимо привести стек в такое состояние, что в нем находится лишь один элемент — 1024. При этом, чем меньше штрафа он заплатит — тем лучше.

Как-то раз Ксюша оставила свой телефон без присмотра, а по возвращению обнаружила, что кто-то играл в «1024 Stack Edition». Ксюше не интересно узнать, кто это был и каковы были его мотивы. Ей интересно узнать, каково математическое ожидание штрафа, который лично ей придется заплатить при оптимальной игре, если она доиграет партию. Ваша задача, как вы могли уже догадаться, посчитать это число.

Разбор задачи A

Для начала рассмотрим случай, когда N = 0. Пусть f(i) — это ожидаемое наименьшее количество монет, которое потребуется потратить, чтобы собрать число 2i. Приведем формулы для подсчета f(i) в случае, если p < 100. Если же p = 100, то эти же формулы адаптируются тривиальным образом.

  1. f(0) = 1.0/p — 1;
  2. f(1) = min(f(0) • 2; 1/(1 — p) — 1, 1 — p);
  3. f(i) = 2 • f(i — 1), i > 1.

В случае с N = 0 ответом на задачу будет f(10).
Теперь предположим, что N > 0. Обозначим через g(i, j) ожидаемое наименьшее количество монет, которые нам нужно будет потратить, чтобы из последних (верхних) i элементов стека получить только одно число 2j. Подсчет g(i, *) для фиксированного i будет происходить в 2 этапа (через S(i)обозначим двоичный логарифм i-го сверху элемента стека):

1. Посчитаем g(i, S(i)) = 1+min(g(i — 1; *)), i > 1. Этот случай соответствует тому, что из всего, что выше элемента i, мы получаем некоторое число, после чего удаляем его.

Также посчитаем g(i, S(i) + 1) = g(i − 1, S(i)). Этот случай соответствует тому, что мы из всех элементов, расположенных выше i, собираем число 2S(i), после чего объединяем его с текущим элементом, который также равен 2S(i). Для всех j, отличных от S(i) и S(i) + 1, положим g(i,j) = +inf.

2. На первом этапе мы «разобрались» с числом S(i). Прежде чем переходить к g(i + 1, *) и числу S(i + 1), мы можем произвести некоторые действия с i-м элементом стека, превратив его в любой другой элемент. Чтобы это учесть в динамике, пересчитаем g(i, *) следующим образом:

g(i, 0) = min(g(i, 0), min(g(i, *)) + 1.0/p) — мы либо используем уже найденное значение g(i, 0), либо берем любое число, удаляем его и ставим туда 1 = 20.
g(i,j) = min(g(i,j),min(g(i,*)) + 1 + f(j),g(i,j − 1) + f(j − 1)), j > 0. Здесь мы либо удаляем стоявшее на месте i число и затем за f(j) монет ставим туда число 2j, либо ставим за g(i, j − 1) шагов число 2j−1, собираем за f(j − 1) шагов еще 2j−1 и объединяем их.

Ответом на задачу будет g(N,10). Следует обратить внимание, что в промежуточных вычислениях следует также считать g(*,11). Сложность решения O(NR), где R — максимальная степень двойки, которая присутствует во входных данные (в данном случае R ≤ 10).



Задача B. Строчная задача


Ограничение по времени: 4 seconds
Ограничение по памяти: 512 mebibytes

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

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

Известно, что пользователи могут допустить опечатки при вводе запроса. Скажем, что строка A почти меньше строки B, если в строке A можно заменить не более одной буквы на произвольную маленькую букву латинского алфавита так, чтобы строка A стала лексикографически меньше строки B.

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

Разбор задачи B

Рассмотрим пару строк s и w. Строка s почти меньше строки w тогда и только тогда, когда минимальная лексикографически строка smin, которую можно получить из s заменой одной буквы, строго меньше w.

Однако, как легко видеть, smin получается из строки s заменой первого символа не равного ‘a’ на символ ‘a’. Если строка s состоит только из символов ‘a’, то s = smin. Рассмотрим строку si, и найдем Ci — количество строк sj (возможно i = j)таких, что smini < sj. Тогда к ответу нужно прибавить Ci — 1, если smini ≠ si, и Ci в противном случае.

Для нахождения величин Ci можно воспользоваться двумя способами:
  • отсортировать строки si и находить Ci двоичным поиском;
  • добавить все строки в trie, и находить Ci спуском по нему.


Задача C. Кубик


Ограничение по времени: 2 seconds
Ограничение по памяти: 512 mebibytes

Дан куб, грани которого пронумерованы различными целыми числами от 1 до 6. Также дано гексамино, все клетки которого пронумерованы различными целыми числами от 1 до 6.

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

Разбор задачи C

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

Далее существует несколько методов решения. Один из них состоит из следующих шагов:

  1. Устанавливаем кубик нижней стороной на соответствующую клетку гексамино.
  2. Для каждого из четырёх поворотов кубика вокруг своей оси начинаем перекатывать его по гексамино до тех пор, пока возможно перекатить кубик так, чтобы нижняя грань попала на клетку с соответствующим номером.
  3. Если для какого-то из поворотов все 6 клеток посещены, то ответ “Yes”.
  4. Если нет, то меняем местами цифры на правой и левой гранях и повторяем процедуру с шага 2.
  5. Если и в этом случае ни при одном из поворотов не посещены все 6 клеток, то ответ — “No”.

Также существует возможность предпросчитать все 11 развёрток и затем проверять совпадение гексамино (поворачивая его в стандартное положение), а в случае совпадения — соответствие пар чисел, использованных для нумерации противоположных сторон кубика, с теми же парами в развёртке.



Задача D. НЛО


Ограничение по времени: 1 second
Ограничение по памяти: 256 mebibytes

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

С утра Вася пришёл на берег озера и нашёл K титановых стержней. Предполагая, что эти стержни являются рёбрами каркаса НЛО и что, возможно, часть рёбер ещё находится под водой, определите наименьшую возможную размерность пространства, из которого прибыл НЛО.

Решение задачи D

Это самая простая задача набора. Очевидно, что размерность параллелепипеда не меньше количества различных длин рёбер. Также заметим, что в K-мерном параллелепипеде 2K-1 рёбер одного типа, то есть в в случае наличия X одинаковых рёбер для них будет использовано [(X − 1)/2k−1] + 1 измерение.

Поэтому в порядке возрастания перебираем все размерности, пока вычисленное по указанной выше формуле суммарное количество использованных измерений не будет меньше или равно текущей размерности. Так как при K = 21 рёбер одного типа будет 220 > 106, то перебор будет небольшим.

Задача E. Недополняемое паросочетание


Ограничение по времени: 1 second
Ограничение по памяти: 512 mebibytes

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

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

Артёмке дан двудольный граф. Его задача — найти количество недополняемых паросочетаний в нем по модулю 1 000 000 007 (109 + 7). Ваша задача — помочь ему.

Решение задачи E

Для решения задачи заметим, что число вершин в левой доле невелико.

Будем считать следующую динамику, добавляя по одной вершине из правой доли: f(i, j) — количество способов расставить рёбра в случае, когда мы рассмотрели первые i вершин правой доли, а вершины левой доли заданы троичной маской j следующим образом: 0 — вершина не могла быть соединена ребром ни с одной вершиной из правой доли, 1 — вершина могла быть соединена ребром ни с одной вершиной из правой доли, однако мы не поставили это ребро, 2 — вершина соединена ребром с одной из вершин правой доли.

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

Таким образом, ответом будет сумма f(n2, ValidMask), для всех троичные масок ValidMask, не содержащих единиц в троичной записи.



Задача F. Музыкальный мир


Ограничение по времени: 1 second
Ограничение по памяти: 512 mebibytes

В обновленной Яндекс.Музыке музыкальные рекомендации стали ещё лучше, чем раньше! Они учитывают каждый прослушанный пользователем трек с самого начала использования сервиса, и в зависимости от уже прослушанных — увеличивают пул рекомендаций. Плеер включает пользователю случайный из рекомендованных треков, и так целый день.

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

Пользователь выбирает первый трек, а дальше алгоритм автоматически строит рекомендации на N песен вперёд. Из каждой песни i-го поколения может получиться не более Ki (1 ≤ Ki ≤ 5) новых песен в (i + 1)-м поколении, причём для i-го поколения известна вероятность pi, j того, что на основании песни i-го поколения будет предсказано j новых песен для каждого j от 0 до Ki.

Так как экспериментальное исследование производилось на жанре инди, все рекомендованные треки различны. Для того чтобы измерить разнообразие сбора статистики о похожести песен, похожесть измеряется для каждой пары треков. Чтобы помочь разработчикам Яндекса оценить затраты по памяти для этого измерения, вычислите математическое ожидание количества пар треков в пуле рекомендаций в (N + 1)-м поколении.

Решение задачи F

Обозначим за Yi случайную величину, равную количеству песен в i-ом поколении. Предлагаемое решение задачи основано на понятии производящей функции. Если вы не знакомы с ним, ознакомиться можно, к примеру, в статье Википедии ru.wikipedia.org/wiki/Производящая_функция_последовательности.

Рассмотрим производящие функции заданных во входе случайных величин , а
также производящие функции случайных величин .

У нас есть явный вид всех ψi, а также явный вид φ1(x) = x. Научимся выражать φi+1 через ψi и φi.

В случае, если бы мы точно знали, что Yi = k, то можно было бы утверждать, что φi+1(x) = ψi(x)k. Но так как Yi — случайная величина, то искомая производящая функция есть сумма производящих функций, соответствующих разным значениям, с весами, равными вероятностям этих значений, то есть .

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


Научимся пересчитывать значение, первую и вторую производную функции φi+1(x) в (1) через предыдущие функции. Напомню, что φi(1) = ψi(1) = 1. Как мы знаем, φi+1(x) = φii(x)). Тогда

При подстановке x = 1 эти формулы упрощаются и принимают вид


Также несложно понять, что вычисления можно проводить сразу по модулю 109 + 7, заменив исходные вероятности на соответствующие значения по модулю.
Автор: @lperovskaya
Яндекс
рейтинг 366,79

Комментарии (32)

  • +14
    Эх, мне решения можно в качестве задач давать, недельки на три наверное хватит.

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

    Победившим поздравления!
    • +2
      А если у них семья, то можно утешать мыслью, что оптимизация мытья тарелок после ужина тоже является ещё той задачкой.
      А если у них есть дети, то можно утешать мыслью, что наше подрастающее поколение настолько продвинуто, то может учить своих родителей. Но ведь этому научили их мы.
      А если у них работа, то можно утешать мыслью, что при сложных условиях работы в невесомости накладываются иные взгляды на решаемые проблемы.
      А если у них…
  • +5
    А что за «штрафное время»? Плохо стрелял в CS? :)

    Прочёл все задачи и не понял одного — а причём тут программирование вообще? Ну отбери у них компьютеры и дай карандаш с бумагой — ТОЧНО ТАК ЖЕ ВСЁ МОЖНО РЕШИТЬ. Зачем тогда тут приплетать компы? Это тервер, комбинаторика, матан — первые три курса института. /хотя каюсь, ничего из этого я уже не решу — забыл :) /
    • +4
      Штрафное время складывается из штрафа за неверную попытку (20 штрафных минут) и времени, потраченного на решение задачи (например, 40 штрафных минут если задача была успешно решена на сороковой минуте). Кроме того, можно получить за задачу отрицательное штрафное время, отправив её без права повторной попытки.

      Кроме математики и теории вероятностей в задачах используются и структуры данных, значение имеет эффективность их использования. Именно умение не только решить задачу математически, но и верно реализовать решение отличает программирование от математики.
      • 0
        Это не программирование, а математика + обсчёт на компьютере. Весь пост — сплошные формулы, что здесь от программирования? Классы? Шаблоны Проектирования? Биты/байты? Или вы «программированием» уже готовы назвать суммирование в цикле?
        Я не спорю, писать программы надо уметь, но с таким успехом и плотник, рассчитавший гипотенузу в Икселе — программист! Вам самой не смешно называть это программированием?

        PS
        Про «штрафы» — шутка же, совсем с работой заморочились? :) CS=Counter Strike, намёк на биатлон
        • +2
          Классы\шаблоны\etc — не более, чем инструмент. Задача программиста как раз в том, чтобы уметь спроецировать реальный мир на математические абстракции, описать реальный мир языком цифр, а именно с цифрами и работает компьютер.
          А конечным инструментом может оказаться процедурное\ООП\функциональное программирование, это уже не так важно в данном контексте.

          Приведу пусть и не точную, но (мне так кажется) уместную аналогию: на конкурсе мастеров деревообработки не станут проверять мастерство работы с ЧПУ-станком, а как раз выдадут рубанок\молоток\нож и так далее.
          • –2
            Ясно. Понимание программирования на уровне «Если в робота кидаться макаронами, то он сломается, потому что от них у него защиты нет».
    • 0
      Смысл конкурса в том, чтобы определить, кто лучший программист, а смысл программиста — в том, чтобы учить компьютер наиболее оптимально решать задачи. Всё логично.
    • +3
      Тут задачки конкретно на программирование и оптимальные алгоритмы, для которых нужны знания математики и смежных наук, а не наоборот.

      Ведь, грубо говоря, почти любую компьютерную задачу можно решить разными способами:
      1. Напролом, перебор и т.п. Это займёт уйму времени (может даже и жизни не хватить)
      2. Оптимальный. Тут на подмогу приходят знания алгоритмов, умения правильно пользоваться структурами данных и знать их слабые и сильные стороны и прочее. Благодаря этому долгую задачу из #1 можно сократить до порядка минут или секунд.
      Особенно это хорошо чувствуется когда идёт обработка больших массивов данных, так как, например, разные алгоритмы эффективны с разным объёмом данных. Так называемое «решение в железе», которое можно применить в реальных условиях и летать с ними на луну.

      А на бумаге это больше как теоретическое решение, а не практическое. То же можно решить, но это другие цели.
      • 0
        Ну да, всё верно.

        «Нам нужно нарисовать борщ, для этого воспользуемся картинкой свёклы и напишем программу, выводящую в случайных местах нашу свёклу» — вот такого специалисту по борщам я сейчас вижу, но никак не программиста.
        • 0
          Примерно так, но только надо это сделать оптимальнее, что бы, например, свёкла не выводилась два раза в одном и том же месте и что бы учитывалось нахождение других овощей.
          • 0
            Ну вот! Уже ближе к программированию. Осталось только закрепить мысль:

            Программирование ДАВНО уже перестало быть частью «математики» и стало абсолютно самостоятельной областью, со своими методами, концепциями и «аксиомами». Математика, физика, ДАЖЕ ЭСТЕТИКА стали на службе IT, но это никак не превращает программирование в решение задач для тервера. Эта мысль не вызывает споров? Равно как и мысль, что 99% задач программистов даже рядом не стоят с математическими абстракциями.

            Отсюда, возвращаемся к изначальному посту: что конкретно компьютерного вы нашли в задачах от тындекса? Они что, общаются с СУБД? Обрабатывают прерывания? По сетям что-то передают? Достаточно глянуть на решения — это же сплошь математика и формулы, накой им компьютеры-то? Проверить, что математик может закодировать цикл? Так это уже вопрос квалификации МАТЕМАТИКА, но никак не задача для профессиональных программистов. А если я вам скажу, что есть такая компьютерная должность «system analyst», вы со стыда сгорите — это как раз тот человек, который избавляет программистов вообще от какой-либо математики/бухгалтерии/физики, превращая требования реального мира в чисто компьютерное ТЗ (надеюсь, не надо расшифровывать?). Верьте мне, я — программист и знаю лучше дамочек-пиарщиц чем мы занимаемся на работе. :)
            • 0
              К сожалению, не согласен. Не знаю почему я похож на «дамочку-пиарщицу», но это не так важно.

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

              Закодировать цикл может любой, а вот что бы закодировать цикл так, что бы он использовал меньше ресурсов и выполнялся быстрее — это уже другое. Тут надо начинать думать иначе.
              • –1
                > Не знаю почему я похож на «дамочку-пиарщицу», но это не так важно.

                :))))))))))))) Это важно, потому что речь шла о lperovskaya, с которой и началась эта довольно глупая дискуссия «математика и программирование». А вы это восприняли на себя ввиду излишней занудности и зацикленности — грустный побочный эффект увлечения математикой. :)

                > Математика нужна…

                Зачем писать банальщину? Вы считаете, что я за 15 лет п-я этого не понял? Это _Я_ вам объясняю, что БОЛЬШИНСТВО п-ских задач даже рядом не стоят с математикой, т.к. решают сугубо компьютерные проблемы — пересылка данных, оптимизации, удобство интерфейса и т.п. Вы нос-то суньте в объявления (ну вот те, которые из реальной жизни) — много там «математики»? Сплошь «похапасты», «облака», «геймдев» и прочее. К чему мне ваши увещевания в математике, месье? Вы совсем не понимаете, что объясняете проф.программисту чем он оказывается занимается! Уж я-то каждый день пишу программы, с людьми разговариваю — мне лучше знать процент вовлечения других дисциплин.

                Вот вам сайт: rsdn.ru слэш forum/dotnet/ — сходите что ли, посмотрите чем занимаются люди, чтоб ерунду не писать.
                • 0
                  Лида не дамочка-пиарщица, а выпускница ИТМО.
                  • –3
                    Разве одно другому мешает? Пол Москвы — «выпускники» чего-либо, правда работают, прости господи, вплоть до «ленинградки» :)
                    Хотя речь не о том, а о том, что человек, работающий в Яндексе, не имеет никакого понимания чем занимается программист. Весь этот бред про математику — умилительная, но далёкая от реальности идея.
                    Выше я уже дал ссылку на сайт — почитайте их вопросы (по реальной работе) и проверьте, сколько там математики.
                    • +2
                      Сами же пишете — «99% задач программистов даже рядом не стоят с математическими абстракциями». Следовательно, каждая десятая задача каждого десятого программиста (условно) требует владения математикой. На абстрактном уровне. И когда этот программист столкнётся с этой задачей — он просто не справится со своей работой. 1% — это огромная величина, особенно при современных объёмах программирования.
                      • –1
                        Требует, но не от программиста. Почитайте кто и чем занимается в составе девелоперской команды:
                        Business Analyst
                        Application Architect
                        DBA
                        Programmer
                        Tester
                        UX specialist
                        Designer
                        Все эти люди «как бы пишут программу», но каждый занимается своим делом. Говорить, что программисту нужно хорошо знать математику — не менее тупо, чем требовать от повара список удобрений для морковки — это НЕ ЕГО РАБОТА.
                        Это в России привыкли на одном Ване пахать за семерых — отсюда и заблуждение.
                        • +1
                          На этой неделе я нарисовал граф обработки данных в нашем проекте. Каждая из десятка с лишним функций, которые попали в него, была математической задачей, на которую я потратил по нескольку месяцев. Причём там была и разработка алгоритма, и кодирование, и много экспериментов. Предсказать заранее, каким должно быть разделение на блоки, и что у них на входе/выходе, мне не удавалось., Как можно было бы реализовать это дело, если бы я только разрабатывал алгоритмы и передавал их кодеру, не представляю. Вообще.
                          • –2
                            И что? А у Васи Иванова вообще нет цифр и формул в проекте. Что будем делать? Настырно проталкивать мысль о важности математики или всё же сходим на RSDN? Пока вы там не прочтёте хотя бы 100 вопросов, не вижу смысла тут «я-кать» со своими графами.
                            • +1
                              Если у Васи в проекте нет формул, то с большой вероятностью ему не приходится реализовывать запросы математика, который пытается перевести свои заумные идеи на понятный Васе язык. Так что речь вообще не о нём. Вот если бы формулы были, а Вася при этом не знал математики, то тогда бы мы посмотрели, как они будут общаться и к чему это приведёт — ведь у каждого своя задача, и математика к программированию не пускают, не так ли?
                • 0
                  Объявления не являются показателем всей сферы.

                  То нанимают «эникейшиков» (так вроде это называется). То есть, люди, которые чисто механически умеют жать на кнопки в правильной последовательности. Для этого много знаний не нужно и, конечно, результат будет соответствующий.
                  После этого эти самые «похапастые» проекты работают тяп-ляп, жрут неимоверное количество ресурсов и не могут решить простые проблемы достаточно быстро. После этого уже начинаются поиски более оптимальных алгоритмов, моделей и прочего. Или проект просто закрывают.

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

                  И это объясняю я, как не математик.
            • 0
              А если я вам скажу, что есть такая компьютерная должность «system analyst», вы со стыда сгорите — это как раз тот человек, который избавляет программистов вообще от какой-либо математики/бухгалтерии/физики, превращая требования реального мира в чисто компьютерное ТЗ

              :)
              Хм, а Вы не путаете «программиста» и «кодера»?
            • +1
              Как насчёт калибровки энкодера в программе? и позиционирования с учетом люфта в механизмах? в ТЗ ни одна сволочь не посчитает нужным это описать (чаще всего именно так, и, вероятно, потому что сами не представляют этого). А Вам, как программисту, все-равно придется это реализовывать.

              2. Понадобилось рассчитать угол отклонения вала рулевого колеса для прохождения заданного поворота на заданной скорости по заданному радиусу и грунту. Поверьте, математик разберется в программировании, но тогда уже вы окажетесь не нужны
              • 0
                Калибровка энкодера — тоже интересно. Особенно если в реальном времени (интересно, на основании каких данных). А ещё и рассчитывать управление мотором, чтобы обеспечить равномерное движение на всём участке и остановку в нужном положении (с точностью хотя бы 10-15 секунд)… Теория там не помощник, нужен анализ эмпирических данных.
                • 0
                  Теория там не помощник...

                  Мы тоже как-то без теории написали программу для управления системой с обратной связью. Всё бы ничего, но примерно раз в неделю систему начинало дико «колбасить», т.е. возникал очень сильный автоколебательный процесс. Пришлось таки браться за теорию и курить критерий устойчивости Найквиста и т.п. — после этого всё заработало как часы!
  • +1
    Дан куб, грани которого пронумерованы различными целыми числами от 1 до 6. Также дано гексамино, все клетки которого пронумерованы различными целыми числами от 1 до 6.
    Определите,...

    Странно, что в условии не поясняется, что такое «гексамино».
    К примеру, в гугл-турнирах мало того, что всё тщательно разжуют по два раза на уровне «домохозяек», так ещё и кучу картинок красивых нарисуют, чтобы исключить неоднозначности. А тут сухая жесть какая-то.
    • 0
      UPD: Почитал оригиналы условий — вопросы отпали. Там всё объясняется, есть примеры входных/выходных данных и ограничения на них, что тоже очень важно для осознания масштаба проблемы :)
      Хотя картинок не хватает — факт!
  • +2
    те кто нихрена не понимает в математике пишет — что математика в голом виде не программирование
    ну и конечно отчасти обидно, что ты типо лох! а эти качки-стероидные они то могут херануть интеграл в уме!

    в сущности повседневный спектр задач — это CRUD-technology =)
    но если будете строить рекомендательную систему то пару формул выучить придется.

    те кто нихрена не понимает в программировании (математики тобишь) — считают что методологии программирования на которых щас все и держится это все бред и надо бы уметь решать алгоритмы на бумажке за 3 минуты.

    видали мы код таких «математиков»

    кстати слыхали мы, что в яндексе мало платят ;)
  • 0
    Поможет ли победа в Тур де Франс стать самым коммерчески успешным токийским рикшей? Вроде бы занятие технически весьма близкое.
    • 0
      Может стать помочь каким-нибудь велокурьером экстра-класса. И это может быть для победителя интереснее, чем работа рикшей.
      • 0
        Именно. Это разные направления саморазвития. Зачем их сравнивать?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка