Задача с доской NxN на которой расположены слоны

Два булевских массива по номерам диагоналей. Для нового слона если диагональ ещё не использовалась, вычитаешь её длину. После этого заносишь в массив.

В описанном алгоритме ошибка: часть клеток вычитаются многократно, что к этому прибавить, я пока не понимаю.

Есть вариант при подсчёте слона вычитать из длин всех затрагиваемых диагоналей по 1, но это портит асимптотику и O(n+m) превращается в O(n*m), что не подходит под условия. Можно попробовать оптимизировать эту чать каким-нибудь деревом (Фенвика или отрезков), но я не думал в эту сторону, потому что почти наверняка должно быть линейное решение, а не такое.

По входным данным можно понять, что тут либо:

1. Алгоритм с параллельным просмотром разрядов за O(~nm),этот тот алгоритм, при котором мы используем битовые операции,даже при таких входных данных будет работать быстро не факт, что очень быстро
2. Формула

Скорее второе. Мы нумеруем диагонали в массиве, можно заметить что в каждой диагонали уменьшается кол-во клеток на 1. Но тут есть проблема, что слоны могут бить одну и ту же клетку, тогда формула работать не будет. А ответ, что привели выше работает как решето Эратосфена, O(~nm), а это слишком долго. Поэтому либо надо знать какое ограничение по времени, либо придумывать умную формулу.

Кажется придумал умное решение:

Что же мы делаем, заводим для каждой диагонали сет(кч дерево работает за log(n)), после постановки слона мы удаляем все клетки, которые нам не нужны, которые он бьет, можно доказать что асимптотика не O(log(n)(n*m)),а O(log(n)(n+m)), потому что с каждым ходом слон точно вычёркивает один сет, а значит подсчет на каждом этапе будет уменьшаться

Еще одно умное решение: Делаем ДО на диагоналях и просто на каждом этапе пересчитываем сумму, это делается ленивым за log(n), а в итоге сложность будет mlog(n), так как ДО с обновлением на отрезке будет работать за log(n)(ленивое обновление). ъ

Готовый код (Python):

size = int(input("Размер шахматной доски: "))
amount = int(input("Количество слонов: "))
print("")

def print_board(board):
    for lines in range(size):
        print(board[lines])
    print("")

board = []
board_2 = []
for row in range(size):
    board.append([])
    board_2.append([])
    for number in range(size):
        board[row].append(0)
        board_2[row].append(0)

f=0
while (f < amount):
    location_y = size - int(input("Введите строку слона: "))
    location_x = int(input("Введите столбец слона: ")) - 1
    board[location_y][location_x] = 1
    board_2[location_y][location_x] = 1
    f+=1

for row in range(size):
    for number in range(size):
        if (board[row][number] != 0):
            for n in range(1,size):
                if ((number+n <= size) and (row+n <= size)):
                    try:
                        board_2[row+n][number+n]=1
                    except:
                        None
                if ((number-n >= 0) and (row+n <= size)):
                    try:
                        board_2[row+n][number-n]=1
                    except:
                        None
                if ((number+n <= size) and (row-n >= 0)):
                    try:
                        board_2[row-n][number+n]=1
                    except:
                        None
                if ((number-n >= 0) and (row-n >= 0)):
                    try:
                        board_2[row-n][number-n]=1
                    except:
                        None
print_board(board_2)

zero=0
for row in range(size):
    zero = zero + board_2[row].count(0)

print(zero)

input()

При вызове input() показывается немного текста - подсказка к следующему действию.

Если подсказки не нужны, замените все конструкции input(...) на input()

Ограничения на размер поля, количество и расположение слонов думаю сможете добавить сами.

Теория

Координаты клетки обозначим (x, y), 1 <= x, y <= n. Диагонали описываются уравнениями:

x + y = s # s-диагональ (sum)
x - y = d # d-диагональ (diff)

Самая длинная (длиной n) s-диагональ проходит через углы (n, 1) и (1, n). Следовательно s = n + 1. Длина любой s-диагонали n - |n + 1 - s|.

Самая длинная (длиной n) d-диагональ проходит через углы (1, 1) и (n, n). Следовательно d = 0. Длина любой d-диагонали n - |d|.

Лемма: пусть s и d одинаковой четности. s-диагональ пересекается с d-диагональю тогда и только тогда когда сумма их длин больше n.

Практика

Составим множество чётных s-диагоналей занятых слонами. Аналогично построим множество чётных d-диагоналей. Слово "множество" означает что дубликаты диагоналей устранены.

Чтобы посчитать количество клеток покрытых чётными диагоналями нужно из суммы их длин вычесть количество попарных пересечений s- и d-диагоналей. Две конкретные диагонали пересекаются если сумма их длин больше n.

Конкретная s-диагональ пересекает все d-диагонали с длиной больше |n + 1 - s|. Если вектор (не множество) длин d-диагоналей отсортировать по убыванию, можно отыскать индекс (i) первой d-диагонали которая не пересекается с s-диагональю. Все диагонали до этого индекса пересекаются с s-диагональю.

Для ускорения процесса вектор длин s-диагоналей отсортируем по возрастанию длины. Тогда при увеличении длины s-диагонали индекс i не убывает.

Подсчёт занятых клеток займёт O(mlogm), где m - число диагоналей (равно числу слонов в худшем случае). Это время займёт сортировка длин диагоналей. Дальнейший подсчёт пересечений делается за O(m).

Нечётные s- и d-диагонали обрабатываются аналогично.

Программа

def slen(n, s):
    return n - abs(n + 1 - s)


def dlen(n, d):
    return n - abs(d)


def attacked(n, sset, dset):
    slens = sorted( slen(n, s) for s in sset               )
    dlens = sorted((dlen(n, d) for d in dset), reverse=True)
    dlens.append(0) # sentinel

    sum_ = sum(slens) + sum(dlens)

    i = 0
    for sl in slens:
        while dlens[i] > n - sl:
            i += 1
        sum_ -= i
    return sum_


def available(n, poses):
    se = set()
    so = set()
    de = set()
    do = set()
    for x, y in poses:
        d = x - y
        s = x + y
        assert s % 2 == d % 2
        if s % 2 == 0:
            se.add(s)
            de.add(d)
        else:
            so.add(s)
            do.add(d)

    return n ** 2 - attacked(n, se, de) - attacked(n, so, do)


def main():
    n, m, *poses = map(int, input().split())
    it = iter(poses)
    print(available(n, zip(it, it)))


main()