Разбор задач

Разбор домашнего задания за позапрошлый раз

• «MCCME Прямоугольники». Предлагается алгоритм:

  1. Выберем самую верхнюю строку клеток, а в ней — самую левую клетку
  2. Добавим все клетки справа до первой вырезанной (получится прямоугольник высотой 1)
  3. Будем увеличивать высоту этого прямоугольника, пока в нем встречаются только невырезанные клетки
  4. Вырежем полученный прямоугольник

     •      ████████  ██     ▒███████  ██     ▒→→→→→→→  ██     ▒→→→→→→→  ██               ██
          ██████████████   ██████████████   ██████████████   ██↓↓↓↓↓↓↓↓████   ██        ████
          ██████████████   ██████████████   ██████████████   ██↓↓↓↓↓↓↓↓████   ██        ████
          ████  ████████   ████  ████████   ████  ████████   ████  ████████   ████  ████████
          ██  ████████     ██  ████████     ██  ████████     ██  ████████     ██  ████████  
          ████████  ████   ████████  ████   ████████  ████   ████████  ████   ████████  ████

  5. Если ещё не все клетки вырезаны, перейдём к п.1

• «Пилообразные перестановки» (эта задача не совпадает с задачей MCCME «пилообразные последовательности»). Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данному числу n определите число пилообразных перестановок последовательности 1,2, …, n. Идея алгоритма: динамическое сведение к подзадачам:

  • Предположим, мы посчитали F(n) — количество пилообразных последовательностей из чисел 1…n для всех n≤N. Тогда F(N+1) вычисляется так:

    • Число последовательностей длины N+1, в которой число N+1 стоит на k+1 месте, — это C_N^k*(F(k)/2)*F(N-k)/2, т. е. произведение

      1. числа последовательностей длины k, в которых k-й элемент меньше k-1го,
      2. числа последовательностей длины (N+1)-(k+1), в которых 1-й элемент меньше второго, и
      3. количества возможных наборов из k чисел в первой посделовательности

    • Следовательно, F(N+1)=Σ_k=1^N+1C_N^k*(F(k)/2)*F(N-k)/2

  • Идея нуждается в проверке и «зачистке по краям» (например, при k=1,2,N,N+1)

Домашнее задание

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

   3. привести контрпример .

2. Проверить алгоритм и написать решение задачи «Пилообразные перестановки», генератор тестовых данных и проверочную функцию для неё.

3. Прочитать внимательно (а не как я ) условия задачи «пилообразные последовательности» и решить её. Она гораздо проще задачи «Пилообразные перестановки»

Условные обозначения

• — тема по Linux

• ­— тема повышенной сложности

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh