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

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

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

  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. @Игорь Беляев, несомненно, достаточно проверять, что расставлены все знаки :)

    ОтветитьУдалить
  6. Здравствуйте. Подскажите как начать? Я сейчас учу C++ по Прате. Материал качественный, но страница за страницей идут новые материалы, не знаю как тренироваться, неплохо былоб найти задачник какой нибудь, не только направленный на математические. Не хочется быть гавнокодером котоый использует всю технологию, а в голове ничего об алгоритмах. Немного премного проходили на первом курсе алгоритмизацию на Си, но на этом закончили, а мне тема интересна.

    ОтветитьУдалить
    Ответы
    1. Я бы посоветовал начать с ресурса https://acmp.ru/

      Удалить