dmkz's blog

By dmkz, history, 6 years ago, In Russian

Привет, codeforces! В рамках проекта по подготовке к олимпиадам по программированию в качестве задания была выдана эта задача на двумерное динамическое программирование.

Кратко суть задачи: дана матрица размера n2, где n ≤ 200 , в которой есть нулевые и ненулевые элементы. Расстояние на матрице между ячейками (x1, y1) и (x2, y2) определяется как dist = |x1 - x2| + |y1 - y2|. Каждый нулевой элемент нужно заменить ближайшим к нему ненулевым элементом, а если подходящих элементов несколько, то оставить без изменений.

Я написал решение на C++, которое получило вердикт Accepted, и решил ради эксперимента перенести его на python3, чтобы попрактиковаться с новым языком программирования. Вот что из этого вышло. Действий получается порядка O(n2), но с большой константой. При n = 200 должно пройти, но не проходит — вердикт TLE. Можно ли как-нибудь ускорить решение на python3, заменив ввод-вывод более быстрым (уже вроде как заменил, но может можно еще быстрее), или применив какие-нибудь другие хитрости, так, чтобы оно получило вердикт Accepted?

Кратко суть решения:

  1. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≥ x *  и y ≥ y * .
  2. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≤ x *  и y ≥ y * .
  3. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≥ x *  и y ≤ y * .
  4. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≤ x *  и y ≤ y * .
  5. Объединение ответов

Для каждого прохода 1-4 используем метод ДП, комбинируя ответы для соседних элементов, например, в 1 пункте: answer[x][y] = combine(answer[x - 1][y], answer[x][y - 1]) + 1

  • Vote: I like it
  • 0
  • Vote: I do not like it