PROBLEM LINK:
Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest
Author: Saarang Srinivasan
Tester: Aryan Choudhary
Editorialist: Jyothi Surya Prakash Bugatha
DIFFICULTY:
Medium
PREREQUISITES:
Bridges, Dynamic Programming
PROBLEM:
There is a country of n houses and m bi-directional roads. We call a subset S of houses a city if every city in S is reachable from any other house in S. The funding required for a city S is equal to |S|^2. Also, we can build a new road between any two cities and the funding required to build a road is equal to c. We want to divide the country into 2 cities with exactly one road connecting these cities with minimum total funding. Note that the total funding is the sum of the funding required for both the cities and the funding needed to build the new roads, i.e. if the first city has x houses and the second one has y house and we build k new roads to achieve this, then the total funding will be equal to x^2 + y^2 + kc
EXPLANATION:
Let us call an edge connecting 2 cities as connector if it is the only edge connecting these 2 cities. First, observe that a pre-existing edge is a connector of some 2 cities if and only if it is a bridge. Also, the final graph should be connected, so we have to build k - 1 new edges irrespective of the connector, where k is equal to the number of connected components in the graph.
So first, find the minimum value of |A|^2 + |B|^2 such that
- A and B partition the set of vertices.
- At most, there is one edge between some vertex in A and some vertex in B.
And then add a\cdot (k - 1) to this value to get the final answer, where k equals the number of connected components in the graph.
Now, there are 2 cases to consider. The connector of the final graph, i.e. the graph we get after building new edges, is either a pre-existing edge or some new edge that we add.
Case 1: The connector is a new edge
If the initial graph is connected, any new edge can never be a bridge and hence can never be a connector. Now suppose that the initial graph is not connected. Let C_1, C_2 \dots C_k be the connected components of the graph. If A and B are the cities corresponding to final answer, then clearly either C_i \subseteq A or C_i \subseteq B for all 1 \leq i \leq k. So, partitioning of vertices into cities A and B is equivalent to partitioning of C_1, C_2 \dots C_k into 2 sets. Let us define s_i = |C_i|. The problem now boils down to finding the minimum value of the expression
over X, Y where X, Y form a partition of the set \{s_1, s_2 \dots s_k\}.
This is a classic Knapsack problem. But the runtime for this is \mathcal{O}(n^2) in the worst case. To speed this up, observe that there s_1 + s_2 + \dots + s_k = n. So, we can use the optimised knapsack to solve this, which is described here. Runtime - \mathcal{O}(n\sqrt{n})
Case 2: The connector is a pre-existing edge
Since a pre-existing edge can be a connector if and only if it is a bridge, compute all bridges in \mathcal{O}(n) using depth-first search. Also, for each bridge, compute the sizes of the 2 connected components that we get by removing this bridge. Suppose C_1, C_2 \dots C_k are the connected components. Consider some connected component C_i and some bridge B in this connected component. Suppose A and B are the two connected components that we get by removing this bridge. The rest of the connected components, i.e. all connected components other than C_i, should be connected to exactly one of A or B. So we iterate over all possible ways to connect the rest of the connected components to exactly one of A or B and find the minimum funding value, with B as connector edge, over all these possible ways.
Since the funding value only depends on the sizes of the cities, we can perform a knapsack on the multi-set \{|C_1|, |C_2| \dots |C_k|\} - \{|C_i|\} to compute all possible subset sizes. And then we iterate over all possible subset sizes x and find the minimum value of the expression
We do this for every bridge B and take the minimum overall B. But this is very slow, to speed this up, we will use a dynamic knapsack which allows both adding an element into the knapsack and removing an element from it in \mathcal{O}(n). First, add all the values |C_i| into the knapsack. Now we do the following
- Iterate s over all possible sizes of the connected components.
- Remove s from our knapsack.
- Let B_1, B_2 \dots B_r be the bridges that are contained in some connected component of size s.
- Let S = \{x_i\} \cup \{y_i\} where x_i, y_i are the sizes of the connected components we get by removing the bridge B_i.
- For each x \in S and for each possible subset sum v, compute the value (x + v)^2 + (n - x - v)^2 and update the minimum funding with this value.
- Add s back into our knapsack.
The second step takes \mathcal{O}(n) and the last step can be performed in \mathcal{O}(n) using 2-pointer technique. And since there are at-most \mathcal{O}(\sqrt{n}) distinct possible values for s, the run-time will be equal to \mathcal{O}(n \sqrt{n}).
Dynamic knapsack:
Let S be a multiset that is initially empty. And for x \leq n, let dp[x] = number of subsets of S with sum equal to x. Now if we want to add a positive a into our set S, then \overline{dp}[x] corresponding to new set is equal to dp[x] + dp[x - a] with dp[y] = 0 for y < 0. Instead of creating a new array \overline{dp}, we can just update the array dp as follows.
for x from n to a:
dp[x] += dp[x - a]
Observe that this operation is reversible, i.e. by doing
for x from a to n:
dp[x] -= dp[x - a]
we get back the previous dp array. And this is equivalent to removing the element x. Now the dp array does not depend on the order in which we add the elements. So, if we want to remove y \in S, then we can assume that adding y into S was the last operation we did and reverse it as described above.
So, this knapsack stores the number of subsets of S with a sum equal x and supports adding an element into S and removing an element from S in \mathcal{O}(n). We usually store these values modulo some large prime as these values can be arbitrarily large.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int MODS[8] = {999996469, 999996407, 999996383, 999996359, 999996341, 999996329, 999996317, 1000000007};
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
void solve_case();
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
int tt = 1;
std::cin >> tt;
while(tt--) {
solve_case();
}
return 0;
}
struct DSU {
int n, cntcmp;
vector<int> e;
DSU() : n(0) {}
DSU(int _) : n(_), cntcmp(_), e(_ + 1, -1) {}
inline int root(int x) {
return (e[x] < 0 ? x : (e[x] = root(e[x])));
}
inline bool same(int x, int y) { return root(x) == root(y); }
inline bool join(int x, int y) {
x = root(x), y = root(y); if(x == y) return false;
if(e[y] < e[x]) swap(x, y);
e[x] += e[y];
e[y] = x;
cntcmp -= 1;
return true;
}
};
const int mxn = 100 * 1000 + 2;
vector<array<int, 2>> g[mxn];
vector<int> tree[mxn];
int tin[mxn], low[mxn], sz[mxn], sub[mxn];
int tx, n, m;
long long c;
vector<int> bridges;
DSU uf;
map<int, pair<int, vector<bool>>> sizes;
void dfs(int v, int p) {
low[v] = tin[v] = ++tx;
for(auto &[u, id] : g[v]) if(u != p) {
if(tin[u] == -1) {
dfs(u, v);
low[v] = min(low[v], low[u]);
if(low[u] > tin[v]) {
bridges[id] = true;
} else {
//uf.join(u, v);
}
} else {
low[v] = min(low[v], tin[u]);
//uf.join(u, v);
}
}
}
int finsz(int v, int p = -1) {
sub[v] = -uf.e[uf.root(v)];
for(int u : tree[v]) if(u != p) {
assert(uf.root(v) != uf.root(u));
sub[v] += finsz(u, v);
}
return sub[v];
}
void solve_case() {
const int mod = MODS[rng() % 8];
cin >> n >> m >> c;
sizes.clear();
uf = DSU(n);
DSU comp(n);
for(int i = 0; i <= n; i++) {
tin[i] = low[i] = -1;
sub[i] = sz[i] = 0;
g[i].clear();
tree[i].clear();
}
tx = 0;
bridges.clear();
bridges.resize(m);
vector<array<int, 2>> ed(m);
for(int u, v, i = 0; i < m; i++) {
cin >> u >> v;
comp.join(u, v);
g[u].push_back({v, i});
g[v].push_back({u, i});
ed[i] = {u, v};
}
int number_of_components = comp.cntcmp;
//bridge and split components
vector<bool> seen(n + 1);
for(int i = 1; i <= n; i++) {
int v = comp.root(i);
sz[i] = -comp.e[v];
if(!sizes.count(sz[i]))
sizes[sz[i]].second = vector<bool>(sz[i] + 1);
if(!seen[v])
sizes[sz[i]].first += 1;
seen[v] = true;
}
for(int i = 1; i <= n; i++) if(tin[i] < 0)
dfs(i, -1);
if((accumulate(bridges.begin(), bridges.end(), 0) == 0) && number_of_components == 1)
return cout << -1 << '\n', void();
for(int i = 0; i < m; i++) if(!bridges[i])
uf.join(ed[i][0], ed[i][1]);
//cout << bridges.size() << endl;
for(auto &[x, y] : ed) {
int u = uf.root(x), v = uf.root(y);
if(u == v)
continue;
tree[u].push_back(v);
tree[v].push_back(u);
}
for(int i = 1; i <= n; i++) {
int id = uf.root(i);
//cout << id << ' ';
if(sub[id]) continue;
finsz(id);
}
//cout << endl;
for(int i = 0; i < m; i++) if(bridges[i]) {
auto &[x, y] = ed[i];
int u = uf.root(x), v = uf.root(y);
if(sub[u] > sub[v])
swap(u, v);
long long one = sub[u], two = sz[x] - one;
//cout << "Bridge: " << x << ' ' << y << endl;
//cout << sub[u] << ' ' << sub[v] << endl;
assert(1 <= one && one <= sz[x]);
assert(1 <= two && two <= sz[x]);
sizes[sz[x]].second[one] = true;
sizes[sz[x]].second[two] = true;
}
//knapsack part
vector<pair<int, pair<int, vector<int>>>> items;
for(auto &[x, y] : sizes) {
pair<int, pair<int, vector<int>>> next;
next.first = x;
next.second.first = y.first;
for(int i = 1; i < x; i++)
if(y.second[i])
next.second.second.push_back(i);
items.push_back(next);
//cout << y.first << " occurences of components of size: " << x << endl;
}
vector<int> cost;
for(auto &[szz, vec] : items) {
auto &[cnt, bri] = vec;
for(int bit = 0, left = cnt; bit < 12 && left > 0; bit++) {
int s = min(left, 1 << bit);
cost.push_back(szz * s);
//cout << "adding: " << s << endl;
left -= s;
}
}
int no = cost.size();
vector<int> knapsack(n, 0);
knapsack[0] = 1;
for(int i = 1; i <= no; i++) {
for(int j = n - 1; j >= 0; j--)
if(j + cost[i - 1] < n) {
knapsack[j + cost[i - 1]] += knapsack[j];
if(knapsack[j + cost[i - 1]] >= mod)
knapsack[j + cost[i - 1]] -= mod;
}
}
// cout << "Knapsack complete:" << '\n';
// for(int i = 0; i <= n; i++)
// cout << knapsack[i] << ' ';
// cout << endl;
auto remove = [&] (int x) {
for(int i = 0; i < n - x; i++) {
knapsack[i + x] -= knapsack[i];
if(knapsack[i + x] < 0)
knapsack[i + x] += mod;
}
};
auto add = [&] (int x) {
for(int i = n - 1; i >= x; i--) {
knapsack[i] += knapsack[i - x];
if(knapsack[i] >= mod)
knapsack[i] -= mod;
}
};
//finding the answer
long long answer = 1e18;
//new edge
for(long long i = n - 1; i > 0; i--)
if(knapsack[i] > 0)
answer = min(answer, i * i + (n - i) * (n - i));
//use existing bridge
for(auto &[szz, vec] : items) {
remove(szz);
auto &[cnt, possible] = vec;
int j = 0;
// cout << "Checking for: " << szz << ' ' << cnt << '\n';
// for(int x : possible)
// cout << x << ' ';
// cout << '\n';
if(possible.empty())
continue;
for(int i = n - 1; i >= 0; i--) if(knapsack[i] > 0) {
//cout << i << " is still possible\n";
while(j < possible.size() && i + possible[j] < n / 2) {
long long one = (i + possible[j]), two = n - one;
answer = min(answer, one * one + two * two);
j++;
}
if(j == possible.size()) j -= 1;
long long one = (i + possible[j]), two = n - one;
answer = min(answer, one * one + two * two);
}
add(szz);
}
answer += c * (number_of_components - 1);
cout << (answer >= 1e18 ? -1 : answer) << '\n';
}
Tester's Solution
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
*/
/*
Credits -
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/ (namespace atcoder)
Github source code of library - https://github.com/atcoder/ac-library/tree/master/atcoder
*/
#include <string>
#include <bits/functexcept.h>
#include <iosfwd>
#include <bits/cxxabi_forced.h>
#include <bits/functional_hash.h>
#pragma push_macro("__SIZEOF_LONG__")
#pragma push_macro("__cplusplus")
#define __SIZEOF_LONG__ __SIZEOF_LONG_LONG__
#define unsigned unsigned long
#define __cplusplus 201102L
#define __builtin_popcountl __builtin_popcountll
#define __builtin_ctzl __builtin_ctzll
#include <bitset>
#pragma pop_macro("__cplusplus")
#pragma pop_macro("__SIZEOF_LONG__")
#undef unsigned
#undef __builtin_popcountl
#undef __builtin_ctzl
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define dbg(args...) 42;
#define endl "\n"
#endif
// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
template <class T>
using ordered_set = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
// X.find_by_order(k) return kth element. 0 indexed.
// X.order_of_key(k) returns count of elements strictly less than k.
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
const lli INF = 0xFFFFFFFFFFFFFFFLL;
const lli SEED=chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(SEED);
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
namespace tourist{
template <typename T>
class graph {
public:
struct edge {
int from;
int to;
T cost;
};
vector<edge> edges;
vector< vector<int> > g;
int n;
function<bool(int)> ignore;
graph(int _n) : n(_n) {
g.resize(n);
ignore = nullptr;
}
virtual int add(int from, int to, T cost) = 0;
virtual void set_ignore_edge_rule(const function<bool(int)> &f) {
ignore = f;
}
virtual void reset_ignore_edge_rule() {
ignore = nullptr;
}
};
template <typename T>
class undigraph : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
undigraph(int _n) : graph<T>(_n) {
}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int) edges.size();
g[from].push_back(id);
g[to].push_back(id);
edges.push_back({from, to, cost});
return id;
}
};
template <typename T>
class dfs_undigraph : public undigraph<T> {
public:
using undigraph<T>::edges;
using undigraph<T>::g;
using undigraph<T>::n;
using undigraph<T>::ignore;
vector<int> pv;
vector<int> pe;
vector<int> order;
vector<int> pos;
vector<int> end;
vector<int> sz;
vector<int> root;
vector<int> depth;
vector<int> min_depth;
vector<T> dist;
vector<int> was;
int attempt;
dfs_undigraph(int _n) : undigraph<T>(_n) {
}
void init() {
pv = vector<int>(n, -1);
pe = vector<int>(n, -1);
order.clear();
pos = vector<int>(n, -1);
end = vector<int>(n, -1);
sz = vector<int>(n, 0);
root = vector<int>(n, -1);
depth = vector<int>(n, -1);
min_depth = vector<int>(n, -1);
dist = vector<T>(n);
was = vector<int>(n, -1);
attempt = 0;
}
void clear() {
pv.clear();
pe.clear();
order.clear();
pos.clear();
end.clear();
sz.clear();
root.clear();
depth.clear();
min_depth.clear();
dist.clear();
was.clear();
}
private:
void do_dfs(int v) {
was[v] = attempt;
pos[v] = (int) order.size();
order.push_back(v);
sz[v] = 1;
min_depth[v] = depth[v];
for (int id : g[v]) {
if (id == pe[v] || (ignore != nullptr && ignore(id))) {
continue;
}
auto &e = edges[id];
int to = e.from ^ e.to ^ v;
if (was[to] == attempt) {
min_depth[v] = min(min_depth[v], depth[to]);
continue;
}
depth[to] = depth[v] + 1;
dist[to] = dist[v] + e.cost;
pv[to] = v;
pe[to] = id;
root[to] = (root[v] != -1 ? root[v] : to);
do_dfs(to);
sz[v] += sz[to];
min_depth[v] = min(min_depth[v], min_depth[to]);
}
end[v] = (int) order.size() - 1;
}
void do_dfs_from(int v) {
++attempt;
depth[v] = 0;
dist[v] = T{};
root[v] = v;
pv[v] = pe[v] = -1;
do_dfs(v);
}
public:
void dfs(int v, bool clear_order = true) {
if (pv.empty()) {
init();
} else {
if (clear_order) {
order.clear();
}
}
do_dfs_from(v);
}
void dfs_all() {
init();
for (int v = 0; v < n; v++) {
if (depth[v] == -1) {
do_dfs_from(v);
}
}
assert((int) order.size() == n);
}
};
template <typename T>
vector<bool> find_bridges(dfs_undigraph<T> &g) {
g.dfs_all();
vector<bool> bridge(g.edges.size(), false);
for (int i = 0; i < g.n; i++) {
if (g.pv[i] != -1 && g.min_depth[i] == g.depth[i]) {
bridge[g.pe[i]] = true;
}
}
return bridge;
}
};
const int maxN = 1e5+2;
using bt = bitset<maxN>;
lli solve(const int n,const map<int, pair<int,vector<bool>>> &components){
lli ans=INF;
bt cur;
cur[0]=true;
cur[n+1]=true;
vector<vector<bool>> cuts;
auto addComponent=[&](int size,int freq){
lli b=1,val=0;
while(val+b<=freq){
cur|=cur<<(b*size);
val+=b;
b*=2;
}
cur|=cur<<((freq-val)*size);
};
for(const auto &z:components){
addComponent(z.X,z.Y.X-1);
cuts.pb(z.Y.Y);
}
auto f=[&](lli s){
dbg(s,n-s);
ans=min(ans,s*s+(n-s)*(n-s));
};
y_combinator([&](const auto &self,int l,int r,bt cur)->void{
if(l==r){
auto add=[&](const int addSize){
if(addSize>=n/2){
f(addSize);
return;
}
const int v=n/2-1-addSize;
const lli s=cur._Find_next(v);
if(s+addSize>=n)
return;
f(s+addSize);
};
const auto ¤t = cuts[l];
const int curSize = current.size()-1;
for(int i=0;i<=curSize;++i){
if(current[i])
add(i);
}
if(l==0){
add(0);
add(curSize);
}
return;
}
const int mid = (l+r)/2;
bt LC=cur,RC=cur;
for(int i=l;i<=mid;++i)
RC|=RC<<(cuts[i].size()-1);
for(int i=mid+1;i<=r;++i)
LC|=LC<<(cuts[i].size()-1);
self(l,mid,LC);
self(mid+1,r,RC);
})(0,sz(cuts)-1,cur);
return ans;
}
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
int T;
cin>>T;
while(T--){
int n,m,c;
cin>>n>>m>>c;
tourist::dfs_undigraph<int> g(n);
for(int i=0;i<m;++i){
int u,v;
cin>>u>>v;
u--;v--;
g.add(u,v);
}
auto bridges = tourist::find_bridges(g);
dbg(bridges);
map<int, pair<int,vector<bool>>> components;
int totalBridges = -1;
lli offset=-c;
for(int i=0;i<n;++i){
if(g.pe[i]!=-1)
continue;
offset+=c;
totalBridges++;
const int s=g.sz[i];
auto it=components.find(s);
if(it==components.end())
components[s]={0,vector<bool>(s+1,0)};
components[g.sz[i]].X++;
}
for(int id=0;id<m;++id){
if(!bridges[id])
continue;
totalBridges++;
const auto &e = g.edges[id];
int u=e.from, p=e.to;
if(g.pe[u]!=id){
swap(u,p);
assert(g.pe[u]==id);
}
// dbg(u,p);
const int root = g.root[u];
const int s=g.sz[u],tot=g.sz[root];
components[tot].Y[s]=true;
components[tot].Y[tot-s]=true;
}
if(totalBridges==0){
cout<<-1<<endl;
continue;
}
const lli ans=solve(n,components)+offset;
cout<<ans<<endl;
}
return 0;
}