Как доказать что мы действительно не пропустим такую пару i,j которая дает правильный ответ в методе двух указателей?

Question

[Егор Полянский]

Помогите пожалуйста с вопросом, указанным выше. Дана задача (на скриншоте)

Я написал код:

def two_pointers(A, B, C): # O(K * (N + M))
    result = []
    for c in C:
        i, j = 0, len(B) - 1
        found = False

        while i < len(A) and j >= 0:
            current_sum = A[i] + B[j]
            if current_sum > c:
                j -= 1
            elif current_sum < c:
                i += 1
            else:
                found = True
                result.append('YES')
                break

        if not found:
            result.append('NO')

    print("\n".join(result))


N = int(input())
if N > 0:
    A = sorted(map(int, input().split())) # O(NlogN)
else:
    s = input()

M = int(input())
if M > 0:
    B = sorted(map(int, input().split())) # O(MlogM)
else:
    s = input()

K = int(input())
if K > 0:
    C = list(map(int, input().split()))

if N > 0 and M > 0 and K > 0:
    two_pointers(A, B, C) # O(NlogN + MlogM + K * (N + M))
elif K > 0:
    for _ in C:
        print('NO')

def two_pointers(A, B, C): # O(K * (N + M))
result = []
for c in C:
i, j = 0, len(B) - 1
found = False

while i < len(A) and j >= 0:
current_sum = A[i] + B[j]
if current_sum > c:
j -= 1
elif current_sum < c:
i += 1
else:
found = True
result.append('YES')
break

if not found:
result.append('NO')

print("\n".join(result))

N = int(input())
if N > 0:
A = sorted(map(int, input().split())) # O(NlogN)
else:
s = input()

M = int(input())
if M > 0:
B = sorted(map(int, input().split())) # O(MlogM)
else:
s = input()

K = int(input())
if K > 0:
C = list(map(int, input().split()))

if N > 0 and M > 0 and K > 0:
two_pointers(A, B, C) # O(NlogN + MlogM + K * (N + M))
elif K > 0:
for _ in C:
print('NO')

Преподаватель задал вопрос:
Как доказать что мы действительно не пропустим такую пару i,j которая дает правильный ответ в методе двух указателей?
Вроде бы доказательство не сложное, но помимо этого был вопрос по типу: Как мы гарантируем то, что мы не перескочим через указатели во время проверки?

Прошу помочь с данными вопросами, желательно как можно подробнее

Comments

[Lynn «Кофеман»]

вообще алгоритм выглядит неверным

а, не дочитал до сортировки

Answer 1

[Wataru]

В такой реализации это плохо видно, но можно переписать основной цикл так:

j = Len(B)-1
for i in range(len(A)):
  while j >= 0 and A[i] + B[j] > c:
    --j;
  if A[i] + B[j] == c:
    found = True
    break

В этом случае после цикла while поддерживается инвариант, что a[i]+b[j] <= c и это максимальное такое j.
Ведь, если этот инвариант поддерживался для пердыдущей итерации, то у нас было a[i-1] +b[j] <=c и a[i-1]+b[j+1]>c. Отсюда получается, a[i]+b[j+1] >= a[i-1]+b[j+1] > c. Т.е. если мы уменьшим j в цикле while инвариант останется действовать - это будет самое большое j, т.ч. a[i]+b[j] <= c.

А этот инвариант гарантирует, что когда в цикле по i переберется значение из ответа, j гарантированно будет указываать на j из ответа. Потому что, если существуют i', j', т.ч. a[i']+b[j'] = c, то можно увеличить j' пока b там не меняется, т.ч. b[j']>b[j'], отсюда получается a[i']+b[j'] <=c и a[i']+b[j+1] > c - а это и есть наш инвариант. Т.е. на итерации i=i' найдется именно j=j'.

Comments

[Егор Полянский]

Благодарю!

[Wataru]

Егор Полянский, еще вариант: можно доказать, что ваш алгоритм выкидывает из рассмотрения точно не нужные пары.

Если a[0]+b[n-1]<c, то a[0] - слишком маленькое. Даже с максимальным b оно дает слишком маленкую сумму, а значит любая пара с a[0] не наберёт искомую сумму, ведь остальные пары еще меньше. Значит, можно a[0] выкинуть из рассмотрения. Точно также можно выкинуть b[n-1], если сумма слишком большая.

Поскольку мы ни одну пару с искомой суммой из рассотрения не удаляем, ответ найдется.

Можно это и через инвариант доказать. В начале цикла, если в массиве есть искомая пара i', j', то i' >= i и j' <= j. После манипуляций этот инвариант сохраняется.

[floppa322]

можно же проще, 70-80% алгоритмов с двумя указателями доказываются, тем, что, если в наборе данных (массиве) есть 2(или m) значений, то указатели их не могут пропустить

доказательство сводится к тому, что нужно перебрать все варианты (их обычно не много) положений указателей и показать, что они обязательно не пропустят ответ

Answer 2

[Alexandroppolus]

мы стартуем с i = 0 и j = M-1. Пусть ближайшее решение находится в индексах i0, j0

рассмотрим возможные состояния:
1) мы уже в (i0, j0), решение найдено
2) мы в (i0, b), где b > j0. Здесь сумма больше чем С, мы просто уменьшаем j до j0 и приходим в п.1
3) мы в (a, j0), где a < i0. Сумма меньше С, увеличиваем i до i0, приходим в п1
4) мы в (a, b), где a < i0 и b > j0. Поскольку i может только увеличиваться, а j - только уменьшаться, то выйдем на п.2 или п.3, а оттуда на п.1

Поскольку стартовали мы гарантированно из состояния 1...4, то все прочие состояния невозможна, потому что кейсы 1...4 уводят на п.1

Вывод: мы не проскочим решение (i0, j0).

ps: для наглядности можно разместить все точки (i, j) на координатной плоскости и заметить, что (i0, j0) - не просто точка, которую можно "обойти": она задает прямоугольник, в котором мы находимся на старте и из которого мы не выйдем, перепрыгнув через сторону.