@pepelac0

Как увеличить производительность скрипта?

Художник

(Время: 1 сек. Память: 16 Мб Сложность: 26%)

Известный художник решил написать новый шедевр. После многих дней усердной работы он захотел исследовать свое творение. Художник вспомнил, что картина писалась следующим образом: сначала был взят белый холст, имеющий форму прямоугольника шириной w и высотой h. Затем художник нарисовал на этом холсте n прямоугольников со сторонами, параллельными сторонам холста и вершинами, расположенными в целочисленных координатах. Помогите художнику определить площадь незакрашенной части холста.

Входные данные

Первая строка входного файла INPUT.TXT содержит два натуральных числа w и h (1 ≤ w, h ≤ 100). Во второй строке записано целое число n (0 ≤ n ≤ 5000) – количество прямоугольников. Следующие n строк содержат информацию о всех прямоугольниках. Каждая строка описывает один прямоугольник в виде четырех чисел x1, y1, x2, y2 , где (x1, y1) и (x2, y2) – координаты левого верхнего и правого нижнего угла прямоугольника соответственно.


Выходные данные
Выведите в выходной файл OUTPUT.TXT одно целое число – площадь незакрашенной части холста.

Ввод и вывод в файлы реализовывать не обязательно. достаточно input(), print()
Как мне посчитать сложность алгоритма? И как оптимизировать? сторонние библиотеки нельзя использовать
Вот что у меня получилось :
w,h = input().split()
w = int(w)
k = 0
h = int(h)
sq = []
count = int(input())
arr = [[0]*h for i in range(w)]
for i in range(count):
	square = [int(l) for l in input().split()]
	for i in range(square[0],square[2]):
		for j in range(square[1],square[3]):
			arr[i][j] = 1

for i in arr:
	for j in i:
		if j==0:
			k += 1
print(k)

В одном из тестов задача не проходит по скорости. Хотя если использовать PyPy3, то все работает
  • Вопрос задан
  • 551 просмотр
Пригласить эксперта
Ответы на вопрос 3
@neol
Самый очевидный вариант: сократить количество проходов по массиву.
Второй проход вам совершенно не нужен, т. к. уже на первом можно подсчитать количество "закрашенных" точек (если точка ещё не закрашена - закрашиваем её и увеличиваем счётчик, иначе переходим к следующей). Имея количество "закрашенных" точек и площадь холста рассчёт сводится к одному действию, а сложность алгоритма уменьшается в два раза.

Если я ничего не путаю, то получится как-то так
w,h = input().split()
w = int(w)
k = 0
h = int(h)
canvasArea = w * h
count = int(input())
arr = [[0]*h for i in range(w)]
for i in range(count):
  square = [int(l) for l in input().split()]
  for i in range(square[0],square[2]):
    for j in range(square[1],square[3]):
      if arr[i][j]==0:
        k += 1
        arr[i][j] = 1
  print(canvasArea - k)


PS Маленький совет по поводу именования переменных: если вы когда-нибудь собираетесь заняться программированием за рамками олимпиадок, то вместо w,h,k и arr стоит использовать что-то типа width, height, filledCount, canvas. Так как в чуть более объемном коде будет значительно сложнее понять, что означают все эти однобуквенные переменные.
Ответ написан
igorzakhar
@igorzakhar
Разбор задачи на Reddit https://www.reddit.com/comments/zaa0v.
Адаптировал под случай который указан в условии:
прямоугольник определяется значениями (x1, y1, x2, y2), где (x1, y1) - верхний левый угол, (x2, y2) - правый нижний угол.
x1,y1───────────┐
    │           │
    │           │
    │           │
    │           │
    └───────────x2,y2

Алгоритм слудующий: находим сумму площадей всех прямоугольников и эту сумму вычитаем из площади полотна.
Площадь прямоугольника, в нашем случае, равна (x2 - x1) * (y1 - y2).

Случай 1. Прямоугольники не пересекаются.
Прямоугольники (0,3,4,0), (4,7,7,3) и (7,3,10,0) будут выглядеть примерно так:
        * * * 
        * * * 
        * * *
        * * *
* * * *       * * *
* * * *       * * *
* * * *       * * *

Общая площадь этих трех прямоугольников проста для вычисления, это всего лишь сумма площадей каждого отдельного прямоугольника: (4 * 3) + (3 * 4) + (3 * 3)

Случай 2. Прямоугольники пересекаются, общее пересечение имеют 2 прямоугольника.
Рассмотрим три прямоугольника (0,3,4,0), (2,5,5,1) и (4,7,7,4):
        * * * 
        * * * 
    * * + * * 
    * * *     
* * + + *      
* * + + *      
* * * *

Вы видите, что прямоугольники пересекаются (области, где они пересекаются, отмечены символом "+" вместо "*"). Поэтому, если мы просто вычислим сумму площадей, как мы делали раньше, 12 + 12 + 9, мы получим слишком большое значение (33 вместо 28), потому что мы рассчитываем области с пересечением дважды.
Чтобы получить правильный ответ, мы должны вычесть области, в которых пересекаются два прямоугольника: (12 + 12 + 9) - (4 + 1) = 28.

Случай 3. Общее пересечение имеют сразу несколько прямоугольников.
Рассмотрим прямоугольники (0,3,4,0), (2,5,5,1) и (3,3,0,6)
    * * *
    * * *     
* * + x + *      
* * + x + *   
* * * + * *

Теперь три прямоугольника перекрываются в точках, отмеченных символом "x" (как и раньше, знак "+", где перекрываются только два прямоугольника). Сумма площадей всех трех треугольников: 12 + 12 + 9. Затем мы должны вычесть сумму всех площадей, где пересекаются два прямоугольника 4 + 3 + 4 (прямоугольники 1 и 2 пересекаются в области с площадью 4, прямоугольники 1 и 3 пересекаются в области с площадью 3, и прямоугольники 2 и 3 пересекаются в области с площадью 4). Мы получили (12 + 12 + 9) - (4 + 3 + 4).
Однако, вычитая все области пересечения двух прямоугольников, мы вычитаем область, в которой три прямоугольника пересекаются (обозначено "x"), три раза. Поэтому мы должны добавить площадь пересечения трех прямоугольников, чтобы получить правильный результат. Таким образом, общая площадь, покрытая прямоугольниками:
A = (12 + 12 + 9) - (4 + 3 + 4) + (2) = 33 - 11 + 2 = 24

Общее правило, на самом деле, довольно простое. Если S1 - сумма площадей всех прямоугольников, S2 - сумма всех областей, где пересекаются два прямоугольника, S3 - сумма всех областей, где пересекаются три прямоугольника, S4 - сумма всех областей, где пересекаются четыре прямоугольника и т.д., значение общей площади равно:
A = S1 - S2 + S3 - S4 + S5 - S6 + S7 - S8 + ...
Это известно в математике как принцип включений-исключений, потому что вы чередуете включение и исключение областей.
Значения в нашем примере соответствуют:
S1 = 12 + 12 + 9 
S2 = 4 + 3 + 4  
S3 = 2

Пример вычисления с использованием рекурсии

def bounding_box(rects):
    return (min(r[0] for r in rects),
            max(r[1] for r in rects),
            max(r[2] for r in rects),
            min(r[3] for r in rects))


def area(rect):
    a, b, c, d = rect
    return (c - a) * (b - d)


def clip(bb, rects):
    if not rects:
        return []

    (x1, y1, x2, y2) = rects[0]
    rs = rects[1:]
    (a1, b1, a2, b2) = bb

    if a1 == a2 or b1 == b2:
        return []

    if a1 >= x2 or a2 <= x1 or y1 <= b2 or y2 >= b1:
        return clip(bb, rs)

    result = [(max(a1, x1), min(b1, y1), min(a2, x2), max(b2, y2))]
    return result + clip(bb, rs)


def cover(bb, rects):

    if not rects:
        return 0
    rc = rects[0]
    rs = rects[1:]

    (a1, b1, a2, b2) = bb
    (x1, y1, x2, y2) = rc

    top = (a1, b1, a2, y1)
    bottom = (a1, y2, a2, b2)
    left = (a1, y1, x1, y2)
    right = (x2, y1, a2, y2)

    sum_area = sum(cover(x, clip(x, rs)) for x in [top, bottom, left, right])
    return area(rc) + sum_area


def main():
    width_canvas = 10
    height_canvas = 10

    rect1 = (0, 3, 4, 0)
    rect2 = (2, 5, 5, 1)
    rect3 = (3, 3, 6, 0)
    rs = [rect1, rect2, rect3]

    painted_area = cover(bounding_box(rs), rs)
    canvas_area = width_canvas * height_canvas
    unpainted_area = canvas_area - painted_area

    print("Canvas area:", canvas_area)
    print("Painted area:", painted_area)
    print("Unpainted area:", unpainted_area)


if __name__ == '__main__':
    main()



Код на GitHub Gist
Код на GitHub с тестами
Ответ написан
Комментировать
@asd111
перепиши на java и не парься. Python редко используется для олимпиад потому что он тормозной для этого дела. Выбор олимпиадника это С#, java, С++
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы