Почему 3 секунд не хватает для выполнения кода?

Question

[WSGlebKavash]

Условие:

Задача 2.7. Прогнозирование
Ограничение времени: 3 секунды
[Программирование]

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

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

Исходя из этого, он просит вас написать программу, которая посчитает, какое максимальное количество матчей его команда проиграет при худшем исходе.

Формат входных данных

В первой строке входных данных записано целое число n (1≤n≤2⋅10^5) -− количество участников в каждой команде и, одновременно, количество матчей в финале. Во второй строке записано nn целых чисел ai (1≤a ≤10^9) -− силы участников команды синих. В третьей строке записано n целых чисел bi (1≤b≤10^9) -− силы участников команды красных.

Формат выходных данных

Выведите одно целое число -− максимальное количество матчей, которое команда синих проиграет при худшем исходе.

Пример входных данных
5
2 3 1 4 3
1 2 1 2 2

Пример выходных данных
2

Пояснение к примеру:

Команда синих при худшем исходе проиграет первых два матча. В первом матче они поставят участника с силой 1 против участника команды красных с силой 2. Во втором матче они поставят участников с силой 1 и 2 против участников команды красных с силами 2 и 2. В третьем матче получится ничья. В четвертом и пятом матче команда синих выигрывает.

Я попытался решить задачу с помощью массивов. Я находил минимальные и максимальные значения для каждого раунда и считал сумму сил. Однако код проходит 6 тестов из 17 и выдаёт ошибку: Time limit exceeded.
Как можно оптимизировать код, чтоб он укладывался в 3 секунды?

Код

import copy
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count = 0;
for i in range(n):
    if i+1 == 1:
        blue = min(a)
        red = max(b)
        if blue < red:
            count += 1
    else:        
        bluelist = copy.deepcopy(a)
        redlist = copy.deepcopy(b)
        blueround = []
        redroud = []
        for j in range(i+1):
            blueround.append(min(bluelist))
            bluelist.remove(min(bluelist))
            redroud.append(max(redlist))
            redlist.remove(max(redlist))
        if sum(blueround) < sum(redroud):
            count += 1
print(count)

Comments

[Dimonchik]

https://www.w3schools.com/python/python_lists_comp...

видно что Вы ими не владеете совершенно
ибо
b = a[:]

безо всяких copy deepcopy

то же и циклов касается

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

[WSGlebKavash]

Dimonchik,

b = a[:]

Пробовал. Прироста производительности не даёт.
Спасибо за внимание!

[Dimonchik]

WSGlebKavash, так там надо остальные циклы переписать выражениями )

Answer 1

[Wataru]

У вас решениe за O(n^3), ибо у вас там 2 вложенных цикла до n, а внутри еще и постоянно вызываются min/max, которые проходятся по всему массиву.

Ограничения же в задаче n<10^5. С такими ограничениями максимум O(n log n) решение уложится в 3 секунды.

Подумайте, как его можно изменить, чтобы работало сильно быстрее? Подсказка: сначала вы берете 1 минимальный элемент, потом 2 самых маленьких, потом 3, и т.д. На второй итерации вам уже как бы не надо искать минимум- вы его уже знаете. Вас интересуют только оставшиеся числа. На третьей итерации у вас уже 2 числа раньше найдены. Надо как-то переиспользовать предыдущие вычисления.

Что можно сделать с входным массивом, чтобы можно было получать несколько самых маленьких элементов быстро? Помните, что вам надо уложиться в O(n log n).

Answer 2

[Руслан .]

Тут наверное имеет смысл один раз отсортировать bluelist и redlist и далее просто по одному массиву идти с начала, там где нужно брать минимальный элемент, а по второму с конца, там где нужно брать максимальный элемент

Comments

[WSGlebKavash]

Руслан ., Огромнейшее спасибо за предложение. 11 из 17 тестов пройдено.

[Руслан .]

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

[WSGlebKavash]

Руслан ., Вот тако получилось:

import copy
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()  # Сортировка сил участников команды синих по возрастанию
b.sort()  # Сортировка сил участников команды красных по уб
count = 0;
for i in range(n):
    if i+1 == 1:
        blue = a[0]
        red = b[-1]
        if blue < red:
            count += 1
    else:
        if sum(a[:i+1:]) < sum(b[:-(i+2):-1]):
            count += 1
print(count)

12 из 17 тестов пройдено

[Руслан .]

WSGlebKavash, вам не нужно копировать списки каждый раз чтобы взять суммы. Тут суммы i - й итерации равны сумме i-1 итерации плюс два новых элемент один из одного массива (минимального) , а второй из другого (максимального).

[WSGlebKavash]

Руслан ., Получилось что-то такое:

#5
#2 3 1 4 3
#1 2 1 2 2
import copy
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()  # Сортировка сил участников команды синих по возрастанию
b.sort() # Сортировка сил участников команды красных по уб
summin = 0
summax = 0
count = 0;
for i in range(n):
    if i+1 == 1:
        blue = a[0]
        red = b[-1]
        if blue < red:
            count += 1
    if i+1 == 2:
        summin = sum(a[:2:])
        summax = sum(b[:-3:-1])
    else:
        if summin < summax:
            count += 1
        summin += a[i]
        summax += b[-i]
print(count)

Огромнейшее, приогромнейшее спасибо!!! Вроде работает.

[Руслан .]

WSGlebKavash, в целях перфекционизма можно ещё немного порефакторить код. Например вынести из цикла часль if, которые срабатывают только один раз. А так шаг за шагом мы пришли примерно к тому о чем писал Wataru Wataru