The string given has even length. I want to pair elements so that all pairs have distinct elements. It is impossible to do so when count of any element exceeds n/2 where n is length of string. For the other case of max frequency of any character less than n/2, it seems it is always possible to pair them. I am not sure if this is too obvious or there is an easy explanation to this, but I came up with a rather long explanation:

Suppose I do make a combination where x pairs have identical elements. I would have in this case pairs like, some of pp, some of qq, some or rr and so on. I can always swap the right element of one of these with others, eg pq, qp, etc. This can always be done and in the end I might be left with some of only one type of identical pairs eg some of pp. These pairs cannot be more than n/2 since that would be first condition at the beginning. Thus, the other pairs that have a p in them can at-most be (n/2 — 2*x)/2, which means I will still have at-least (n/2 — (n/2 — 2*x)/2) = x pairs left that don't have a p in them, now I can swap the right p of all the top x elements with last x right elements, hence I have all distinct pairs.

Is there a simpler explanation to this?

(apologies for bad formatting, I have to work on that)

Hey folks, how the below code from here has O(√n) time complexity? Shouldn't it be equal to the number of prime factors of n?

vector<long long> trial_division1(long long n) {
    vector<long long> factorization;
    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}

Hello everyone, I have been trying to find shortest path using dijkstra with set by storing indices instead of index-distance pairs with the help of a custom comparator. It is failing on a very large test case and I am having a difficult time debugging it. Where am I doing wrong? Any type of hint would be appreciated.

The Problem My solution

vector<ll> d;
 
struct comp {
	bool operator()(const int& a, const int& b) const {
		return d[a] < d[b];
	}
};
 
void solve() {
	int n, m; cin >> n >> m;
	vector<vector<pii>> graph(n + 1);
	set<int, comp> q;											
	rep(m) {
		int a, b, c; cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));
	}
	vector<int> p(n + 1, -1);
	d.resize(n + 1, LLONG_MAX);
	d[1] = 0;
	q.insert(1);
	while(!q.empty()) {
		int node = *q.begin();
		q.erase(q.begin());
		for(auto adj : graph[node]) {
			if(d[adj.ff] > d[node] + adj.ss) {
				if(q.find(adj.ff) != q.end()) q.erase(adj.ff); 
				d[adj.ff] = d[node] + adj.ss;
				p[adj.ff] = node;
				q.insert(adj.ff);
			}	
		}
	}
	if(d[n] == LLONG_MAX) cout << -1 << endl;
	else {
		vector<int> path;
		while(n != -1) {
			path.push_back(n);
			n = p[n];
		}
		rep(path.size()) cout << path[path.size() - i - 1] << ' '; cout << endl;
	}
}

Operation : Change any array element to arbitrary integer, O(N^2) would give TLE, My approach : ans = Length of array — Length of longest non-decreasing sub-sequence because I want maximum length already sorted, TC : O(NlgN),
Is this approach correct? Any other approaches?