Description

Submission

A Stupid Submission

• Follow the explanation
• Greedy Algorithm, not always work, made the problem really complicated

#include <iostream>
#include <vector>
#include <map>
#include <experimental/map>

using namespace std;


/*
 * Complete the 'nonDivisibleSubset' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER k
 *  2. INTEGER_ARRAY s
 */

int nonDivisibleSubset(int k, vector<int> s) {
    vector<pair<int, int>> v; // pairs that divide
    map<int, int> m;    // count for each single number
    for(int i = 0; i < s.size(); ++i) {
        for(int j = i + 1; j < s.size(); ++j) {
            if((s[i] + s[j]) % k == 0) {
                v.push_back(pair<int, int>(s[i], s[j]));
                if(m.find(s[i]) != m.end()) m[s[i]]++;
                else m.insert(pair<int, int>(s[i], 1));
                if(m.find(s[j]) != m.end()) m[s[j]]++;
                else m.insert(pair<int, int>(s[j], 1));
            }
        }
    }
    while(!v.empty()) {
        map<int, int>::iterator max = m.begin();
        for(map<int, int>::iterator it = m.begin(); it != m.end(); advance(it, 1)) {
            if(it->second > max->second) max = it;
        }

        // remove max->first from related pairs
        for(auto it = v.begin(); it != v.end();) {
            if(it->first == max->first || it->second == max->first) it = v.erase(it);
            else ++it;
        }

        // remove max->first from map entries
        for(auto it = m.begin(); it != m.end(); ) {
            if(it->first == max->first) it = m.erase(it);
            else ++it;
        }


        // remove max->first from s
        for(auto it = s.begin(); it != s.end(); ) {
            if(*it == max->first) it = s.erase(it);
            else ++it;
        }
    }

    return s.size();
}

int main()
{
    int n; cin >> n;
    int k; cin >> k;

    vector<int> s(n);

    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    int result = nonDivisibleSubset(k, s);

    cout << result << "\n";

    return 0;
}

Smart Submission

• Categorize the numbers based on their remainder against k
• i and k-i are complementary, only one of these should survive, we should remove the one with fewer numbers in it
• When the remainder is 0, only 0 or 1 number in this category could survive
• When k is even and the remainder is k/2, only 0 or 1 number in this category could survive

#include <iostream>
#include <vector>
#include <map>
#include <experimental/map>

using namespace std;


/*
 * Complete the 'nonDivisibleSubset' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER k
 *  2. INTEGER_ARRAY s
 */

int nonDivisibleSubset(int k, vector<int> s) {
    vector<int> count(k);
    for(int i = 0; i < count.size(); i++) {
        count[i] = 0;
    }
    for(auto e : s) {
        count[e % k]++;
    }
    int r = 0;
    for(int i = 1; i <= (k - 1) / 2; i++) {
        if(count[i] == 0 || count[k-i] == 0) continue;
        int min = count[i] < count[k-i] ? count[i] : count[k-i];
        r += min;
    }
    if(k % 2 == 0) {
        r += (count[k/2] ? count[k/2] - 1 : 0);
    }
    return count[0] ? s.size() - r - count[0] + 1 : s.size() - r;
}

int main()
{
    int n; cin >> n;
    int k; cin >> k;

    vector<int> s(n);

    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    int result = nonDivisibleSubset(k, s);

    cout << result << "\n";

    return 0;
}