4
\$\begingroup\$

I have n indexed socks, each of which has one of k colors. I also have a list that states which two socks I must wear at each of m days.

Of course I want always wear same color socks. But unfortunately I must follow the list. What I can do is to re-color some socks. The paint is expensive so I want to re-color the least possible number of socks. What is the number?

Input:

n m k
[color of sock 1] [color of sock 2] ... [color of sock n]
[pair for 1st day]
[pair for 2nd day]
...
[pair for mth day]

n, m and k are not larger than 200 000

Examples:

Input:

3 2 3
1 2 3
1 2
2 3

Output:

2

Input:

3 2 2
1 1 2
1 2
2 1

Output:

0

In my solution I find linked parts of socks. To do it I recursively look for socks which are in pair with one in any day (via dfs). All socks in a linked part must have one color. Now it's simple to determine how many socks must be re-painted in each linked part and to sum these numbers.

The problem is that my solution works rather slowly. It reaches the time limit (2000 ms) at the middle test. How do I improve my algorithm?

#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <stack>
using namespace std;

class Data {
    int n_socks, n_days, n_colors;
    vector<int> sock_color; // color of the sock
    vector<set<int>> sock_with; // what socks are in pair with this
public:
    Data() {
        cin >> n_socks >> n_days >> n_colors;
        sock_color.resize(n_socks);
        for (auto & c: sock_color) {
            scanf("%d", &c);
            --c;
        }
        sock_with.resize(n_socks);
        int l, r;
        for (int i = 0; i < n_days; ++i) {
            scanf("%d %d", &l, &r);
            sock_with[l - 1].insert(r - 1);
            sock_with[r - 1].insert(l - 1);
        }
    }
    int compute() {
        int sum = 0;
        vector<bool> visited(n_socks);
        int cur = 0; // first unvisited
        while (true) {
            visited[cur] = true;
            vector<int> color_number(n_colors);
            // how many socks of each color
            // are linked with cur
            ++color_number[sock_color[cur]];

            // let's find it via dfs:
            stack<int> st;
            st.push(cur);
            while (!st.empty()) {
                int u = st.top();
                st.pop();
                for (int v: sock_with[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        ++color_number[sock_color[u]];
                        st.push(v);
                    }
                }
            }

            int max = 0, all = 0; // linked
            for (int i: color_number) {
                all += i;
                if (i > max)
                    max = i;
            }

            // we should paint all except max
            sum += all - max;

            // finding next cur:
            for (; cur < n_socks; ++cur)
                if (!visited[cur])
                    break;
            if (cur == n_socks)
                break;
        }
        return sum;
    }
};

int main() {
    Data d;
    cout << d.compute() << endl;
    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.