Коля и дата-центры

@RockSun · Регистрация: 19.12.2022

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

Рано или поздно все крупные IT-компании создают свои дата-центры. Коля только устроился в такую компанию и еще не успел во всем разобраться. В его компании есть N дата-цетров,в каждом дата-центре установлено M серверов. Из-за большой нагрузки серверы могут выключаться. Из-за спешки при постройке дата-центров включить только один сервер не получается, поэтому приходится перезагружать весь дата-центр. У каждого дата-центра есть два неотрицательных целочисленных параметра: R(i) — число перезапусков i-го дата-центра и A(i) — число рабочих (не выключенных) серверов на текущий момент в i -м дата-центре. Коля получил задачу по сбору некоторых метрик, которые в будущем позволят улучшить работу дата-центов. Для этого Коля собрал данные о Q событиях, произошедших за текущий день. Коля справился с этой задачей, но просит помочь и проверить свои результаты.
Формат ввода:
В первой строке входных данных записано 3 положительных целых числа n , m , q ( 1 ≤ q ≤ 1 0 5 , 1 ≤ n ⋅ m ≤ 1 0 6 ) — число дата-центров, число серверов в каждом из дата-центров и число событий соответственно.
В последующих q строках записаны события, которые могут иметь один из следующих видов:
RESET i — был перезагружен i -й дата-центр ( 1 ≤ i ≤ n )
DISABLE i j — в i -м дата-центре был выключен j -й сервер ( 1 ≤ i ≤ n , 1 ≤ j ≤ m )
GETMAX — получить номер дата-центра с наибольшим произведением R(i) ∗ A(i)
GETMIN — получить номер дата-центра с наименьшим произведением R(i) ∗ A(i)
Формат вывода:
На каждый запрос вида GETMIN или GETMAX выведите единственное положительное целое число — номер дата-центра, подходящий под условие. В случае неоднозначности ответа выведите номер наименьшего из дата-центров.
Пример ввода:
3 3 12
DISABLE 1 2
DISABLE 2 1
DISABLE 3 3
GETMAX
RESET 1
RESET 2
DISABLE 1 2
DISABLE 1 3
DISABLE 2 2
GETMAX
RESET 3
GETMIN
Пример вывода:
1
2
1
Еще пример ввода:
2 3 9
DISABLE 1 1
DISABLE 2 2
RESET 2
DISABLE 2 1
DISABLE 2 3
RESET 1
GETMAX
DISABLE 2 1
GETMIN
Пример вывода:
1
2
Примечания
Обратите внимание на 2 пример. DISABLE приходится для уже выключенного сервера. В данном случае сервер по-прежнему остаётся выключенным.
У меня уже есть код:

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
from collections import defaultdict
 
n, m, q = map(int, input().split())
 
R = [0] * n
A = [m] * n
 
prod = defaultdict(int)
for i in range(n):
    prod[i] = R[i] * A[i]
 
for i in range(q):
    query = input().split()
    if query[0] == 'RESET':
        idx = int(query[1]) - 1
        R[idx] += 1
        A[idx] = m
        prod[idx] = R[idx] * A[idx]
    elif query[0] == 'DISABLE':
        idx1, idx2 = map(int, query[1:])
        idx1 -= 1
        A[idx1] -= 1
        prod[idx1] = R[idx1] * A[idx1]
    elif query[0] == 'GETMAX':
        max_idx = max(prod, key=prod.get)
        print(max_idx + 1)
    elif query[0] == 'GETMIN':
        min_idx = min(prod, key=prod.get)
        print(min_idx + 1)

Он работает на примерах которые даны в условии, но на каких-то тестах не хочет. Почему - я без понятия. Есть идеи, как можно доработать?

@eaa · 21.03.2023, 15:16

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

но на каких-то тестах не хочет.

какой вердикт?

@Aviz__ · 21.03.2023, 15:51

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

на каких-то тестах не хочет.

логи ошибок выдает?

@Berbentsev · 21.03.2023, 21:00

Во втором примере никак не получается 1 2, вручную уже пересчитал, и программу накидал. Все равно получается 1 3.

Добавлено через 1 минуту
Если предпоследнюю строчку заменить на DISABLE 2 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class DataCenter:
    def __init__(self, name: int, servers_qt: int):
        self.name = name
        self.server_qt = servers_qt
        self.server_list = [True] * servers_qt
        self.reset_qt = 0
 
    def disable(self, server_number: int) -> None:
        self.server_list[server_number - 1] = False
 
    def reset(self) -> None:
        self.server_list = [True] * self.server_qt
        self.reset_qt += 1
 
    def reset_mul_server_on(self):
        return self.reset_qt * self.server_list.count(True)
    
    def __gt__(self, other):
        if self.reset_mul_server_on() == other.reset_mul_server_on():
            return self.name > other.name
        return self.reset_mul_server_on() > other.reset_mul_server_on()
 
    def __lt__(self, other):
        if self.reset_mul_server_on() == other.reset_mul_server_on():
            return self.name < other.name
        return self.reset_mul_server_on() < other.reset_mul_server_on()
 
    def __repr__(self):
        return str(self.name)
 
 
def main():
    n, m, q = map(int, input().split())
    data_centers = [DataCenter(i, m) for i in range(1, m + 1)]
 
    for command in (input() for _ in range(q)):
        match command.split():
            case 'DISABLE', i, j:
                i = int(i) - 1
                j = int(j)
                data_centers[i].disable(j)
            case 'RESET', i:
                i = int(i) - 1
                data_centers[i].reset()
            case 'GETMAX', *_:
                print(max(data_centers))
            case 'GETMIN', *_:
                print(min(data_centers))
        # print(*map(lambda x: x.reset_mul_server_on(), data_centers))
 
 
if __name__ == '__main__':
    main()

@eaa · 22.03.2023, 07:12

Berbentsev, как 1 3 получилось? дата-центров же всего 2.

Добавлено через 10 минут
34 строка, наверное в range(1, n + 1) ?

Python
1
data_centers = [DataCenter(i, m) for i in range(1, m + 1)]

Добавлено через 3 минуты
накидал "решение в лоб":

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n, m, q = map(int, input().split())
dc = [[1] * m for _ in range(n)]  # изначально все включены
dr = [0] * m  # накапливаем количество перезапусков
for _ in range(q):
    cmd, *a, = input().split()
    *a, = map(int, a)
    if cmd == 'RESET':
        i = a[0]
        dc[i - 1] = [1] * m
        dr[i - 1] += 1
    elif cmd == 'DISABLE':
        i, j = a
        dc[i - 1][j - 1] = 0
    elif cmd == 'GETMAX':
        ans = max(range(n), key=lambda x: dr[x] * dc[x].count(1)) + 1
        print(ans)
    elif cmd == 'GETMIN':
        ans = min(range(n), key=lambda x: dr[x] * dc[x].count(1)) + 1
        print(ans)

но это все про времени не пройдет.

@wumpochuck · 25.03.2023, 20:12

RockSun, У меня есть 2 решения, одно не проходит по времени (23), второе не проходит 21й тест. Не хочешь вместе подумать? Или мне подсказать, если ты уже справился)

@Falazure · 12.04.2023, 13:16

Ну как, получилось?
Таймлимит на 40+ каком-то тесте. Надо оптимизировать поиск максимума/минимума. Использование функций max/min при операции GETMAX или GETMIN это O(n).
В задаче вся суть - как-то поддерживать эти максимумы и минимумы, чтобы их за O(1) получить.
По идее тут надо использовать 2 кучи - одну maxHeap , другую minHeap. (очередь с приоритетами по сути). И иметь в ней операцию - изменение приоритета (она за логарифм работает). А взятие максимума минимума будет за константу.

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

@eaa · 12.04.2023, 15:20

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

@Юлия27 · 14.04.2023, 18:14

wumpochuck, привет
мой код тоже остановился на 21 тесте
ты в итоге нашел решения этому?

@Red white socks · 15.04.2023, 11:10

Юлия27, Falazure всем рассказал что надо делать.
Да, есть проблема, что во встроенной реализации кучи на питоне нет удаления по значению. Значит нужно реализовать кучу или двоичное дерево поиска самостоятельно. Что, как заметил eaa, только пойдет вам на пользу.

@GhoulIvan · 15.04.2023, 23:25

Получилось исправить ошибки?

@Grootys · 16.04.2023, 00:24

Red white socks, сделал через ДП, но wa на 6 тесте, думаю проблема getmax/getmin, из за этого условия: "В случае неоднозначности ответа выведите номер наименьшего из датацентров.". Криво реализовал, может есть какие идеи, как хранить пары (R*A, N), чтобы доставать их за logn?

@eaa · 16.04.2023, 11:59

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n, m, q = map(int, input().split())
dc = [[1] * m for _ in range(n)]  # изначально все включены
dr = [0] * m  # накапливаем количество перезапусков
dw = [m] * n
for _ in range(q):
    cmd, *a, = input().split()
    *a, = map(int, a)
    if cmd == 'RESET':
        i = a[0]
        dc[i - 1] = [1] * m
        dr[i - 1] += 1
        dw[i - 1] = m
    elif cmd == 'DISABLE':
        i, j = a
        if dc[i - 1][j - 1]:
            dw[i - 1] -= 1
        dc[i - 1][j - 1] = 0
    elif cmd == 'GETMAX':
        ans = max(range(n), key=lambda x: dr[x] * dw[x]) + 1
        print(ans)
    elif cmd == 'GETMIN':
        ans = min(range(n), key=lambda x: dr[x] * dw[x]) + 1
        print(ans)

теоретически должно быстрее работать, чем предыдущее мое решение.
осталось min и max в кучу кидать.

@Red white socks · 16.04.2023, 12:50

nick]Grootys[/nick], в треде уже 2 раза было сказано.
Ок. Давайте распишу подробно.
Данную задачу могут решить две структуры: куча с индексацией и двоичное дерево поиска.
Рассмотрим оба подробнее (рассматриваем для поиска минимума, для максимума дублируем структуру с противоположными элементами)
Куча - двоичное дерево, у которого оба потомка больше родителя. Основное свойство - на вершине кучи всегда будет минимальный элемент. В питоне есть реализация heapq. Это список у которого потомками элемента с индексом k являются элементы с индексами 2k+1, 2k+2.
В данной задаче мы кладем в кучу кортежи (R_i*A_i, i) для i-го дата-центра. Но при изменении произведения кучу надо перестраивать. Для этого надо найти элемент и увеличить ключ, после чего кучу перестроить. Увеличение ключа k-го элемента производится непубличным методом _siftdown. Остается найти элемент по ключу. И здесь это проблема, потому что в среднем это О(n). Поэтому нужна индексация - словарь, в котором ключу будет соответствовать индекс элемента в куче. Но это потребует ручной реализации кучи и ее методов с поддержкой индексации. Поэтому отложим пока в сторону.
Давайте рассмотрим двоичное дерево поиска. Оно отличается от кучи дополнительным свойством: левый потомок меньше правого. И здесь поиск элемента идет за логарифм (отсюда и название структуры). Изменение ключа можно проводить удалением/вставкой. И всё работает. Одна проблема - в питоне нет встроенной реализации. Но хорошая новость - в инете их миллион.

Upd. На этом можно было поставить точку, но пока писал - увидел пост eaa и мне сразу же пришла "гениальная" идея. Не будем мучаться с ручной реализацией, а берем стандартный heapq. При изменении ключа - старый не удаляем, просто добавляем новый. Тогда если минимум в куче не соответствует актуальному состоянию, то просто удаляем его и берем следующий. В код eaa потребуется внести тогда всего несколько строчек.

@eaa · 16.04.2023, 13:16

Red white socks, да тут удалять не нужно.

@Red white socks · 16.04.2023, 13:17

eaa, я не сомневался, что вы видели эту опцию сразу)

@Grootys · 16.04.2023, 14:00

eaa, Red white socks, Решил таким способом, но TL на 52 тесте

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
import heapq
n, m, q = map(int, input().split())
dc = [[1] * m for _ in range(n)]  # изначально все включены
dr = [0] * n  # накапливаем количество перезапусков
dw = [m] * n # количество рабочих серверов
 
min_heap = [(0, i) for i in range(n)]
max_heap = [(0, i) for i in range(n)]
heapq.heapify(min_heap)
heapq.heapify(max_heap)
 
for _ in range(q):
    cmd, *a, = input().split()
    *a, = map(int, a)
    if cmd == 'RESET':
        i = a[0] - 1
        dc[i] = [1] * m
        dr[i] += 1
        dw[i] = m
        heapq.heappush(min_heap, (dr[i] * dw[i], i))
        heapq.heappush(max_heap, (-dr[i] * dw[i], i))
    elif cmd == 'DISABLE':
        i, j = a
        i -= 1
        j -= 1
        if dc[i][j]:
            dw[i] -= 1
        dc[i][j] = 0
        heapq.heappush(min_heap, (dr[i] * dw[i], i))
        heapq.heappush(max_heap, (-dr[i] * dw[i], i))
    elif cmd == 'GETMAX':
        while -max_heap[0][0] != dr[max_heap[0][1]] * dw[max_heap[0][1]]: # Проверяем актуальность
            heapq.heappop(max_heap)
        print(max_heap[0][1] + 1)
    elif cmd == 'GETMIN':
        while min_heap[0][0] != dr[min_heap[0][1]] * dw[min_heap[0][1]]: # Проверяем актуальность
            heapq.heappop(min_heap)
        print(min_heap[0][1] + 1)

@Red white socks · 16.04.2023, 14:19

Grootys, тут надо тестировать - насколько критичен этот таймлимит. По коду могу сказать, что показатель R*A надо считать только один раз, запоминая. Количество умножений уменьшится кратно и на 10К запросах это может быть пара десятых секунды, что может и критично.

@eaa · 16.04.2023, 14:21

Grootys, PyPy нужно выбирать или на плюсы переписывать. Не уверен, что на python пройдет это.

@Grootys · 16.04.2023, 14:32

Red white socks, eaa, храню актуальные R*A в словаре и при поиске актуального в getmin/getmax достаю их из словаря за O(n), также запустил на PyPy, теперь падает с TL на 54 тесте))) Какая то безысходность

Новые блоги и статьи Все статьи Все блоги /
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере нетипового документа выдачи шин для спецтехники с табличной частью, разработанного в конфигурации КА2. Номеклатура. . .

Коля и дата-центры

Решение

Решение

@wumpochuck 0 / 0 / 0 Регистрация: 25.03.2023 Сообщений: 1
	25.03.2023, 20:12
	RockSun, У меня есть 2 решения, одно не проходит по времени (23), второе не проходит 21й тест. Не хочешь вместе подумать? Или мне подсказать, если ты уже справился) 0

@Falazure 1 / 1 / 2 Регистрация: 24.07.2013 Сообщений: 8
	12.04.2023, 13:16
	Ну как, получилось? Таймлимит на 40+ каком-то тесте. Надо оптимизировать поиск максимума/минимума. Использование функций max/min при операции GETMAX или GETMIN это O(n). В задаче вся суть - как-то поддерживать эти максимумы и минимумы, чтобы их за O(1) получить. По идее тут надо использовать 2 кучи - одну maxHeap , другую minHeap. (очередь с приоритетами по сути). И иметь в ней операцию - изменение приоритета (она за логарифм работает). А взятие максимума минимума будет за константу. Возможно есть ещё какие-то способы, без знания структур данных, но ничего не придумалось 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	12.04.2023, 15:20
	без знания алгоритмов и структур данных в олимпиадах делать нечего. 2

@Юлия27 0 / 0 / 0 Регистрация: 09.11.2020 Сообщений: 1
	14.04.2023, 18:14
	wumpochuck, привет мой код тоже остановился на 21 тесте ты в итоге нашел решения этому? 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	15.04.2023, 11:10
	Юлия27, Falazure всем рассказал что надо делать. Да, есть проблема, что во встроенной реализации кучи на питоне нет удаления по значению. Значит нужно реализовать кучу или двоичное дерево поиска самостоятельно. Что, как заметил eaa, только пойдет вам на пользу. 0

@GhoulIvan 0 / 0 / 0 Регистрация: 15.04.2023 Сообщений: 1
	15.04.2023, 23:25
	Получилось исправить ошибки? 0

@Grootys 3 / 2 / 1 Регистрация: 17.09.2021 Сообщений: 5
	16.04.2023, 00:24
	Red white socks, сделал через ДП, но wa на 6 тесте, думаю проблема getmax/getmin, из за этого условия: "В случае неоднозначности ответа выведите номер наименьшего из датацентров.". Криво реализовал, может есть какие идеи, как хранить пары (R*A, N), чтобы доставать их за logn? 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	16.04.2023, 12:50
	Сообщение было отмечено rim41 как решение Решение nick]Grootys[/nick], в треде уже 2 раза было сказано. Ок. Давайте распишу подробно. Данную задачу могут решить две структуры: куча с индексацией и двоичное дерево поиска. Рассмотрим оба подробнее (рассматриваем для поиска минимума, для максимума дублируем структуру с противоположными элементами) Куча - двоичное дерево, у которого оба потомка больше родителя. Основное свойство - на вершине кучи всегда будет минимальный элемент. В питоне есть реализация heapq. Это список у которого потомками элемента с индексом k являются элементы с индексами 2k+1, 2k+2. В данной задаче мы кладем в кучу кортежи (R_iA_i, i) для i-го дата-центра. Но при изменении произведения кучу надо перестраивать. Для этого надо найти элемент и увеличить ключ, после чего кучу перестроить. Увеличение ключа k-го элемента производится непубличным методом _siftdown. Остается найти элемент по ключу. И здесь это проблема, потому что в среднем это О(n). Поэтому нужна индексация - словарь, в котором ключу будет соответствовать индекс элемента в куче. Но это потребует ручной реализации кучи и ее методов с поддержкой индексации. Поэтому отложим пока в сторону. Давайте рассмотрим двоичное дерево поиска. Оно отличается от кучи дополнительным свойством: левый потомок меньше правого. И здесь поиск элемента идет за логарифм (отсюда и название структуры). Изменение ключа можно проводить удалением/вставкой. И всё работает. Одна проблема - в питоне нет встроенной реализации. Но хорошая новость - в инете их миллион. Upd. На этом можно было поставить точку, но пока писал - увидел пост eaa* и мне сразу же пришла "гениальная" идея. Не будем мучаться с ручной реализацией, а берем стандартный heapq. При изменении ключа - старый не удаляем, просто добавляем новый. Тогда если минимум в куче не соответствует актуальному состоянию, то просто удаляем его и берем следующий. В код eaa потребуется внести тогда всего несколько строчек. 2

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	16.04.2023, 13:16
	Red white socks, да тут удалять не нужно. 1

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	16.04.2023, 13:17
	eaa, я не сомневался, что вы видели эту опцию сразу) 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	16.04.2023, 14:19
	Grootys, тут надо тестировать - насколько критичен этот таймлимит. По коду могу сказать, что показатель R*A надо считать только один раз, запоминая. Количество умножений уменьшится кратно и на 10К запросах это может быть пара десятых секунды, что может и критично. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	16.04.2023, 14:21
	Grootys, PyPy нужно выбирать или на плюсы переписывать. Не уверен, что на python пройдет это. 1

@Grootys 3 / 2 / 1 Регистрация: 17.09.2021 Сообщений: 5
	16.04.2023, 14:32
	Red white socks, eaa, храню актуальные R*A в словаре и при поиске актуального в getmin/getmax достаю их из словаря за O(n), также запустил на PyPy, теперь падает с TL на 54 тесте))) Какая то безысходность 0