Как доказать что мы действительно не пропустим такую пару 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

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

Благодарю!