Тренировка #1 [Меньшиков]

[Условия задач]                    [Список тренировок]

1A. Простые числа
[primes]
Незамудренная реализация с одной фишкой: при нахождении делителей числа перебираем только нечетные из них. Как показала практика при этом достигается экономия по времени в 4 раза.
1B. Выражение
[expr]
Лаконичная рекурсивная реализация. Помимо этого решение имело место решение с генерацией всех комбинаций ‘+’ и ‘–’ для текущего набора чисел, которое требовало пересчета всего выражения целиком для каждой комбинации. Это решение не прошло по времени. К достоинству рекурсивного решения относится то, что перерасчет всего выражения не требуется. Нужно пересчитать только его изменившийся конец.
1C. Возрастающая подпоследовательность
[incseq] O(n*n)
Классическая задача на динамику. Решать всем)
Для каждого элемента храним длину максимальной возрастающей подпоследовательности, которая заканчивается текущим элементом. По этим данным можно узнать длину этой последовательности для всего массива и сформировать один из возможных ответов.
[incseq] O(n*logN) 
Для каждого i-ого элемента храним индекс предыдущего элемента из максимальной возрастающей подпоследовательности, которая заканчивается текущим элементом. Поиск предыдущего элемента для i-ого осуществляется бинарным поиском по массиву, сформированному из предыдущих элементов нетривиальным[в оригинале “хитрожопым”] способом.
1D. Треугольник и точка
[tria-pt]
Один из простых подходов: вычисление ориентированной площади через векторное произведение. Если во время обхода знак ориентированной площади треугольника, образованного точкой и двумя смежными вершинами тре(N)угольника не меняется, значит точка лежит внутри[иначе вне]. Данный подход справедлив ТОЛЬКО для выпуклых многоугольников.
1E. Степень
[power]
Классика длинной арифметики. Одно не дает покоя, почему длинное произведение идет раньше длинного сложения. osn = 10.
1F. Покер
[poker] brute
На основе одной сортировки подсчетом и независимой сортировки всех элементов последовательно рассматриваются все случаи. Громоздкая и не самая лучшая реализация с множеством мест для потенциальной ошибки.
[poker] optimized
Двойная последовательная сортировка подсчетом сводит места, где можно сделать потенциальную ошибку к минимуму. Рассмотрение всех случаев кроме Straight тривиальны, хотя и сам Straight не представляет большой сложности.

[Все решения]