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

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

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.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