LINUX.ORG.RU

Задача с hackerrank

 ,


0

4

Дописать ф-ю, у которой параметры - это 4 списка.
p - количество людей в каждом городе (int >0)
x - расположение каждого города (int>0)
y - расположение каждого облака (int>0)
r - радиус каждого облака (int), соответственно начало и конец облака c индексом i (Yi-Ri, Yi+Ri).

Необходимо удалить одно облако так, чтобы общее количество людей в городах вне облаков стало максимально возможным.

В списке участников, прошедших все тесты, решения в основном на с++ и java (на каждые 20 участников c максимум баллов - 1 питонист).
Первый же питонист в топе списка, как оказалось, переписал полностью вот этот код ниже, который трогать не предполагается и соответственно его ф-я принимает другие параметры, переделанные списки и прочее.

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    p = list(map(int, input().rstrip().split()))

    x = list(map(int, input().rstrip().split()))

    m = int(input())

    y = list(map(int, input().rstrip().split()))

    r = list(map(int, input().rstrip().split()))

    result = maximumPeople(p, x, y, r)

    fptr.write(str(result) + '\n')

    fptr.close()

Мое решение ниже проходит всего 11 тестов из 28, когда начинаются списки из 200 000 элементов то Terminated due to timeout error.
В связи с чем у меня вопрос, эту задачу в принципе возможно решить на Python? И если да, то какой подход использовать?

def maxSun(p, x, y, r):
    # Return the maximum number of people that will be in sunny towns after removing exactly one cloud.
    from collections import defaultdict
    from itertools import chain

    lY,lX=range(len(y)),range(len(x))

    by_length=sorted(((y[i] - r[i], y[i] + r[i]) if (y[i] - r[i]) >= 0
                      else (0, y[i] + r[i])
                      for i in lY), key=lambda x: x[1]- x[0], reverse=True)


    if not by_length[1:]:  # remove first largest range
        return sum(p)


    d=defaultdict(list)

    for tupl in by_length[1:]:
        if not d:

            for i in lX:
                if x[i]<tupl[0] or x[i]>tupl[1]:
                    d[x[i]].append(p[i]) #X beyond second largest range; form a dict
            if not d:  #no X-elements beyond second largest range
                return 0
        else:

            for X in d.copy():  #exclude X within other ranges from a dict
                if X >=tupl[0] and X<=tupl[1]:
                    del d[X]
                    if not d:
                        return 0


    return sum(chain(*d.values()))

Возможно, большая часть облаков примерно одинаковые по длине и расположению (с несущественными различиями). В результате чего у меня после исключения всех X из второго по протяженности облака, все добавленные в словарь X снова бесполезно проверяются на следующих примерно равных по длине и расположению облаках.

hibiscusM ()

когда начинаются списки из 200 000 элементов

На 200К городов и 50 облаков минуты 3 ушло.

vvn_black ★★★★★ ()
Последнее исправление: vvn_black (всего исправлений: 1)
Ответ на: комментарий от MyTrooName

типа, посчитать частичные суммы по координатам (нужны не все 10^9 координат, а только те, на которых лежит город или граница облака - всего 3*10^5 максимум):

  1. P_0 население, не покрытое облаками

  2. P_1 население, покрытое не более чем одним облаком

дальше перебрать все облака, и для каждого облака сложить P_0 слева от облака, плюс P_1 внутри облака плюс P_0 справа от облака; и выбрать облако с лучшим результатом

на все про все O(n log n) походу

и отдельно проработать случаи, когда город на границе облака

MyTrooName ★★★★★ ()
Последнее исправление: MyTrooName (всего исправлений: 3)
Ответ на: комментарий от MyTrooName

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

спасибо, попробую.

hibiscusM ()
Ответ на: комментарий от MyTrooName

P_1 население, покрытое не более чем одним облаком

Определить сколькими облаками покрыт город тоже как-то надо.

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

Я бы подумал о реализации быстрого получения списка городов, над которым находится конкретное облако. Имея это, думаю можно сделать всё остальное.

xaizek ★★★★★ ()

В связи с чем у меня вопрос, эту задачу в принципе возможно решить на Python? И если да, то какой подход использовать?

насколько я помню, на hackerrank увеличенные лимиты времени для решений на python. Так что да, решение точно есть.

И если да, то какой подход использовать?

избавиться от dict, chain и вот этого всего. Придумать решение с асимптотикой O(n log n), в котором используется только сортировка и проходы по массивам в цикле for. (небольшая подсказка: если одно облако лежит целиком внутри другого, то очевидно, его нет смысла убирать)

anonymous ()

Мне показалось, что нашёл приемлимый вариант, Test Case #26 (200К зданий, 100К облаков) проходит влёт.

Но, вот на решение такого варианта, просто не хватает ресурсов ПК )

p = (814442966, )
x = (450418, )
y = (638572, )
r = (570738426, )

vvn_black ★★★★★ ()
Ответ на: комментарий от MyTrooName

типа, посчитать частичные суммы по координатам (нужны не все 10^9 координат, а только те, на которых лежит город или граница облака - всего 3*10^5 максимум)

верно, нужно занести все 3*10^5 координат в один массив и отсортировать. Тогда мы легко сможем определить для каждого города, сколькими облаками он покрыт.

и отдельно проработать случаи, когда город на границе облака

можно например умножить каждую координату на 3, и затем к координатам городов прибавить 1, а к правым концам облаков - 2. Тогда все города будут лежать либо строго внутри облаков, либо строго вне.

anonymous ()
Ответ на: комментарий от xaizek

Я бы подумал о реализации быстрого получения списка городов, над которым находится конкретное облако. Имея это, думаю можно сделать всё остальное.

100к - это типичный для олимпиадных задачек размер, который намекает, что все нужно сделать за O(nlog n). быстрее чем за O(n) в общем случае список городов под облаком не получить, ввиду того что его размер O(n)

крайний пример: все облака покрывают все города каждый

MyTrooName ★★★★★ ()
Последнее исправление: MyTrooName (всего исправлений: 3)

Python не знаю, поэтому попробовал на перле. Решается не сложно. Сортируем список городов по положению и добавляем туда дополнительное поле указывающее на то покрыт ли город облаком и каким или несколькими. Облака переводим в формат начало-конец и тоже сортируем. Потом проходим одним циклом все города в процессе добавляя в отдельный список облака если они покрывают данный город и считаем популяцию.

У алгоритма есть некоторые минусы, если по серьезному можно пробовать seg tree или еще что-то придумать.

anonymous ()
Ответ на: комментарий от anonymous

Понятно. А у меня не получилось на Питоне. И первое питоновское решение, которое удалось найти, мне показалось, слишком мудреное. А как в бизнесе/на пратике подобные задачи сформулированы?

hibiscusM ()
Ответ на: комментарий от hibiscusM

если ты про это решение, то оно примерно такое, как тут говорилось.

cloud_start - список облаков, отсортированный по координате начала. cloud_end - список облаков, отсортированный по координате конца. clouds - сет облаков, покрывающих данный город. d - сколько человек живет в городах, покрытых только данным облаком.

  • Проходим по отсортированному массиву городов.
  • Добавляем в clouds все облака, у которых координата начала меньше координаты текущего города.
  • Удаляем из clouds все облака, у которых координата конца меньше координаты текущего города.
  • Смотрим, сколько облаков в clouds. Если 0 - добавляем город сразу в ответ, если 1 - добавляем его в d.

Чтобы пункты 2 и 3 не приводили к квадратичному решению, просматриваем массивы cloud_start и cloud_end не с начала, а с индекса, на котором мы остановились на предыдущем городе (cloud_start_i и cloud_end_i). Тогда каждый индекс будет просмотрен не более 1 раза, и эта часть решения сработает за O(n). Прием называется «two pointers method», вместо него можно использовать обычный двоичный поиск (bisect_left и т.п.)

anonymous ()
Ответ на: комментарий от anonymous

Я про это.

import operator


# Complete the maximumPeople function below.
def maximumPeople(people, tower_pos, lclouds, lranges):
    # make list of cloud tuples with start and end
    clouds = []
    for c, r in zip(lclouds, lranges):
        clouds.append((max(c - r, 0), c + r))
    # sort by start
    clouds.sort(key=lambda x: x[0])

    # make list of tower tuples with position and people
    towers = []
    for pos, p in zip(tower_pos, people):
        towers.append((pos, p))
    # sort by start
    towers.sort(key=lambda x: x[0])

    # add a ghost cloud (to do all in one while loop)
    last_tower_pos = towers[-1][0]
    last_cloud = clouds[-1][1]
    ghost_pos = max(last_tower_pos, last_cloud) + 100

    # insert ghost cloud
    clouds.append((ghost_pos, ghost_pos))

    # end of the current cloud interval
    cend = -10 * 9

    # counter to check soleley covered people by current cloud
    covered = 0

    # counter for people not covered by a cloud at all
    uncovered = 0

    # to remember maximum count
    max_covered = 0

    # index for the
    t_idx = 0

    # helper function to count people before a certain position
    def count(pos, exc=False):
        res = 0
        nonlocal t_idx
        # uses less than or less or equal operator
        op = operator.lt if exc else operator.le
        while (t_idx < len(towers)
               and op(towers[t_idx][0], pos)):
            # op: a<b or a<=b
            res += towers[t_idx][1]
            t_idx += 1
        return res

    # the actual algorithm
    # there are three cases considered:
    for start, end in clouds:
        # next cloud start after the end of old cloud
        if start > cend:
            covered += count(cend)
            max_covered = max(max_covered, covered)
            covered = 0
            uncovered += count(start, exc=True)
            cend = end
        # next cloud starts and ends before the next cloud
        elif start <= cend and end < cend:
            covered += count(start, exc=True)
            _ = count(end)
        # or it starts before but ends later
        elif start <= cend and end >= cend:
            covered += count(start, exc=True)
            max_covered = max(max_covered, covered)
            covered = 0
            _ = count(cend)
            cend = end

    return max_covered + uncovered

hibiscusM ()
Ответ на: комментарий от anonymous

как было указано на сайте, задача была на greedy algorithms. тут .

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage[1] with the intent of finding a global optimum. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

из википедии.

Мне не очень понятно, где в этих двух решениях greedy algorithm? Принять локально оптимальные решения на каждом этапе, что в итоге апроксимируется в глобально оптимальное решение. Не требуется находить лучшее решение, требуется найти оптимальное решение.

hibiscusM ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.