HackerRank - Неразделяемому Подмножество


В этой проблеме мы попросили:

Учитывая набор, С, из п различных чисел, напечатать размер максимальной подмножество, Ы', где сумма любых двух чисел в ней не равномерно кратно к.

Код

Моя идея заключается в том, что только соответствующие части остатки в отношении к. Кроме того, для каждого числа есть только одно число, которое можно подвести к к. Поэтому задача может быть сведена к подсчету количество чисел с одинаковым остатком и сравнения на счет ее дополнения, и накопления с максимальным значением. Следующий рисунок поясняет мысль, для следующих остатков и значения к = 5, мы должны считать +1 на 0, а затем добавить максимальным между каждой парой, чтобы получить общий размер максимальный набор.

enter image description here

Кроме того, номера которых остаток равен 0 и число-два К может быть включен только один раз в наборе.

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

int non_divisible_subset_size(int k, std::vector<int> &v) {
    if (v.begin() == v.end()) return 0;
    // Checking the remainder allows to group different numbers which have the same influence
    std::for_each(v.begin(), v.end(), [&k](auto& x){x%=k;});
    std::sort(v.begin(),v.end());
    int max_count{0};
    // Only one of the elements with remainder 0 can be added
    if (*v.begin()== 0) ++max_count;
    // Each element has only one complement that can sum up to k
    // The complement of a number betwen 0 to k/2 is located from k/2 to k-1
    // Therefore we only need to loop from (0 to k/2]
    for(auto it_lower=std::upper_bound(v.begin(),v.end(),0);
        *it_lower <= k/2;
        it_lower=std::upper_bound(v.begin(),v.end(),*it_lower)) 
    {
       auto it_upper = std::upper_bound(v.begin(),v.end(),*it_lower);
       int count;
       if (*it_lower*2 == k) {
           count = 1;
       }
       else { 
           count = it_upper-it_lower;
       }
       int complement = k-*it_lower;
       auto it_lower_comp = std::lower_bound(v.begin(),v.end(),complement);
       auto it_upper_comp = std::upper_bound(v.begin(),v.end(),complement);
       int count_comp = count;
       if (*it_lower_comp == complement) {
           if (complement*2 == k) {
               count_comp = 1;
           } 
           else { 
               count_comp = it_upper_comp - it_lower_comp;
           }
       }
       max_count += std::max(count,count_comp);
    }
    return max_count;
}

int main() {
    int n, k; std::cin >> n >> k;
    std::vector<int> v;
    v.reserve(n);
    while(n--) {
        int x; std::cin >> x;
        v.push_back(x);
    }

    int result = non_divisible_subset_size(k, v);
    std::cout << result << std::endl;
    return 0;
}

Вопросы

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



Комментарии
2 ответа

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

Начать с мелочей, я считаю, что:

std::for_each(v.begin(), v.end(), [&k](auto& x){x%=k;});

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

for (auto& x : v) x %= k;

если вы хотите сделать ваши намерения еще более очевидной с transform алгоритм:

std::transform(vec.begin(), vec.end(), vec.begin(), [k](auto&& i) {return i%k;});

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

// first step: counting modulo populations
std::map<int, int> counter;
for (auto elem: v) ++counter[v%k];

// second step: traversing different modulos
auto no_duplicates = std::unique(vec.begin(), vec.end());
std::for_each(vec.begin, no_duplicates, [](auto etc) { do_something(etc); });

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

Подводя итог, вот мое предложение:

int nonDivisibleSubset(int k, std::vector<int> vec) {
// 1. check for multiples of k, multiples of half of k, and retain only one of each
int res = 0;
auto multiples = std::remove_if(vec.begin(), vec.end(), [k](auto&& i) { return i%k == 0; });
if (multiples != vec.end()) ++res;
auto half_multiples = std::remove_if(vec.begin(), multiples, [k](auto&& i) { return 2*(i%k) == k; });
if (half_multiples != multiples) ++res;
// 2. for each possible modulo-complementary couple, choose the one with the most occurrences
std::transform(vec.begin(), half_multiples, vec.begin(), [k](auto&& i) {return i%k;}); // calculate modulos
std::sort(vec.begin(), half_multiples);
std::map<int, int> mods; // count their occurrences
std::for_each(vec.begin(), half_multiples, [&mods](auto&& i) {++mods[i];});
// and then examine each possible couple
auto uniques = std::unique(vec.begin(), half_multiples);
auto bottom_up = vec.begin();
auto top_down = std::reverse_iterator<std::vector<int>::iterator>(uniques);
while (bottom_up < top_down.base()) {
if (*bottom_up + *top_down == k) { // complementary
res += std::max(mods[*bottom_up], mods[*top_down]);
++bottom_up, ++top_down;
}
// if not complementary advance the closest from its origin
else if (*bottom_up < k - *top_down ) {
res += mods[*bottom_up++];
}
else res += mods[*top_down++];
}
return res;
}

P. S: Я уже пытался представить, что код и он проходит правильно.

4
ответ дан 31 января 2018 в 05:01 Источник Поделиться

Я наконец заставили его работать

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <iterator>

int non_divisible_subset_size(int k, std::vector<int> &v) {
// Count the mods occurrencies
using value = int; using occurencies = int;
std::map<value, occurencies> mods;
std::for_each(v.begin(), v.end(), [&mods,k](auto& x) {++mods[x%k];});
// 0 and k/2 mods can only be included once
int subset_size{0};
auto zero_mod = mods.find(0);
if (zero_mod != mods.end()) {
++subset_size;
mods.erase(zero_mod);
}
if (k%2 == 0) {
auto half_k_mod = mods.find(k/2);
if (half_k_mod != mods.end()) {
++subset_size;
mods.erase(half_k_mod);
}
}
if (mods.begin() == mods.end()) return subset_size;
// For each mod x there is only other mod x-k
// (with x-k > k/2) that sums up to k.
// For each pair count the one with more ocurrencies.
if (mods.size()==1) return subset_size += mods.begin()->second;
auto bottom_up = mods.begin();
auto top_down = mods.rbegin();
while (bottom_up->first <= top_down->first) {
if (bottom_up->first + top_down->first == k) {
subset_size += std::max(bottom_up->second,top_down->second);
++bottom_up, ++top_down;
}
// if not complementary count and advance the outter one
else {
if (top_down->first < k - bottom_up->first) {
subset_size += mods[bottom_up->first];
++bottom_up;
}
else {
subset_size += mods[top_down->first];
++top_down;
}
}
}
return subset_size;
}

int main() {
int n;
int k;
std::cin >> n >> k;
std::vector<int> v(n);
for(int i = 0; i < n; ++i){
std::cin >> v[i];
}

int result = non_divisible_subset_size(k, v);
std::cout << result << std::endl;
}

Фишка была в том, чтобы найти пары, подход bottom_up top_down из papagaga был быстрее, чем найти элементы.

1
ответ дан 1 февраля 2018 в 11:02 Источник Поделиться