Как минимум без мапы можно обойтись, тогда логарифм выкинешь.

Сильно не вчитывался, но если верно понял, то можнопройтись 1 раз по D, чтобы наполнить массив индексов. затем по этому массиву пройтись пока не насобираешь достаточное комплексити.

новый массив будет хранить индексы соответствующих объектов. Если взять пример твой, что он будет выглядеть так: 2, 0, 3, 1

Затем идем по новому массиву, ну идея ясна да.

Или я невнимательно читал :3

Как минимум без мапы можно обойтись, тогда логарифм выкинешь.

Насколько я понимаю, амортизированная сложность последовательного обхода мапа от begin до end это O(n). А построение мапа имеет такую же сложность, что и сортировка вектора - O(N log N)

Я так понял (возможно неверно), комплексити моего решения O(nlogn).

n log n - это только вставка в мапу. сложность вставки - log n, элементов - n.

то, что обход мепа(а он вовсе не обязан такое свойство давать эффективно) это сложность N, еще надо показать. если там просто дерево, то там будет беготня по поддеревьям, и сложность будет опять порядка n*log n

А почему бы не организовать min heap по (distance, complexity) и потом просто удалять вершину, пока суммарная сложность меньше P? Асимптотика одинаковая, но лишних телодвижений значительно меньше.

Полюбому сортировать Д придется.

Эмммм, тупо в цикле посчитать сумму чисел в массиве С пока она меньше P и счётчик итерации будет ответом? Зачем тут вообще расстояние? Ты же сказал «чтобь отрендерить объект 3, надо чтобы 2 и 1 уже были отрендерены.» следовательно тебе нужно идти строго по интексу, а не искать лучшие вариаты. Слишком всё просто… или нет и мне спать пора, в чём подвох? Это же даже не задача =)

D не отсортирован. Объект 3 на последнем месте стоит.

unordered_map<int, vector> - будет лучшим решением, мне кажется. Плюс можно выйграть, если сделать unordered_map::reserve(D.size()), также небольшой запас у вектора (элементов на 10). Если лезть в сортировку, то должно быть сложнее.

Автосудья сказал

Это как? Как проверяется эффективность? Запуск теста с замером времени?

unordered_map<int, vector> - будет лучшим решением, мне кажется.

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

по хорошему, тут сортировка массива пар <Di, Ci> по Di, потом проход по сортированному массиву от меньших к большим с подсчетом суммы.

Это же задача о рюкзаке в формулировке для зуммеров.

Плюсую min heap. Тебе в любом случае нужно отсортировать сложность по расстоянию, а затем остаётся только доставать по одному элементу пока не достигнешь вычислительной способности видеокарты

Чёт не подмал, что по нему в конце пройти надо. Значить сортировать.

А будет ли быстрее?

Но ведь сортировка это nlogn минимум. Будет ли оно быстрее вставки в мапу?

Будет ли оно быстрее вставки в мапу?

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

Асимптотическая сложность не меняется, так что мимо =|

Можно ли проблему решить более лучше именно по big O?

sudo cast Reset

Асимптотическая сложность не меняется, так что мимо =|

что мимо-то? погуглите std::map iterator complexity.

Ты не ответил на вопрос " Это как? Как проверяется эффективность? Запуск теста с замером времени?". Где-то это тест пощупать можно с выставлением оценки?

А вообще сортировка разная бывает, если тебе известен верхний лимит (а дальность ограничена либо экраном, либо настройками игры), то существует алгоритмы сортировки проще n log n.

Не компилировал, но по-идее, если с помощью чего-то в духе zip-iterator ручками отсортировать сначала по C, затем по D, асимптотика останется та же с точностью до константы, но с точки зрения локальности данных и работы с менеджером памяти всё должно быть намного приятней, это может дать прирост в разы или даже на порядок, т.к. обычно именно операции с памятью есть узкое место. Плюс потребление памяти будет ниже.

Лучше в среднем случае имхо можно сделать только если вторую сортировку реализовать вручную и прямо в ней как-то считать сумму.

офтопик

А ссылку на задачу религия не позволяет в постец включить?

мапы какие-то, хипы … почему нельзя просто отсортировать, а потом пройтись? Быстрее будет, хотя конечно асимптотика не изменится.

Давай ссылку на задачу.

Не компилировал, но по-идее, если с помощью чего-то в духе zip-iterator ручками отсортировать сначала по C, затем по D…

а задвинуть D в старшие 32 бита, а в младшие - C, и сразу сортировать… по такому вот числу…не позволяет особенная любовь к шаблонам?

тогда сразу будет отсортировано по distance-complexity.

Доступа к тестам нет.

Нет ссылки. Задача была на codility.

Пример такой сортировки в студию.

В студию :)

Этого может не позволять ОДЗ задачи. Да и int он таки в окружении leetcode 100% 32битный, потому, что там ляликс x86_64, потому, что он везде.

Так-то можно много ещё чего низкоуровневого придумать(например толи merge толи radix sort говорят можно не кисло ускорить на видюхе).

Если я правильно понял задачу, то как-то так: https://ideone.com/IrRtnr

Моя твоя не понимать.

Мое решение O(nlogn)? Да/Нет и почему?

Твое решение лучше O(nlogn)? Да/Нет и почему?

Этого может не позволять ОДЗ задачи. Да и int он таки в окружении leetcode 100% 32битный, потому, что там ляликс x86_64, потому, что он везде.

дальше думайте там… и не тащите сюда темплейты на два листа.

если дана суммарная сложность 6, то видимо она больше сложности любого из обьектов?

тогда можно D умножать на эту сложность. а не двигать в старшие 4 байта. то есть сортировать по весу D[i]* total_complexity + C[i].

Что это за закорюки? Можно на ц++?

Твое решение лучше O(nlogn)? Да/Нет и почему?

если вы там сортируете только по дистанции, а потом проходите, то сортировать по весу - D[i]* total_complexity + C[i]. будет лучше.

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

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

Сую их в multiset. Оно по дефолту сортирует, как и std::map.

Сую их в multiset. Оно по дефолту сортирует, как и std::map.

может под эффективностью они считают то, что нечего огород городить? критерии эффективности у них неясны

Твоя задача должна решаться без всяких n log n, у тебя есть «глубина отристовки», которая зависит либо от выхода за граница вида, либо в настройках ползунок. Например - Bucket Sort, заявляется, что у неё O(n+k), и вполне годно работает при равномерном распределении значений в каком-то диапазоне (что не вместилось - присваиваем некий max_val и ингорим в конце). Такой пример есть:

// C++ program to sort an
// array using bucket sort
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
// Function to sort arr[] of
// size n using bucket sort
void bucketSort(float arr[], int n)
{
     
    // 1) Create n empty buckets
    vector<float> b[n];
 
    // 2) Put array elements
    // in different buckets
    for (int i = 0; i < n; i++) {
        int bi = n * arr[i]; // Index in bucket
        b[bi].push_back(arr[i]);
    }
 
    // 3) Sort individual buckets
    for (int i = 0; i < n; i++)
        sort(b[i].begin(), b[i].end());
 
    // 4) Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++)
            arr[index++] = b[i][j];
}
 
/* Driver program to test above function */
int main()
{
    float arr[]
        = { 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434 };
    int n = sizeof(arr) / sizeof(arr[0]);
    bucketSort(arr, n);
 
    cout << "Sorted array is \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Вангую, что хотели нечто вроде:

int render(std::vector<int> D, std::vector<int> C, int P)
{
    std::vector<int> indices(D.size());
    for (int i = 0; i < D.size(); ++i) {
        indices[i] = i;
    }

    std::sort(indices.begin(), indices.end(), [&D](int a, int b) {
        return D[a] < D[b];
    });

    int i;
    for (i = 0; i < indices.size(); ++i) {
        int cost = C[indices[i]];
        if (cost > P) break;
        P -= cost;
    }

    if (i == indices.size()) return i;

    const int dist = D[indices[i]];
    auto left = indices.begin() + i;
    auto right = std::upper_bound(left, indices.end(), dist, [&D](int a, int b) {
        return D[a] < D[b];
    });

    std::sort(left, right, [&C](int a, int b) {
        return C[a] < C[b];
    });

    for (auto it = left; it != right; ++it) {
        int cost = C[indices[i]];
        if (cost > P) break;
        P -= cost;
        ++i;
    }

    return i;
}

map/multiset будут сильно проседать из-за выделения памяти под узлы. А сортировка сложностей нужна только для последнего видимого расстояния.

Тут, конечно, есть варианты в зависимости от входных данных, но скринов задачи нет, а без них так.

Мое решение – n log n. Я не уверен, что судья проверяет асимптотику. На тестах поймать отличие n от n log n довольно сложно. Считай, что log n это константа :) А вот поймать тормоза мапа по сравнению с массивом можно.

Аааа 🤦.

Суммарная сложность это до 2^31. Дальше читайте там…

Я не понимаю те закорюки что ты запостил.

И не очень понимаю как сортировать 2 массива вместе. Их ведь надо сортировать именно вместе одновременно. Потому что расстояние и сложность стоят под одним индексом. Отсортировав только один массив расстояний, мы теряем индексы сложности.

Я их склеил с помощью zip и отсортировал вместе. В C++ сделай массив пар. Если не хочется память тратить, то надо с нуля написать сортировку.

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

Предполагаю, что это ещё можно оптимизировать применив битовую маску чтобы отметить только существующие дистанции.