понедельник, 8 марта 2010 г.

Тренировка #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 не представляет большой сложности.

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

7 комментариев:

  1. Оп оп оп, стоп :)
    Жопой чую, что для невыпуклого многоугольника подход с ориентированными площадями не канает.

    Там только через проведения произвольной прямой и подсчёта четности пересечения со сторонами N угольника.

    P.S.: This needs to be clarified and tested :)

    ОтветитьУдалить
  2. P.S.: Я выпил во фрайдейз кувшин пива, но мне кажется я прав :-d

    ОтветитьУдалить
  3. Решение задачи "1B. Выражение" не верно. На тесте: 2 10 10 1 программа выдает ошибочный ответ. Ошибка в этой строке if (curSum == sum) // ответ найден в функции int rec(int, int)

    ОтветитьУдалить
  4. Да, Вы правы. Этот вопрос поднимался здесь: http://informatics.mccme.ru/moodle/mod/forum/discuss.php?d=1097 Я думаю не составит большого труда исправить текущую реализацию.

    ОтветитьУдалить
  5. @Игорь Беляев, несомненно, достаточно проверять, что расставлены все знаки :)

    ОтветитьУдалить