Сильно в фоновом режиме прохожу курс института Сан-Диего по алгоритмам.
Так сказать гешефт прикрываю
Вот четкая формулировка: даны начала отрезков (массив), конец отрезков (массив)
и точки (массив). Для каждой точки посчитать число интервалов, куда она входит.
И конкретно туплю -- у меня время решения (не знаю единиц) что-то типа 500 из 20. где туплю, но туплю, видимо, сильно. В общем вот:
#скачал из интернетов -- возвращает число меньших эл-во чем заданный в отсортированном массивеdef binarySearchCount(arr: List[Tuple[int, int]],item, key):
left = 0
n = len(arr)
right = n - 1
count = 0
while left <= right:
mid = (right + left) // 2
# Check if middle element is
# less than or equal to keyif arr[mid][item] < key:
# At least (mid ) elements are there
# whose values are less than
# or equal to key
count = mid
left = mid + 1
# If key is smaller, ignore right halfelse:
right = mid - 1
return count
def fast_count_segments(starts: List[int], ends: List[int], points: List[int]):
cnt = [0] * len(points)
tups_sort_by_end = [(starts[i], ends[i]) for i in range(len(ends))]
tups_sort_by_start = [(starts[i], ends[i]) for i in range(len(ends))]
# сортирую по началу и концу nlog(n)
tups_sort_by_end.sort(key=lambda tup: tup[1])
tups_sort_by_start.sort(key=lambda tup: tup[0])
l_s = len(tups_sort_by_end)
d = {}
for i in range(len(points)):
if points[i] in d:
cnt[i] = d[points[i]]
continue# смотрю, где меньше итераций(к началу или к концу)
idx_e = binarySearchCount(tups_sort_by_end, 1, points[i])
idx_s = binarySearchCount(tups_sort_by_start, 0, points[i])
# лежит во всех интервалах, готово, идем дальшеif idx_s == l_s and idx_e == 0:
cnt[i] = l_s
else:
if idx_s == idx_e:
for j in range(idx_e, l_s):
if tups_sort_by_end[j][0] <= points[i] <= tups_sort_by_end[j][1]:
cnt[i] += 1
else:
if idx_s > l_s - idx_e:
# к концу быстрееfor j in range(idx_e, l_s):
if tups_sort_by_end[j][0] <= points[i] <= tups_sort_by_end[j][1]:
cnt[i] += 1
else:
# к началу быстрееfor j in range(0, idx_s + 1):
if tups_sort_by_start[j][0] <= points[i] <= tups_sort_by_start[j][1]:
cnt[i] += 1
d[points[i]] = cnt[i]
return cnt
Глава называется Divide and Conquer, ничего лучше чем отсортировать, бинарным поиском отсечь лишнее, а дальше
по всем оставшимся пройти и проверить, я не придумал. Однако в одном из тестов по времени я сильно не укладываюсь,
причем сами данные не показывают....
ЧЯДНТ? Думается, что можно как-то избавиться от циклов после (дважды)бинарного поиска...
Никто не поможет? Задача(формулировка) вроде простая -- даны начала отрезков (массив), конец отрезков (массив)
и точки (массив). Для каждой точки посчитать число интервалов, куда она входит.
Здравствуйте, Sharov, Вы писали: S>Никто не поможет? Задача(формулировка) вроде простая -- даны начала отрезков (массив), конец отрезков (массив) S>и точки (массив). Для каждой точки посчитать число интервалов, куда она входит.
Ту же понимаешь, что формулировку задачи нужно было написать в первом же сообщении?
Там вместо этого написано, что ты что-то сделал и что это не работает. Предлагаешь другим догадываться, что именно нужно было сделать и в чём была ошибка?
Вообще, раз у тебя все запросы доступны заранее, то это типичная offline-задача: их часто можно гораздо быстрее решить, если не обрабатывать каждый запрос по отдельности (как в online), а делать их кучей.
Тут достаточно слить все три входящих массива в один и отсортировать его. Дальше пройтись один раз с любого из концов и обновлять число обрамляющих интервалов, а при встрече запроса копировать в него текущий счётчик.
…
def count_segments(starts: List[int], ends: List[int], points: List[int]):
# замкнутый интервал
S, E, Q = 0, 2, 1 # [u, v]
# варианты для открытых/полуоткрытых интервалов
# S, E, Q = 2, 0, 1 # (u, v)
# S, E, Q = 0, 1, 2 # [u, v)
a = []
for b, l in ((S, starts), (E, ends), (Q, points)):
a.extend((i << 2) | b for i in l)
a.sort()
c = 0
d = {}
for v in a:
t = v & 3
if t == S:
c += 1
elif t == E:
c -= 1
elif t == Q:
p = v >> 2
d[p] = c # тут можно ещё быстрее, если убрать промежуточный хещ-массив, а сразу хранить индекс точки, куда нужно записать ответelse:
assert False
return [d[p] for p in points]
Здравствуйте, watchmaker, Вы писали: W>Ту же понимаешь, что формулировку задачи нужно было написать в первом же сообщении? W>Там вместо этого написано, что ты что-то сделал и что это не работает. Предлагаешь другим догадываться, что именно нужно было сделать и в чём была ошибка?
Ага, виноват, дописал. Мне казалось данная задача известна, поэтому можно в общих чертах.
W>Тут достаточно слить все три входящих массива в один и отсортировать его. W>
Выше осн. идея -- прохожу по точкам и считаю открытые интервалы (счетчик интервалов), верно?
Просто, как я выше написал, глава называется Divide and conquer, мастер теорема и т.п.
Соотв. решение ожидается с соотв. техникой или с применением классических алгоритмов для данной техники --
например бинарный поиск, быстрая сортировка. Соотв. ничего лучше чем отсортировать по началу и концу
точек я не придумал, равно как и использовать бинарный поиск, чтобы понять в каком направлении быстрее.
Но это, похоже, совсем мимо. А идей совсем не осталось...
Здравствуйте, Sharov, Вы писали:
S>ЧЯДНТ? Думается, что можно как-то избавиться от циклов после (дважды)бинарного поиска...
Можно. Количество отрезков — это количество начал отрезков левее точки минус количество концов отрезков левее точки. Правда нужно аккуратно разобраться со вхождением (одно считается включительно, другое — нет). Можно два бинарных поиска написать. А можно обработать minint (он вообще у вас во входе бывает?) и считать концы тем же методом, что и начала, но на одну точку левее.
Здравствуйте, Sharov, Вы писали:
S>Вот четкая формулировка: даны начала отрезков (массив), конец отрезков (массив) S>и точки (массив). Для каждой точки посчитать число интервалов, куда она входит.
Подсчитывай интервалы, в которые НЕ входит заданная точка:
— отрезки, находящиеся полностью левее точки p (конец отрезка < p)
— отрезки, находящиеся полностью правее точки p (p < начало отрезка)
Точка входит в остальные отрезки. Ответ = общее количество отрезков минус количество "ненужных" отрезков.
Каждый из этих пунктов делается бинарным поиском по отсортированному массиву начал и концов отрезков.
Сложность алгоритма O(N*logM) (N точек, M-отрезков). Это если нужен "Divide and conquer"
Этот же подход можно использовать и для реализации за O(N+M). Здесь отсутствует необходимость применять бинарный поиск:
— отсортировать все искомые точки по возрастанию
— по мере прохождения по искомым точкам двигать указатели в отсортированных массивах начал и концов отрезков
Здравствуйте, Буравчик, Вы писали:
Б>Подсчитывай интервалы, в которые НЕ входит заданная точка: Б>- отрезки, находящиеся полностью левее точки p (конец отрезка < p) Б>- отрезки, находящиеся полностью правее точки p (p < начало отрезка) Б>Точка входит в остальные отрезки. Ответ = общее количество отрезков минус количество "ненужных" отрезков.
Это плохая идея, поскольку отрезки выше могут совпадать, соотв. посчитаю их дважды.
Б>Этот же подход можно использовать и для реализации за O(N+M). Здесь отсутствует необходимость применять бинарный поиск: Б>- отсортировать все искомые точки по возрастанию Б>- по мере прохождения по искомым точкам двигать указатели в отсортированных массивах начал и концов отрезков
Ну да, так и сделал. См. выше комментарий watchmaker'а.
где туплю, но туплю, видимо, сильно. В общем вот:
