Комментарии 9
Странное это ваше спортивное программирование, которое по сути чисто математические задачи, в принципе можно решать просто на бумаге с ручкой, а от программирования, смакования программирования, тут мало чего.
А что есть «смакование программирования»? Любая программа — математика, которая решается с помощью ручки. Пощупать результат? Но так в спортивном программировании нужно реализовать свою мысль. Половить баги? В спортивном программировании этого добра выше головы. Тут вопрос терминологии и определений.
Конечно, получить данные на входе, допустим из парсера или с хардварной карты, обработать их, интерполировать, агрегировать и красиво вывести в виде графика тоже математика. Но согласитесь, совершенно не та математика, требующая специальных знаний, как на соревнованиях по спортивному программированию. Да и вряд ли такие задачи когда-либо будут этих соревнованиях. Можно ли оперировать с такими данными с помощью ручки и бумажки? Да, можно, но на это у вас уйдёт слишком много времени и бумажек. И вам не нужно строить графы, поиск выхода из лабиринта или искать где сходится множество.
Это для математиков задачи, а не для программистов! Такие знания математики нужны пожалуй только для написания своего 3D движка. Программлю успешно последние 12 лет своей жизни и честно сказать почти ничего не понял о чем тут говорится. Математику знаю (и помню) до 5 класса школы)
«Это для математиков задачи, а не для программистов!» Простите, а те же создатели 3D движка не программисты? А создатели алгоритмов или структур данных (которые все используют, возможно и вы, пусть и неявно)? Программирование бывает разным (как и много других специальностей): вот у меня знакомый 7 лет делает сайты визитки на вордпресе и знать ничего не знает про все эти энгуляры и другие новомодные течения (и я никого не упрекаю и не критикую, сайты визитки также нужно делать и это нелегкая работа ). Я, например, также ничего не понял из этого поста, но это не потому что он не для программистов, а просто потому, что я в это ни в зуб ногой (если бы я зашел на топик про haskell также ничего не понял бы ). Извините за, возможно, кривые примеры, но позволю себе привести еще один: представьте себе, после разбора конкурса для хирургов один врач заявляет, мол, эти задачи для анатомов, а не для врачей, я вон 20 лет проработал окулистом и знания анатомии мне так и не пригодились. (Опять же, я не уменьшаю важности окулистов, просто пытаюсь донести, что специалист по глазам, может ничего не понимать в хирургии и наоборот)
Используя ваш пример с врачами, можно сказать о том, что здесь даны задачи для нейрохирургов, которые назвали просто задачами для врачей. Это узкоспециализированные знания, которые касаются ну может быть максимум 10% программистов. И не способность решить их отнюдь не означает что остальные 90% – не программисты.
Разбор задачи С:
«Асимптотика решения — O(sqrt(a[1]) + d(a[1])•n), где d(a[1]) ≤ 1344.»
Объясните, пожалуйста, почему именно такая асимптотика? Ведь gcd множества M_2 находится за O(log(max(M_2))), таким образом асимптотика должна быть O(sqrt(a[1]) + d(a[1])•n•log(max(a[i]))).
«Асимптотика решения — O(sqrt(a[1]) + d(a[1])•n), где d(a[1]) ≤ 1344.»
Объясните, пожалуйста, почему именно такая асимптотика? Ведь gcd множества M_2 находится за O(log(max(M_2))), таким образом асимптотика должна быть O(sqrt(a[1]) + d(a[1])•n•log(max(a[i]))).
Давайте рассмотрим множество M_2, будем считать его gcd по-очереди добавляя в gcd числа из M_2. Пусть g — текущее значение gcd, и мы берем gcd(g, a_i). Где a_i — очередной элемент M_2. Будем рассматривать рекурсивную реализацию gcd.
int gcd(int a, int b) {
return b == 0? a: gcd(b, a % b);
}
Тогда на глубине рекурсии, равной 2, значения a и b не превосходят значения g. А так, как при каждом новом уходе в рекурсию итоговое значение gcd уменьшается в 2 раза, после вычисления gcd, g уменьшится в 2^(h — 1) раз, где h — глубина рекурсии. Так как, g мы поддерживаем по ходу, оно может уменьшится в 2 раза не более логарифма раз. В итоге, вычисление gcd множества M_2 будет работать за O(|M_2| + log(max(a_i)))
Вроде, как-то так :)
int gcd(int a, int b) {
return b == 0? a: gcd(b, a % b);
}
Тогда на глубине рекурсии, равной 2, значения a и b не превосходят значения g. А так, как при каждом новом уходе в рекурсию итоговое значение gcd уменьшается в 2 раза, после вычисления gcd, g уменьшится в 2^(h — 1) раз, где h — глубина рекурсии. Так как, g мы поддерживаем по ходу, оно может уменьшится в 2 раза не более логарифма раз. В итоге, вычисление gcd множества M_2 будет работать за O(|M_2| + log(max(a_i)))
Вроде, как-то так :)
Что мне не нравится в разборах, так это бездоказательные утверждения. «Очевидно», «заметим» и т. д. Вот не очевидно совсем.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Разбор задач первого квалификационного раунда RCC 2016