Задача "Борьба с рутиной"

@STALKER77777 · Регистрация: 07.07.2022

Студворк — интернет-сервис помощи студентам

Здравствуйте, прошу помощи с решением данной задачи:

Борьба с рутиной
(Время: 2 сек. Память: 16 Мб Сложность: 52%)
Важным элементом повышения эффективности работы сотрудников является борьба с рутиной. Построим математическую модель разнообразия типов заданий, выполняемых сотрудником в компании.

Рассмотрим работу сотрудника в течение n последовательных рабочих дней. Будем считать, что каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый сотрудником в i-й день, целым числом ai.

Для оценки рутинности работы сотрудника будем использовать следующую характеристику. Зафиксируем целое число d и рассмотрим все отрезки из d подряд идущих рабочих дней. Для каждого такого отрезка найдём количество различных типов заданий, которые работник выполнял на протяжении этих дней, и просуммируем эти значения. Полученную величину обозначим как Sd и будем называть её d-разнообразием. Чем d-разнообразие выше, тем больше различных типов заданий выполнял сотрудник. Профилем вариативности сотрудника будем называть массив значений [S1, S2, ... , Sn].

Требуется написать программу, которая по заданной последовательности a1, a2, ... , an типов выполняемых сотрудником заданий вычисляет его профиль вариативности.

Входные данные
В первой строке входного файла INPUT.TXT находится единственное целое число n — количество последовательных рабочих дней, которые необходимо проанализировать (1 ≤ n ≤ 2×105).

Во второй строке находится n целых чисел a1, a2, ... , an — типы заданий, которое выполнял сотрудник (1 ≤ ai ≤ 109).

Выходные данные
В выходной файл OUTPUT.TXT выведите n целых чисел: S1, S2, ... , Sn.
Примеры
№ INPUT.TXT OUTPUT.TXT
1 5
1 3 2 1 2 5 8 8 6 3
2 3
10 10 10 3 2 1
##################

Сам я писал код на питоне, кому интересно, вот он:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
n = int(input())
a = list(map(int, input().split()))
s = []
q = []
q1 = []
for d in range(n):
    if a[d] not in q:
        q.append(a[d])
        q1.append(d)
        if d > 1:
            s.append(d)
    else:
        j = q.index(a[d])
        if d - q1[j] > 2:
            s.append(d - q1[j] - 1)
        q1[j] = d
for d in q1:
    if d < n - 2:
        s.append(n - d - 1)
a = len(q1)
s.sort()
print(n, end=' ')
for d in range(2, n):
    print(a * (n - d + 1) - sum(s) + (d - 1) * len(s), end=' ')
    if len(s) != 0:
        while s[0] - d <= 0:
            s.pop(0)
            if len(s) == 0:
                break
else:
    if n != 1:
        print(a)

Собственно, решение само по себе верное, но реализация, видимо, подкачала, на 77 тесте из 100 выдаёт MLE.
Объясните, пожалуйста, где тут можно сократить объём используемой памяти или как переписать код так, чтобы память не нагружалась так сильно.

@Red white socks · 07.07.2022, 19:18

Сообщение от STALKER77777

Примеры
№ INPUT.TXT OUTPUT.TXT
1 5
1 3 2 1 2 5 8 8 6 3
2 3
10 10 10 3 2 1
##################

В нормальном виде пример приведите.

@STALKER77777 · 08.07.2022, 01:04 **[ТС]**

№1
INPUT.TXT
5
1 3 2 1 2

OUTPUT.TXT
5 8 8 6 3
___________

№2
INPUT.TXT
3
10 10 10

OUTPUT.TXT
3 2 1

@Red white socks · 08.07.2022, 10:21

Первым делом нужно отметить, что Python, являясь языком интерпретируемым, а не компилируемым, не способен обеспечить должную скорость работы в большинстве задач. Эталонных решений на Python нет и не предполагается, поэтому используйте этот язык на свой страх и риск. Возможно, решение придётся переписывать на другом языке. Эмпирические наблюдения показывают, что Python использует до 10 раз больше памяти и около 10–100 раз больше времени по сравнению с аналогичным решением на C/C++.

https://acm.bsu.by/wiki/Решения на Python

В реализации, чтобы уменьшить память, можно избавиться от сортировки, в алгоритме она опциональна, можно без нее.
Странно, что у вас выдало MLE, а не RTE, хотя явно вы не укладываетесь по времени из-за вот этого:

Python
1
s.pop(0)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from time import time
x = [i for i in range(2*10**5)]
start_time = time()
while x:
    x.pop(0)
print('Удаление из начала списка: {0:.3f} c'.format(time()-start_time))
 
x = [i for i in range(2*10**5)]
start_time = time()
while x:
    x.pop()
print('Удаление из конца списка: {0:.3f} c'.format(time()-start_time))
 
#Удаление из начала списка: 7.043 c
#Удаление из конца списка: 0.017 c

Расскажите, пожалуйста, о своем алгоритме. Что за способ выбрали для подсчета и его реализацию. Что в списках s, q, q1?

@STALKER77777 · 09.07.2022, 18:41 **[ТС]**

В s я храню длины отрезков между 2 ближайшими вхождениями одного числа c_i в последовательность a, а также длины отрезков от начала и конца последовательности до первого и последнего вхождения числа соответственно. Я решил не добавлять отрезки, которые в последующем не будут использоваться, поэтому, если длина отрезка меньше 3, то я его не включаю в s.
В q хранятся всевозможные числа c_i, входящие в последовательность a, в q1 - индекс последнего вхождения c_i в a.
Спасибо за подсказку, насчёт исключения чисел с конца, а не с начала. Логика решения была такой, что мы для каждого различного c_i записываем в s все значения отрезков между его ближайшими 2 вхождениями в последовательность a. Затем по данным из s высчитываем для каждого c_i, сколько существует различных отрезков по d подряд идущих дней, которые не включают в себя c_i. Сумма результатов будет ответом для данного d, но так как количество отрезков из d подряд идущих дней между 2 вхождениями для любого c_i не может быть отрицательной, а 0 мы не учитываем, т.к. он суммы не меняет, приходится удалять все ненужные отрезки из s. Также я заметил, что для d = 1 ответ будет равен n, а для d = n ответ будет длиной q, то есть количеством различных c_i в последовательности a.

Добавлено через 7 минут
Также я забыл упомянуть, что была и 2 попытка, там я реализовал двоичный поиск для нахождения в отсортированном s отрезка, с которого стоит начать подсчёт суммы для следующего d, но там уже была кривая реализация скорее-всего, поэтому дальше 8 теста такой вариант не прошёл из-за неверных ответов. Вот код, но он крайне кривой, потому что такого вида двоичный поиск я реализовывал впервые.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
n = int(input())
a = list(map(int, input().split()))
s = []
q = []
q1 = []
for d in range(n):
    if a[d] not in q:
        q.append(a[d])
        q1.append(d)
        if d > 1:
            s.append(d)
    else:
        j = q.index(a[d])
        if d - q1[j] > 2:
            s.append(d - q1[j] - 1)
        q1[j] = d
del a
del q
for d in q1:
    if d < n - 2:
        s.append(n - d - 1)
a = len(q1)
del q1
if len(s) != 0:
    q = max(s)
    q1 = min(s)
else:
    q = 0
    q1 = 0
s = tuple(sorted(s))
print(n, end=' ')
i = 0
for d in range(2, n):
    print(a * (n - d + 1) - sum(s[i:]) + (d - 1) * (len(s) - i), end=' ')
    if q > d >= q1:
        j = len(s) - 1
        if s[j] > d >= s[j - 1]:
            i = j
            continue
        if s[i] > d >= s[i - 1]:
            continue
        while i < j:
            if s[(i + j) // 2] > d >= s[(i + j) // 2 - 1]:
                i = (i + j) // 2
                break
            if s[(i + j) // 2 + 1] > d >= s[(i + j) // 2]:
                i = (i + j) // 2 + 1
                break
            if s[(i + j) // 2] > d:
                j = (i + j) // 2 + 1
            else:
                i = (i + j) // 2 + 1
    elif d >= q:
        i = len(s)
else:
    if n != 1:
        print(a)

Новые блоги и статьи Все статьи Все блоги /
wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .
К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .

@STALKER77777 0 / 0 / 0 Регистрация: 07.07.2022 Сообщений: 3
	08.07.2022, 01:04 [ТС]
	№1 INPUT.TXT 5 1 3 2 1 2 OUTPUT.TXT 5 8 8 6 3 ___________ №2 INPUT.TXT 3 10 10 10 OUTPUT.TXT 3 2 1 0