Не могу найти плавающий баг в логике решения задачи на алгоритмы С++
Задача в тестирующей системе валится на 20 тесте. Доступа к тестам нет. Результат моделирование на мелких тестах совпадает с тем что выдаёт вывод.
Я проходи контест от Яндекса. Там дается задание. Я беру выбираю компилятор и отправляю код. Там мне показывают, какой тест я прошел, а какой не прошел, но показывают только номер теста, в котором СТРОГО нет входных данных, то есть я знаю что ТОЛЬКО ЧТО мое решение не прошло на 20 тесте, и все. Там могут быть любые числа. И вряд ли баг в тестирующей системе, да такое может быть, но скорее всего проблема в моей логике. И я не могу найти проблему в логике.
Я пытаюсь решить это с помощью классов. Я везде использую long long. Я много раз проверял логику. Я тестировал этот код на разных небольших входных данных(3 2, 3 3, 3 4, 4 4). Все эти примеры соответствуют тому, что я рассчитал сам.
ТЕКСТ ЗАДАЧИ
В системе умного дома под управлением голосового помощника Лариса n устройств, соединяющихся между собой по сети LoRaWAN. Устройство номер 1 подключено к интернету и на него было скачано обновление, которое необходимо передать на все устройства. Сеть LoRaWAN очень медленная, поэтому для распространения протокола был придуман peer-to-peer (P2P) протокол. Файл обновления разбивается на k одинаковых по размеру частей, занумерованных от 1 до k.
Передача части обновления происходит во время таймслотов. Каждый таймслот занимает одну минуту. За один таймслот каждое устройство может получить и передать ровно одну часть обновления. То есть устройство во время таймслота может получать новую часть обновления и передавать уже имеющуюуся у него к началу таймслота часть обновления, или совершать только одно из этих действий, или вообще не осуществлять прием или передачу. После приема части обновления устройство может передавать эту часть обновления другим устройствам в следующих таймслотах.
Перед каждым таймслотом для каждой части обновления определяется, на скольких устройствах сети скачана эта часть. Каждое устройство выбирает отсутствующую на нем часть обновления, которая встречается в сети реже всего. Если таких частей несколько, то выбирается отсутствующая на устройстве часть обновления с наименьшим номером.
После этого устройство делает запрос выбранной части обновления у одного из устройств, на котором такая часть обновления уже скачана. Если таких устройств несколько — выбирается устройство, на котором скачано наименьшее количество частей обновления. Если и таких устройств оказалось несколько — выбирается устройство с минимальным номером.
После того, как все запросы отправлены, каждое устройство выбирает, чей запрос удовлетворить. Устройство A удовлетворяет тот запрос, который поступил от наиболее ценного для A устройства. Ценность устройства B для устройства A определяется как количество частей обновления, ранее полученных устройством A от устройства B. Если на устройство A пришло несколько запросов от одинаково ценных устройств, то удовлетворяется запрос того устройства, на котором меньше всего скачанных частей обновления. Если и таких запросов несколько, то среди них выбирается устройство с наименьшим номером.
Далее начинается новый таймслот. Устройства, чьи запросы удовлетворены, скачивают запрошенную часть обновления, а остальные не скачивают ничего.
Для каждого устройства определите, сколько таймслотов понадобится для скачивания всех частей обновления.
Формат ввода:
Вводится два числа n и k (2 ≤ n ≤ 100, 1 ≤ k ≤ 200).
Формат вывода:
Выведите n-1 число — количество таймслотов, необходимых для скачивания обновления на устройства с номерами от 2 до n.
Пример:
Ввод: 3 2
Вывод: 3 3Ограничение времени: 15 секунд
Ограничение памяти: 256Mb
Ввод: стандартный ввод или input.txt
Вывод: стандартный вывод или output.txt
Мое решение
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
class Device {
public:
Device(vector<Device*>& vd, long long k, vector<long long>& cu, long long n) {
devices = &vd;
commonUpdates = &cu;
updates = vector<bool>(k, false);
valueble = vector<long long>(n, 0);
requests = vector<Device*>();
countPartOfUpdates = 0;
nowNeedpartOfUpdate = -1;
iters = 0;
indexInDevices = devices->size();
devices->push_back(this);
}
void choose_part_of_update() {
nowNeedpartOfUpdate = -1;
long long minCountUpdates = LLONG_MAX;
for (size_t i = 0; i < updates.size(); ++i) {
if (updates[i] == false && (*commonUpdates)[i] < minCountUpdates) {
minCountUpdates = (*commonUpdates)[i];
nowNeedpartOfUpdate = i;
}
}
if (nowNeedpartOfUpdate != -1) {
++iters;
}
}
void choose_device_who_have_part_of_update() {
if (nowNeedpartOfUpdate == -1) {
return;
}
long long minDownloadUpdates = LLONG_MAX;
long long iDevice = 0;
for (size_t i = 0; i < devices->size(); ++i) {
Device* dev = (*devices)[i];
if (dev->updates[nowNeedpartOfUpdate] == true) {
if (dev->countPartOfUpdates < minDownloadUpdates) {
iDevice = i;
minDownloadUpdates = dev->countPartOfUpdates;
}
}
}
(*devices)[iDevice]->requests.push_back(this);
}
void choose_request() {
long long minCountPartOfUpdates = LLONG_MAX;
long long iOkDevice = -1;
long long maxValueble = -1;
for (size_t i = 0; i < this->requests.size(); ++i) {
Device* dev = requests[i];
if (valueble[dev->indexInDevices] > maxValueble) {
iOkDevice = dev->indexInDevices;
minCountPartOfUpdates = dev->countPartOfUpdates;
maxValueble = valueble[dev->indexInDevices];
}
else if (valueble[dev->indexInDevices] == maxValueble) {
if (minCountPartOfUpdates > dev->countPartOfUpdates) {
iOkDevice = dev->indexInDevices;
minCountPartOfUpdates = dev->countPartOfUpdates;
}
}
}
this->requests.clear();
if (iOkDevice != -1) {
Device* dev = (*devices)[iOkDevice];
++(dev->countPartOfUpdates);
dev->updates[dev->nowNeedpartOfUpdate] = true;
++((*commonUpdates)[dev->nowNeedpartOfUpdate]);
++(dev->valueble[this->indexInDevices]);
}
}
vector<Device*>* devices;
vector<long long>* commonUpdates;
vector<bool> updates;
vector<long long> valueble;
vector<Device*> requests;
long long countPartOfUpdates;
long long nowNeedpartOfUpdate;
long long iters;
long long indexInDevices;
};
vector<long long> decide(long long n, long long k) {
vector<Device*> devices;
vector<long long> commonUpds(k, 1);
for (long long i = 0; i < n; ++i) {
Device* dev = new Device(devices, k, commonUpds, n);
}
devices[0]->countPartOfUpdates = k;
devices[0]->updates = vector<bool>(k, true);
while (true) {
long long thisIsEnd = 0;
for (Device* dev : devices) {
if (dev->countPartOfUpdates == k) {
thisIsEnd += 1;
continue;
}
dev->choose_part_of_update();
}
if (thisIsEnd == n) {
break;
}
for (Device* dev : devices) {
if (dev->countPartOfUpdates == k)
continue;
dev->choose_device_who_have_part_of_update();
}
for (Device* dev : devices) {
if (dev->requests.size() == 0)
continue;
dev->choose_request();
}
}
vector<long long> ans;
for (Device* dev : devices) {
ans.push_back(dev->iters);
}
return ans;
}
int main() {
ifstream iFile("input.txt");
long long n, k;
iFile >> n >> k;
vector<long long> v = decide(n, k);
ofstream outputFile("output.txt");
for (size_t i = 1; i < v.size(); ++i) {
outputFile << v[i] << " ";
}
return 0;
}
Ответы (1 шт):
Проблема заключалась в функции choose_request() менялась "ценность" объекта, у которого был запрошен запрос, для объекта который этот запрос делал, из-за чего могла образоваться ситуация, когда объект 3 делал себя более ценным для объекта 5, который из-за этого теперь будет выбирать объект 3, а не объект скажем 2 (если бы 2 и 3 имели бы одинаковую ценность).
Вынес в отдельную функцию удовлетворения запроса объекта, и вынес вызов у всех объектов данную функцию ПОСЛЕ подсчета выбора чей запрос удовлетворить.
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <limits>
using namespace std;
class Device {
public:
Device(long long k, long long n) {
updates = vector<bool>(k, false);
valueble = vector<long long>(n, 0);
requests = vector<Device*>();
countPartOfUpdates = 0;
nowNeedpartOfUpdate = -1;
iters = 0;
indexInDevices = devices.size();
myRequestOK = false;
idDeviceRequest = -1;
devices.push_back(this);
}
void choose_part_of_update() {
nowNeedpartOfUpdate = -1;
long long minCountUpdates = std::numeric_limits<long long>::max();
for (size_t i = 0; i < updates.size(); ++i) {
if (updates[i] == false && commonUpdates[i] < minCountUpdates) {
minCountUpdates = commonUpdates[i];
nowNeedpartOfUpdate = i;
}
}
if (nowNeedpartOfUpdate != -1) {
++iters;
}
}
void choose_device_who_have_part_of_update() {
if (nowNeedpartOfUpdate == -1) {
return;
}
long long minDownloadUpdates = std::numeric_limits<long long>::max();
Device* deviceRequest = nullptr;
for (size_t i = 0; i < devices.size(); ++i) {
Device* dev = devices[i];
if (dev->updates[nowNeedpartOfUpdate] == true) {
if (dev->countPartOfUpdates < minDownloadUpdates) {
deviceRequest = dev;
minDownloadUpdates = dev->countPartOfUpdates;
}
}
}
if (deviceRequest != nullptr) {
deviceRequest->requests.push_back(this);
}
}
void choose_request() {
long long minCountPartOfUpdates = std::numeric_limits<long long>::max();
long long iOkDevice = -1;
long long maxValueble = -1;
for (size_t i = 0; i < this->requests.size(); ++i) {
Device* dev = requests[i];
if (valueble[dev->indexInDevices] > maxValueble) {
iOkDevice = dev->indexInDevices;
minCountPartOfUpdates = dev->countPartOfUpdates;
maxValueble = valueble[dev->indexInDevices];
}
else if (valueble[dev->indexInDevices] == maxValueble) {
if (minCountPartOfUpdates > dev->countPartOfUpdates) {
iOkDevice = dev->indexInDevices;
minCountPartOfUpdates = dev->countPartOfUpdates;
}
}
}
this->requests.clear();
if (iOkDevice != -1) {
Device* dev = devices[iOkDevice];
dev->myRequestOK = true;
dev->idDeviceRequest = this->indexInDevices;
}
}
void request_OK() {
if (!myRequestOK)
return;
++countPartOfUpdates;
updates[nowNeedpartOfUpdate] = true;
++commonUpdates[nowNeedpartOfUpdate];
++valueble[idDeviceRequest];
myRequestOK = false;
}
static vector<Device*> devices;
static vector<long long> commonUpdates;
vector<bool> updates;
vector<long long> valueble;
vector<Device*> requests;
bool myRequestOK;
int idDeviceRequest;
long long countPartOfUpdates;
long long nowNeedpartOfUpdate;
long long iters;
long long indexInDevices;
};
vector<Device*> Device::devices;
vector<long long> Device::commonUpdates;
vector<long long> decide(long long n, long long k) {
Device::devices = vector<Device*>();
Device::commonUpdates = vector<long long>(k, 1);
for (long long i = 0; i < n; ++i) {
Device* dev = new Device(k, n);
}
Device::devices[0]->countPartOfUpdates = k;
Device::devices[0]->updates = vector<bool>(k, true);
while (true) {
long long thisIsEnd = 0;
for (Device* dev : Device::devices) {
if (dev->countPartOfUpdates == k) {
thisIsEnd += 1;
continue;
}
dev->choose_part_of_update();
}
if (thisIsEnd == n) {
break;
}
for (Device* dev : Device::devices) {
if (dev->countPartOfUpdates == k)
continue;
dev->choose_device_who_have_part_of_update();
}
for (Device* dev : Device::devices) {
if (dev->requests.size() == 0)
continue;
dev->choose_request();
}
for (Device* dev : Device::devices) {
if (dev->myRequestOK == false) {
continue;
}
dev->request_OK();
}
}
vector<long long> ans;
for (Device* dev : Device::devices) {
ans.push_back(dev->iters);
}
for (Device* dev : Device::devices) {
delete dev;
}
return ans;
}
int main() {
ifstream iFile("input.txt");
long long n, k;
iFile >> n >> k;
vector<long long> v = decide(n, k);
ofstream outputFile("output.txt");
for (size_t i = 1; i < v.size(); ++i) {
outputFile << v[i] << " ";
}
return 0;
}