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

@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)

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

@Red white socks · 16.04.2023, 16:03

Grootys, есть оптимизация для случая большого количества дата-центров.
В кучу надо класть только ДЦ, с серверами которых проводились действия. Понятно, что максимум будет среди них. А для минимума, пока есть сервера с которыми не было никаких действий, то можно выдавать ответ с помощью словаря, поскольку с какой-то версии (3.6 или 3.7 кажется) гарантирован порядок - надо только удалять ключи. А в случае, если n > q (а в тесте, который заваливается, подозреваю так и есть), то куча на минимум вообще не нужна.
Например, для случая 50К дата-центров, это кратно повысит скорость, а для 10К должен работать и старый код.

@eaa · 16.04.2023, 17:51

Red white socks, похоже придется писать какое то сбалансированное дерево, чтобы за log удалять.
Grootys, а есть ссылка на проверяющую систему?

@Grootys · 16.04.2023, 17:57

eaa, https://coderun.yandex.ru/ заходи в Сезоны выбирай Бэкенд, регайся, потом найдешь в треке бэкенда 325 задача среднего уровня "Коля и датацентры"

Добавлено через 3 минуты
eaa, я кстати на с++ переписал с использованием queue и 2мя своими компараторами, падает с TL на том же 54м тесте, если нужно могу скинуть

@eaa · 16.04.2023, 17:58

Grootys, мне не нужно.

@Red white socks · 16.04.2023, 21:27

eaa, по видимому да. Моя "оптимизация" не работает, хотя на случайных значениях укладывается в секунду.
Придется писать красно-черное дерево.

@eaa · 16.04.2023, 21:35

В плюсах map и set на красно-черных же реализовано вроде

@Falazure · 17.04.2023, 00:23

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

Интересно, одинаковые ли у всех задачи

@Grootys · 17.04.2023, 00:31

Falazure, так скинь решение то правильное)) я уже сутки решаю эту хню

@rRczZZ · 17.04.2023, 02:18

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

заходи в Сезоны выбирай Бэкенд, регайся, потом найдешь в треке бэкенда 325 задача среднего уровня "Коля и датацентры"

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

Решил таким способом, но 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
39
40
41
42
43
44
import sys
import heapq
 
# input = open('input.txt').readline
input = sys.stdin.readline
n, m, q = map(int, input().split())
db = [0] * n  # битовая маска включенных машин
da = [m] * n  # число включённыых машин
dr = [0] * n  # число перезапусков
dw = [0] * n  # метрика r*a
 
min_heap = [(0, i) for i in range(n)]
max_heap = [(0, i) for i in range(n)]
 
for _ in range(q):
    cmd, *a, = input().split()
    *a, = map(int, a)
    if cmd == 'RESET':
        i = a[0] - 1
        db[i] = 0
        da[i] = m
        dr[i] += 1
        dw[i] = dr[i] * da[i]
        heapq.heappush(min_heap, (dw[i], i))
        heapq.heappush(max_heap, (-dw[i], i))
    elif cmd == 'DISABLE':
        i, j = a
        i -= 1
        j -= 1
        t = 1 << j
        if db[i] & t: continue
        db[i] |= t
        da[i] -= 1
        dw[i] -= dr[i]
        heapq.heappush(min_heap, (dw[i], i))
        heapq.heappush(max_heap, (-dw[i], i))
    elif cmd == 'GETMAX':
        while -max_heap[0][0] != dw[max_heap[0][1]]:
            heapq.heappop(max_heap)
        print(max_heap[0][1] + 1)
    elif cmd == 'GETMIN':
        while min_heap[0][0] != dw[min_heap[0][1]]:
            heapq.heappop(min_heap)
        print(min_heap[0][1] + 1)

Сообщение от Red white socks

В кучу надо класть только ДЦ, с серверами которых проводились действия. Понятно, что максимум будет среди них. А для минимума, пока есть сервера с которыми не было никаких действий, то можно выдавать ответ с помощью словаря, поскольку с какой-то версии (3.6 или 3.7 кажется) гарантирован порядок - надо только удалять ключи.

Сообщение от Red white socks

Одна проблема - в питоне нет встроенной реализации.

т.е. брать первый элемент из dict.keys()? Тогда универсальный алгоритм, наверное, - кластеризовать датацентры по метрикам R*A в кучи с минимумами по номерам датацентров, а кластеры (между собой) сортировать (самобалансирующимся) BST с поддержкой минимума и максимума (по метрике R*A). При этом каждый датацентр должен знать свой индекс в кластере (куче) чтобы прыгнуть в другую по запросу. А шутка в том, что дерево можно заменить двумя dict, но реализация кучи нужна кастомная (ради получения индексов после вставки), получается всё наоборот от того как Вы писали.

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

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

@Red white socks · 17.04.2023, 13:13

rRczZZ, это была фантазия, пораженная больным воображением, поэтому даже обсуждать не хочется. И ведь понимал, что несу дичь, но было не остановить. У себя то я даже не пытался это реализовать, а сделал эту штуку обычным проходом по массиву ) Только проблема в тесте, как, спасибо вам, выяснилось, была не в большом n, а скорее в большом m, потому и не сработала.
Отдельное спасибо за возвращение веры в битовую арифметику. Я как-то замерял скорости взятия последнего бита со взятием остатка на 2 и вторая у меня выиграла. Догадываюсь, что сравнивал двенадцать с дюжиной, но осадок остался...

@Mencey · 22.04.2023, 14:42

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

@RockSun · 22.04.2023, 15:34 **[ТС]**

Grootys написал лучшее решение из предложенных) Я забыл про эту тему, но пришел в итоге к выводу что эту задачу лучше было писать на C++, как отметил eaa.

@Mencey · 22.04.2023, 16:17

Я на плюсах такое написал, но почему-то валится на 56 тесте. Вместо 2 выводит 1.

C++
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <fstream>
#include <set>
#include <map>
using namespace std;
 
typedef pair<int, int> dc_key;
 
int main() {
    int n, m, q;
 
    ifstream f("input.txt"); istream &in = f;
    // istream &in = cin;
    
    in >> n >> m >> q;
 
    auto cmp1 = [](dc_key a, dc_key b) {
        if (a.second < b.second) return true;
        if (a.second == b.second && a.first < b.first) return true;
        return false;
    };
    set<dc_key, decltype(cmp1)> ra_min;
    auto cmp2 = [](dc_key a, dc_key b) {
        if (a.second > b.second) return true;
        if (a.second == b.second && a.first < b.first) return true;
        return false;
    };
    set<dc_key, decltype(cmp2)> ra_max;
    for (int i = 1; i <= n; i++) {
        ra_min.insert(make_pair(i, 0));
        ra_max.insert(make_pair(i, 0));
    }
 
    map<int, int> ra_val;
 
    map<int, int> R;
    map<int, map<int, bool>> is_disabled;
 
    while (q--) {
        string s;
        in >> s;
        int i, j;
        if (s == "GETMAX") {
            cout << (*ra_max.begin()).first << endl;
            continue;
        } else if (s == "GETMIN") {
            cout << (*ra_min.begin()).first << endl;
            continue;
        } else if (s == "DISABLE") {
            in >> i >> j;
            if (is_disabled[i][j]) {
                continue;
            }
            is_disabled[i][j] = true;
        } else if (s == "RESET") {
            in >> i;
            is_disabled[i] = map<int, bool>();
            R[i]++;
        }
        int a = m - is_disabled[i].size();
        int ra_cur = R[i] * a;
 
        ra_max.erase(make_pair(i, ra_val[i]));
        ra_min.erase(make_pair(i, ra_val[i]));
 
        ra_max.insert(make_pair(i, ra_cur));
        ra_min.insert(make_pair(i, ra_cur));
 
        ra_val[i] = ra_cur;
    }
 
    return 0;
}

@rRczZZ · 22.04.2023, 20:07

Mencey, std::map<Key,T,Compare,Allocator>::operator[]

Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist.

в 51 строке иногда добавляется +1 к размеру множества, вставляя false. А в 60'ой смотрите на этот размер, предполагая, что во множестве все элементы true (хотя это не так)

@rRczZZ · 23.04.2023, 13:15

Mencey, до меня дошел финт со скобками.. , тогда здесь переполнение, нужно заменить тип int на long long везде где хранится произведение (в dc_key, ra_val, is_disabled, ra_cur, a).

Новые блоги и статьи Все статьи Все блоги /
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	16.04.2023, 16:03
	Grootys, есть оптимизация для случая большого количества дата-центров. В кучу надо класть только ДЦ, с серверами которых проводились действия. Понятно, что максимум будет среди них. А для минимума, пока есть сервера с которыми не было никаких действий, то можно выдавать ответ с помощью словаря, поскольку с какой-то версии (3.6 или 3.7 кажется) гарантирован порядок - надо только удалять ключи. А в случае, если n > q (а в тесте, который заваливается, подозреваю так и есть), то куча на минимум вообще не нужна. Например, для случая 50К дата-центров, это кратно повысит скорость, а для 10К должен работать и старый код. 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	16.04.2023, 17:51
	Red white socks, похоже придется писать какое то сбалансированное дерево, чтобы за log удалять. Grootys, а есть ссылка на проверяющую систему? 2

@Grootys 3 / 2 / 1 Регистрация: 17.09.2021 Сообщений: 5
	16.04.2023, 17:57
	eaa, https://coderun.yandex.ru/ заходи в Сезоны выбирай Бэкенд, регайся, потом найдешь в треке бэкенда 325 задача среднего уровня "Коля и датацентры" Добавлено через 3 минуты eaa, я кстати на с++ переписал с использованием queue и 2мя своими компараторами, падает с TL на том же 54м тесте, если нужно могу скинуть 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	16.04.2023, 17:58
	Grootys, мне не нужно. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	16.04.2023, 21:27
	eaa, по видимому да. Моя "оптимизация" не работает, хотя на случайных значениях укладывается в секунду. Придется писать красно-черное дерево. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	16.04.2023, 21:35
	В плюсах map и set на красно-черных же реализовано вроде 0

@Falazure 1 / 1 / 2 Регистрация: 24.07.2013 Сообщений: 8
	17.04.2023, 00:23
	найс отсев, конечно, придумали. проще на аа сходить и там связный список развернуть, чем этот треш решать... Решил таки эту задачу, но остальные две свои задачи уже сил и желания не было решать. Хотя там с виду тоже трешачок и всякие ограничения будут -_- Интересно, одинаковые ли у всех задачи 0

@Grootys 3 / 2 / 1 Регистрация: 17.09.2021 Сообщений: 5
	17.04.2023, 00:31
	Falazure, так скинь решение то правильное)) я уже сутки решаю эту хню 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	17.04.2023, 13:13
	rRczZZ, это была фантазия, пораженная больным воображением, поэтому даже обсуждать не хочется. И ведь понимал, что несу дичь, но было не остановить. У себя то я даже не пытался это реализовать, а сделал эту штуку обычным проходом по массиву ) Только проблема в тесте, как, спасибо вам, выяснилось, была не в большом n, а скорее в большом m, потому и не сработала. Отдельное спасибо за возвращение веры в битовую арифметику. Я как-то замерял скорости взятия последнего бита со взятием остатка на 2 и вторая у меня выиграла. Догадываюсь, что сравнивал двенадцать с дюжиной, но осадок остался... 0

@Mencey 155 / 102 / 12 Регистрация: 22.07.2010 Сообщений: 445
	22.04.2023, 14:42
	Кто-нибудь в курсе того можно ли как-то отправлять решение когда закончилось время? 0

@RockSun 44 / 31 / 13 Регистрация: 19.12.2022 Сообщений: 107
	22.04.2023, 15:34 [ТС]
	Grootys написал лучшее решение из предложенных) Я забыл про эту тему, но пришел в итоге к выводу что эту задачу лучше было писать на C++, как отметил eaa. 0

@rRczZZ 814 / 422 / 169 Регистрация: 08.02.2013 Сообщений: 711
	23.04.2023, 13:15
	Mencey, до меня дошел финт со скобками.. , тогда здесь переполнение, нужно заменить тип `int` на `long long` везде где хранится произведение (в `dc_key`, `ra_val`, `is_disabled`, `ra_cur`, `a`). 0