Что можно убрать чтобы оптимизировать затраты памяти?

Question

[impelix]

Задача кода сложить 2 числа которые заданы в формате: Сначала идет кол-во цепочек повторяющихся цифр, потом количество цифр идущих подряд, а потом сама цифра. Например: число 111 - это 1 3 1, а число 21 это 2 1 2 1 1. Задча сложить 2 числа которые задаются таким способом и вывести ответ в таком же формате.
Вроде как длинная арифметика работает правильно, но теперь он не заходит по памяти, насколько я понимаю есть какой-то другой, альтернативный вариант решения подобных задач. Насчет того, какое из чисел больше, то 1 всегда больше, поэтому запись ответа в него подойдет.

КОД

#include <iostream>
#include <vector>
#include <algorithm>

struct vv{
    int c, num;
};

// Функция для вывода большого числа
void printBigNumber(const std::vector<int>& number) {
    int cnt = 0;
    std::vector<vv> kk;
    for (int k = 0; k < number.size(); ++k) {
        if (k + 1 < number.size()) {
            if (number[k] == number[k + 1]) {
                cnt++;
            } else {
                kk.push_back({cnt + 1, number[k]});
                cnt = 0;
            }
        } else {
            kk.push_back({cnt + 1, number[k]});
        }
    }
    std::cout << kk.size() << std::endl;
    for (auto j: kk) {
        std::cout << j.c << ' ' << j.num << '\n';
//    }
//    for(auto k : number){
//        std::cout << k;
//    }
    }
}
void add(std::vector<int>& num1, std::vector<int>& num2) {
    int size1 = num1.size();
    int size2 = num2.size();
    int carry = 0;
    int maxSize = std::max(size1, size2);

    for (int i = 0; i < maxSize; i++) {
        int digit1 = (i < size1) ? num1[size1 - i - 1] : 0;
        int digit2 = (i < size2) ? num2[size2 - i - 1] : 0;

        int sum = digit1 + digit2 + carry;
        carry = sum / 10;
        num1[size1 - i - 1] = sum % 10;
    }

    if (carry > 0) {
        num1.insert(num1.begin(), carry);
    }
}

int main() {
    int n;
    std::vector<int> num1;
    std::vector<int> num2;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        int q;
        int num;
        std::cin >> q >> num;
        for (int j = 0; j < q; ++j) {
            num1.push_back(num);
        }
    }
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        int q;
        int num;
        std::cin >> q >> num;
        for (int j = 0; j < q; ++j) {
            num2.push_back(num);
        }
    }
    add(num1, num2);
    printBigNumber(num1);
}

Comments

[mayton2019]

Тут приложение борет проблему которая высосана из пальца. Само по себе сложение - длинных целых - это
очень простой алгоритм.

А вот эта форма хранения чисел - это какая-то чепуха и несуразца.

Вот твой пример.

Например: число 111 - это 1 3 1, а число 21 это 2 1 2 1 1.

Заметно что число в котором цифры различаются (а таковых чисел - подавляющее большинство)
занимает более чем в 2 раза больше места чем оригинальное число.

Представь сколько символов будет занимать следующее.

1234567890

10 цепочек. По одному символу в цепочке.

Я здесь не вижу никакой оптимизации кроме как игнорировать этот архиватор Бабушкина и
просто вычислять в длинной арифметике как и задумано. Если есть предположение
что оптимизация даст полезный эффект - то хочу узнать на чем основано это предположение?
Может быть на том что бы будем складывать цепочки цифр типа
111111111111111111111111 или 2222222222222 ? Но это никак не акцентировано
в задании.

Вообще какая цель этой лабораторной? Какая тема? Что изучаете?

[impelix]

mayton2019, ну вообще это просто контест, с различными задачами среди которых встретилась подобная. числа подаются в таком формате, у меня же они хранятся в векторе где каждый индекс это цифра. Для более простой арифметики. А 2 2 1 1 1 - это формат входных данных, всего навсего.

[mayton2019]

Было бы честным для задач контестеров и лит-кодов предупреждать о факте копирования задания сюда.

[impelix]

mayton2019, сам код то рабочий, просто интересно что здесь еще можно оптимизировать чтобы снизить затраты памяти.

[mayton2019]

Убери вектор kk отсюда.

void printBigNumber(const std::vector<int>& number) {
    int cnt = 0;
    std::vector<vv> kk;

[impelix]

mayton2019, а как считать количество цепочек повторяющихся?

[mayton2019]

impelix, опиши мне словами что делает эта функция. В 1-2 предложения.

[impelix]

mayton2019, она идет по числу и считает кол-во цепочек из одинаковых цифр подряд, после того как такая цепочка найдена, она заносит в этот вектор(kk) данные в формате кол-ва цифр в цепочки и самой цифры, После того как прошлись она выводит число таких цепочек и потом само число в заданном формате. Таком же как формат ввода.

[mayton2019]

Ну и прекрасно. Не нужен тебе этот массив. Ты его как буфер накапливаешь а потом печатаешь.
Печатай сразу.

Answer 1

[Wataru]

(Отредактировал ответ согласно комментариям). Как выяснилось, в задаче длины вот групп одинаковых цифр могут достигать 10^18. Поэтому попытка развернуть эту запись обречена на провал: все эти цифры потребуют миллионов террабайт. Естественно, ваша программа падает еще на этапе ввода ( а еще, вы там читаете int, в который такие большие числа не влезают, что будет дополнительной ошибкой).

Надо прочитать группы для каждого числа, развернуть эти списки, и складывать группу с группой. Будет у вас 2 указателя, как при слиянии двух массивов. Если первые группы в двух числах разной длины, то откусывайте от большей группы длину равную меньшей. Записывайте в ответ сумму групп, сдвигайте указатель в одном массиве, а во втором укоротите первую группу.

Главная часть решения - это научиться складывать две группы цифр равной длины (плюс перенос). Вроде 7777 + 4444 +1 = 12222 - 4 двойки и 1 единица (помните, порядок у нас развернутый же). Тут можно всегда выделять в отдельную группу первую цифру из-за переноса. Отдельный случай будет, похоже, если цифры дают в сумме 9 и есть перенос (10000..000). А иначе вы получите что-то вида abbbbbbc в оставшихся цифрах. Главное, что при сумме нельзя группы распаковывать.

В конце разверните группы и объедините подряд идущие группы для одинаковых цифр.

Comments

[impelix]

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

[Wataru]

impelix, или заведите отдельный вектор для ответа. Количество пар можно подсчитать перед выводом (считайте различия в массиве отдельным циклом). Цифры можно хранить в char - тоже экономия.

[impelix]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct vv{
    int c, num;
};

void printBigNumber(const std::vector<int>& number, int len) {
    int cnt = 0;
    std::vector<vv> kk;
    for (int k = 0; k < len; ++k) {
        if (k + 1 < len) {
            if (number[k] == number[k + 1]) {
                cnt++;
            } else {
                kk.push_back({cnt + 1, number[k]});
                cnt = 0;
            }
        } else {
            kk.push_back({cnt + 1, number[k]});
        }
    }
    std::cout << kk.size() << std::endl;
    for (auto j: kk) {
        std::cout << j.c << ' ' << j.num << '\n';
    }
//    for(auto k : number){
//        std::cout << k << ' ';
//    }
}

int main() {
    vector<int> a;
    vector<int> b;
    const int base = 1000 * 1000 * 1000;
    int n;
    cin >> n;
    while (n--) {
        int c;
        int num;
        cin >> c >> num;
        while (c--) {
            a.push_back(num);
        }
    }
    cin >> n;
    while (n--) {
        int c;
        int num;
        cin >> c >> num;
        while (c--) {
            b.push_back(num);
        }
    }
//    for(auto k : a){
//        std::cout << k;
//    }
//    cout << '+';
//    for(auto k : b){
//        std::cout << k;
//    }
//    cout << endl;
    int size_a = a.size();
    int size_b = b.size();
    int length;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    if (size_a > size_b) {
        length = size_a + 1;
        b.resize(length);
    }
    else
        length = size_b + 1;
        a.resize(length);

    for (int ix = 0; ix < length; ix++)
    {
        b[ix] += a[ix];
        b[ix + 1] += (b[ix] / 10);
        b[ix] %= 10;
    }

    if (b[length - 1] == 0){
        length--;
        b.erase(b.end() - 1);
    }
    reverse(b.begin(), b.end());
    printBigNumber(b, length);
}

Переписал для чисел разных размеров(второе может быть больше), такая же ошибка, на том же тесте. Есть предположение что тут нужен другой алгоритм, нашел какой то на емаксе, но не понял пока как его перенести к такому выводу, который мне нужен.

[Wataru]

Что за ошибку то выдает система? В коде виду 2 ошибки - отсутствие фигурных скобок у else, и все ту же запись за границу массива в цикле. Вы там после всех resize'ов можете получить массив b га один короче массива a. Вы там +1 к length делаете как бы для этого переноса, но цикл суммирования все равно гоните до length-1. Можно прибавлять перенос, если он не 0, тогда выхода за границу нк будет. Но испоавьте код, чтобы массивы были одинаковой длины.

[impelix]

Wataru, превышен лимит по памяти(memory limit exceed). Я переписал код, используя осноания для оптимизации(хранил числа в интах максимально возможные, до миллиарда) но снизилось не сильно, все так же лимит по памяти.

тест

При вводе:
3
2 2
3 3
9 9
1
1 1
Вывод должен быть
4
2 2
2 3
1 4
9 0

#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <sstream>

using namespace std;

struct vv{
    int c, num;
};

void printBigNumber(const std::vector<int>& number) {

    std::stringstream ss;
    for(int i = 0; i < number.size(); ++i)
    {
        if(i != 0)
            ss << "";
        ss << number[i];
    }
    std::string s = ss.str();
    vector<int>num;
    //cout << 's' << endl;
    for(auto k : s)
        num.push_back(int(k) - 48);
    s.clear();
    s.shrink_to_fit();
    int cnt = 0;
    std::vector<vv> kk;
    for (int k = 0; k < num.size(); ++k) {
        if (k + 1 < num.size()) {
            if (num[k] == num[k + 1]) {
                cnt++;
            } else {
                kk.push_back({cnt + 1, num[k]});
                cnt = 0;
            }
        } else {
            kk.push_back({cnt + 1, num[k]});
        }
    }
    std::cout << kk.size() << std::endl;
    for (auto j: kk) {
        std::cout << j.c << ' ' << j.num << '\n';
    }
}

int main() {
    vector<int> a;
    vector<int> b;
    const int base = 1000 * 1000 * 1000;
    int n;
    string stra;
    string strb;
    cin >> n;
    while (n--) {
        int c;
        char num;
        cin >> c >> num;
        while (c--) {
            stra.push_back(num);
        }
    }
    cin >> n;
    while (n--) {
        int c;
        char num;
        cin >> c >> num;
        while (c--) {
            strb.push_back(num);
        }
    }
    for (int i = (int) stra.length(); i > 0; i -= 9) {
        if (i < 9)
            a.push_back(atoi(stra.substr(0, i).c_str()));
        else
            a.push_back(atoi(stra.substr(i - 9, 9).c_str()));
    }


    for (int i = (int) strb.length(); i > 0; i -= 9){
        if (i < 9)
            b.push_back(atoi(strb.substr(0, i).c_str()));
        else
            b.push_back(atoi(strb.substr(i - 9, 9).c_str()));
    }

    while (a.size() > 1 && a.back() == 0)
        a.pop_back();

    while (b.size() > 1 && b.back() == 0)
        b.pop_back();


    int carry = 0;
    for (size_t i=0; i<max(a.size(),b.size()) || carry; ++i) {
        if (i == a.size())
            a.push_back (0);
        a[i] += carry + (i < b.size() ? b[i] : 0);
        carry = a[i] >= base;
        if (carry)  a[i] -= base;
    }
    b.clear();
    b.shrink_to_fit();
    std::vector<int>res;
    res.push_back(a.empty() ? 0 : a.back());

    for (int i=a.size()-2;i>=0;i--) {
        int len2=9;
        if (!a[i])
            while(--len2) res.push_back(0);
        else
            while (a[i]<pow(10.0,--len2)) res.push_back(0);
        res.push_back(a[i]);
    }
    a.clear();
    a.shrink_to_fit();
    printBigNumber(res);
}

[Wataru]

impelix, А дайте задачу целиком. Что там за ограничения по числам? По памяти и по времени?

Может, надо суммировать не разворачивая вот эти вот группы. Если там дается, скажем, до миллиона групп, но в каждой может быть до миллиона чисел, то вы падаете по памяти еще во время ввода.

Тут надо прочитать пары (цифра, количество), развернуть их списки, а потом суммировать погрупно. Если группы одинакового размера - сложили их. если нет, то откусили от более длинной групы кусок равный более короткой. Обработали. Из-за переноса можно в ответ вписать сразу несколько групп. В ответе в конце надо будет подряд идущие одинаковые группы цифр слить в одну группу. Ну и развернуть перед выводом.

Надо порисовать на бумажке, что будет, если сложить "aa...a", "bb....b" и еще перенос (0 или 1) в правый разряд.

[impelix]

Условие:
Один из используемых форматов заключается в следующем: число задаётся группами подряд идущих в
десятичной записи цифр. То есть число 111 задаётся как 3 1, чисор 2020 — как 1 2 1 0 1 2 1 0, число 222 233
как 4 2 2 3. Отметим, что длина группы должна быть максимальной, то есть запись 2 2 2 2 2 3 в последнем
случае является некорректной.
Для проверки ответов игроков Вам требуется написать программу, складывающую числа в вышеописанном
формате
Формат входных данных:
Первая строка входных данных содержит целое число N — количество групп одинаковых цифр в записи
первого слагаемого (1 ≤ N ≤ 100). i-я из последующих N строк содержит по два целых числа ni и di
(1 ≤ ni ≤ 10^18 , 0 ≤ di ≤ 9). Гарантируется, что соседние di всегда различны, di != 0 и сумма всех ni не превосходит 10^18
В таком же формате идет второе слагаемое.
Вывод нужен в формате таком же как и ввод

[Wataru]

impelix, охохо! ni <= 10^18. Вот вы столько цифр пытались запихать в массив. Конечно, оно падает по памяти, тут нужны миллионы терабайт. Да, надо складывать, как я написал в последнем комментарии: группа с группой.

[Wataru]

impelix, Я исправил ответ