## Saturday, July 23, 2016

### Codeforces Round #360 (Div. 1) - D. Dividing Kingdom II

Problem Statement:
http://codeforces.com/contest/687/problem/D

Summary:
n < 1000 vertices, m = O(n^2) weighted edges (numbered from 1 to m), and q < 1000 queries (L, R) to consider all edges number L to R, group the endpoints of the edges into two groups 0 or 1, and minimize the weight of the edge with the largest weight having its endpoints in the same group.

Solution:
The idea to solve the problem is interesting. Consider the query (L, R). If we go through all the edges numbered L to R in decreasing weight order, then for each edge (u, v) we will attempt to join the vertices u and v, which leads to three possibilities:
1. u and v are not in the same connected component. This means that u and v can be connected together and their connected components will form one larger connected components which is bipartite.
2. u and v are already in the same connected component. Before addition of edge u-v, the connected component is bipartite. Hence we need to check if the addition of u-v still maintains this property. This means we must check if u and v are in different group/color. If they are of different group, we can join them without problem.
3. Otherwise, u and v are of the same group/color. Hence u-v is the first edge such that its addition causes its connected component to be not bipartite. We conclude that the weight of edge u-v is the answer for the current query (L, R). [Contemplating about this further, here is why this is correct: we have proven to ourselves by construction that the answer to the query (L, R) is at most the weight of u-v, because we can indeed create bipartite components using all the edges of higher weight before u-v. To prove that the answer cannot be smaller than u-v, first observe that a cycle of odd length cannot be bipartite. Hence when u-v connects two vertices of the same color, we conclude that u-v introduces an odd cycle to the connected component. Hence there the edges from the highest weight to u-v cannot be bipartite due to the existence of the odd cycle, which means u-v must be the smallest possible answer to the query].

The implementation given here is not the most efficient one asymptotically (the expected solution seems to use segment tree of 'interesting' edges). It follows exactly the idea described above.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight, id;
};
int n, m, q;
int color[1010], par[1010], sz[1010];
vector<Edge> edges;
void Init(){
for (int i=0;i<n;++i){
par[i]=i;
color[i]=0;
sz[i]=1;
}
}
int FindPar(int u) {
return par[u] == u ? u : (par[u] = FindPar(par[u]));
}
bool Combine(int u, int v) {
int x = FindPar(u);
int y = FindPar(v);
if (x == y) {
return color[u] != color[v];
}
if (sz[x] > sz[y]) {
swap(x, y);
swap(u, v);
}
if (color[u] == color[v]) {
for (int i=0;i<n;++i){
if (FindPar(i)==x) color[i] ^= 1;
}
}
par[x] = y;
if (sz[x] == sz[y]) sz[y]++;
return true;
}
int Query(int L, int R) {
Init();
for (int i=0;i<m;++i){
if(L <= edges[i].id  && edges[i].id <= R) {
if (!Combine(edges[i].u, edges[i].v)) return edges[i].weight;
}
}
return -1;
}
int main(){
scanf("%d%d%d",&n,&m,&q);
int u,v,w;
for(int i=0;i<m;++i){
scanf("%d%d%d",&u,&v,&w);
if (u > v) swap(u,v);
--u; --v;
edges.push_back({u, v, w, i});
}
sort(edges.begin(), edges.end(),
[](const Edge& L, const Edge& R) {
return L.weight > R.weight;
});
int l,r;
for(int qq=0;qq<q;++qq){
scanf("%d%d",&l,&r);
l--;r--;
printf("%d\n",Query(l,r));
}
return 0;
}