PROBLEM LINK:
Author: Md Shahid
Testers: Sandeep Singh, Soham Chakrabarti
Editorialist: Md Shahid
DIFFICULTY:
Medium
PREREQUISITES:
Bipartile Graph
PROBLEM:
In Chefland there is N number of soldiers live excluding Chef with strengths A_1,A_2,.......A_N. A huge battle is only possible if the following conditions exist:
- If you can divide all soldiers into two groups(not necessarily equal size) excluding Chef.
- Grouping is done in such a way that one group has maximum strength possible.
- At least one member of a group must have challenged at least one member of another group for war(If two or more groups exist).
- If two soldiers challenged themself then they can not exist in the same group because they became enemies to each other.
- It is possible that two different soldiers challenge the same soldier.
- If a soldier S_1 challenges a soldier S_2 then they must join the different groups.
- One soldier only exists in one group.
If all soldiers made M challenge to each other then you need to find out the maximum possible strength of the team which Chef will join.
EXPLANATION:
In the problem, it is given that you have a graph which don’t have any self loop(No soldier can challenge himself). If there are no challenges then there would not be any war i.e, when the value of edge(M) is zero.
If there exists at least one edge then you need to divide the vertices into two sets such that no two vertices in the same set can have an edge between them. Here comes the bipartile graph concept. In the Bipartile graph, we divide the graphs into two sets such that no two vertices in the set share the same edge. The easiest way to check a graph is Bipartile or not, is to check whether the given graph is two colorable or not. If the graph is two colorable then the answer always exists else war is not possible. If the given graph is two colorable then calculate the total strengths of every color in each component and take the maximum of them. At the end print the sum of maximum strengths from all components.
Let’s take an example-
In the above graph, we have four components with their respective strengths given in their respective nodes.
We can clearly see that the given graph is two colorable i.e, Bipartile graph. Now calculate maximum strengths from each and every component.
The maximum sum from component 1, maxForComp1 = (1+3) = 4. Same for the rests are maxForComp2 = 10, maxForComp3 = 5 and maxForComp4 = 4. So the total strengths for team which Chef will join are (maxForComp1 + maxForComp2 + maxForComp3 + maxForComp4) i.e, 23.
Time Complexity: O(N)
AUTHOR’S, TESTERS’ AND EDITORIALIST’S SOLUTIONS:
Author's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define ppb pop_back
#define pii pair<ll, ll>
#define vi vector<ll>
#define vull vector<ull>
#define vpii vector<pii>
#define mt make_tuple
#define ff first
#define ss second
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define revall(x) x.rbegin(), x.rend()
#define rep(i, j, k) for(ll i = j; i < (k); ++i)
#define repr(i, j, k) for(ll i = k-1; i >= (j); --i)
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define T int tt; cin>>tt; while(tt--)
const ll MOD = (ll)(1e9+7);
const int inf = (int)INFINITY;
const ll INF = (ll)INFINITY;
const int MAX = (int)(1e5+5);
vi G[MAX], a(MAX), color(MAX, -1);
pii ans;
bool isBipartite(int u) {
if(color[u] == 0) ans.first += a[u];
else ans.second += a[u];
for(int v : G[u]) {
if(color[v] == -1) {
color[v] = color[u]^1;
if(!isBipartite(v))
return false;
} else if(color[u] == color[v])
return false;
}
return true;
}
int main() {
fastio;
int t;
cin>>t;
while(t--) {
ll n, m, res = 0;
cin >> n >> m;
rep(i, 1, n+1) cin >> a[i];
rep(i, 0, m) {
int u, v;
cin >> u >> v;
G[u].pb(v);
G[v].pb(u);
}
bool poss = m ? true : false;
if(poss) {
rep(i, 1, n+1) {
if(color[i] == -1) {
color[i] = 0;
ans.first = ans.second = 0;
poss = isBipartite(i);
if(!poss) break;
res += max(ans.first, ans.second);
}
}
}
if(poss)
cout << "YES\n" << res;
else
cout << "NOT POSSIBLE";
cout << '\n';
rep(i, 1, n+1) G[i].clear(), color[i] = -1;
}
return 0;
}
Tester1 Solution(Soham Chakrabarti)
/* nuttela - Soham Chakrabarti */
#include <bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL)
#define all(v) v.begin(),v.end()
#define pb push_back
#define FR(i,j,k) for(int i=j;i<k;i++)
#define FRR(i,j,k) for(int i=j;i>=k;--i)
#define ff first
#define ss second
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <ll,ll> pii;
const int N = 1e5+5;
const int M = 1e3;
const int inf = INT_MAX;
const int MOD = 1e9 + 7;
vector<ll> adj[N], arr, side;
ll color[2];
bool check(int u)
{
color[1] = arr[u];
color[0] = 0;
side[u] = 1;
queue <int> q;
q.push(u);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v:adj[u])
{
if (side[v] == -1)
{
side[v] = 1 - side[u];
color[side[v]] += arr[v];
q.push(v);
}
else if (side[v] == side[u])
return false;
}
}
return true;
}
int32_t main() {
IO;
int t;
cin>>t;
while(t--) {
FR(i,0,N) {
adj[i].clear();
}
int n,m;
cin>>n>>m;
arr.assign(n,0);
side.assign(n,-1);
if(m==0){
cout<<"NOT POSSIBLE\n";
exit(0);
}
FR(i,0,n)
cin>>arr[i];
FR(i,0,m) {
int u,v;
cin>>u>>v;
adj[u-1].pb(v-1);
adj[v-1].pb(u-1);
}
ll sum=0,no=0;
FR(i,0,n) {
if(side[i]==-1) {
if(adj[i].empty())sum+=arr[i];
else{
if(check(i)) {
sum+=max(color[0],color[1]);
}
else {
cout<<"NOT POSSIBLE\n";
no=1;
break;
}
}
}
}
if(!no){
cout<<"YES\n";
cout<<sum<<endl;
}
}
return 0;
}
Tester2 Solution(Sandeep Singh)
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
vector<int> G[100005];
int colorArr[100005];
ll c[2];
vector<ll> st(100005);
bool isBipartite(int src)
{
colorArr[src] = 1;
c[1] = st[src];
c[0] = 0;
queue <int> q;
q.push(src);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v:G[u])
{
if (colorArr[v] == -1)
{
colorArr[v] = 1 - colorArr[u];
c[colorArr[v]] += st[v];
q.push(v);
}
else if (colorArr[v] == colorArr[u])
return false;
}
}
return true;
}
void solve(){
int n,i,j,m, u, v;
ll ans = 0;
cin>>n>>m;
for(i=1;i<=n;i++){
G[i].clear();
colorArr[i] = -1;
}
for(i=1;i<=n;i++)
cin>>st[i];
for(i=0;i<m;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
if(m==0){
cout<<"NOT POSSIBLE"<<endl;
return;
}
for(i=1;i<=n;i++){
if(colorArr[i]==-1){
if(G[i].empty()){
colorArr[i] = 1;
ans += st[i];
}
else{
if(isBipartite(i)){
ans += max(c[0],c[1]);
}
else{
cout<<"NOT POSSIBLE"<<endl;
return;
}
}
}
}
cout<<"YES"<<endl;
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t;
cin >> t;
while(t--)
solve();
}