@SilentGr0ve
Первокурсник

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

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

Я написал код:
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 которая дает правильный ответ в методе двух указателей?
Вроде бы доказательство не сложное, но помимо этого был вопрос по типу: Как мы гарантируем то, что мы не перескочим через указатели во время проверки?

Прошу помочь с данными вопросами, желательно как можно подробнее
  • Вопрос задан
  • 158 просмотров
Решения вопроса 1
wataru
@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'.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Alexandroppolus
@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) - не просто точка, которую можно "обойти": она задает прямоугольник, в котором мы находимся на старте и из которого мы не выйдем, перепрыгнув через сторону.
Ответ написан
Комментировать
Ваш ответ на вопрос

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

Похожие вопросы