MAXGRAPH - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: still_me
Testers: the_hyp0cr1t3, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given an array A of N integers, construct a simple directed strongly connected graph on N vertices such that:

  • A_i = A_j means the edges i \to j and j \to i cannot exist. Also, A_i and A_j must have the same outdegree.
  • If u \to v, then v \to u cannot exist.
  • The number of edges is maximum under the above constraints.

EXPLANATION:

Suppose A has K distinct values, 0, 1, 2, \ldots, K-1.
Let’s consider the cases K \gt 2 and K = 2 separately.

K > 2

This case is in fact rather trivial.

For each 0 \leq i \lt j \leq K-1, add an edge from every vertex with color i to every vertex with color j.
This clearly satisfies every condition except strong connectivity.

Now, reverse all the edges from color 0 to color K-1. This keeps the number of edges the same, but also gives us strong connectivity.

Every pair of vertices with distinct colors has an edge between them in one direction, so this is of course the maximum we can achieve.

K = 2

This case is the meat of the problem.

Suppose there are X vertices labelled 0 and Y vertices labelled 1. Without loss of generality, let X \geq Y.

Suppose the respective outdegrees are A and B, for a total of AX + BY edges. Our aim is to maximize this quantity.
Note that the 1-vertices have a total indegree of AX, so one of them must have \displaystyle \left\lceil \frac{AX}{Y} \right\rceil incoming edges.

In particular, this means that B + \left\lceil \frac{AX}{Y} \right\rceil \leq X, since we can’t have both u\to v and v\to u as edges.
So, if we fix A, we obtain an upper bound on B.

So, let’s try every value of A from 1 to Y-1 (any more would be pointless).
For each value of A, obtain an upperbound on B. If this upper bound is positive, look at the value of AX + BY you get and take the maximum among them all.

If no valid pair (A, B) exists, the answer is of course -1.
Otherwise, now that we know A and B let’s construct a graph.

There are several ways to do this.

One simple way is to do it greedily:

  • First, pick Y vertices labelled 0, and connect them to all the Y 1-vertices in an alternating cycle.
  • Next, for each vertex labelled 1, choose the A vertices labelled 0 with smallest indegree (and which don’t already have an edge to/from it) and connect edges to them
  • Then, for each vertex labelled 0, choose the B vertices labelled 1 with smallest indegree (that don’t already have an edge to/from this vertex) and connect edges to them.
    • It’s always possible to find B such vertices, our initial computation of A and B ensured this.

This gives a valid graph, and we’re done.

TIME COMPLEXITY:

\mathcal{O}(N^2 \log N) per testcase.

CODE:

Setter's code (C++)
//	Code by Sahil Tiwari (still_me)

#include<bits/stdc++.h>
#define still_me main
#define endl "\n"
#define int long long int
#define all(a) (a).begin() , (a).end()
#define print(a) for(auto TEMPORARY: a) cerr<<TEMPORARY<<" ";cerr<<endl;
#define tt int TESTCASE;cin>>TESTCASE;while(TESTCASE--)
#define arrin(a,n) for(int INPUT=0;INPUT<n;INPUT++)cin>>a[INPUT]

using namespace std;
const int mod = 1e9+7;
const int inf = 1e18;
int N = 0;

pair<int,int> ed(int n , int m) {
    int a = -1 , b = -1;
    int ans = 0;
    for(int i=(m+n-1)/n;i<m;i++) {
        int A = i;
        int B = n - (A*n+m-1) / m;
        if(B == 0)
            continue;
        if((A*n + B*m) > ans) {
            ans = (A*n + B*m);
            a = A;
            b = B;
        }
    }
    return {a , b};
}

void solve() {
    int n;
    cin>>n;
    N+=n;
    vector<int> a(n);
    arrin(a , n);

    int k = *max_element(all(a)) + 1;
    vector<vector<int>> c(k);

    for(int i=0;i<n;i++){
        if(a[i] >= k) {
            print(a);
            cerr<<n<<" "<<a[i]<<endl;
            break;
        }
        c[a[i]].push_back(i);
    }
    // print(c[0]);
    // print(c[1]);
    
    if(k != 2) {
        vector<vector<int>> adj(n);
        for(int i=0;i<3;i++) {
            for(int j: c[i]) {
                for(int l: c[(i+1)%3])
                    adj[j].push_back(l);
            }
        }
        for(int i=3;i<k;i++) {
            for(int j: c[i]){
                for(int l: c[0])
                    adj[j].push_back(l);
            }
            for(int j=1;j<i;j++) {
                for(int l: c[i]) {
                    for(int m: c[j]) {
                        adj[m].push_back(l);
                    }
                }
            }
        }
        int ans = 0;
        for(auto i: adj) {
            ans += i.size();
        }
        cout<<ans<<endl;
        for(int i=0;i<n;i++) {
            for(auto j: adj[i])
                cout<<i+1<<" "<<j+1<<endl;
        }
        // cout<<"done\n";
        return;
    }
    if(c[0].size() > c[1].size())
        swap(c[0] , c[1]);
    // print(c[0]);
    // print(c[1]);
    auto x = ed(c[0].size() , c[1].size());

    if(x.first == -1) {
        cout<<-1<<endl;
        return;
    }

    int l = c[0].size() , r = c[1].size();
    // cerr<<l<<" "<<r<<endl;
    // if(l+r != n){
    //     cerr<<"uneq\n";
    //     return;
    // }
    vector<vector<int>> adj(n);
    vector<set<int>> fout(l) , sout(r) , fin(l) , sin(r);
    set<pair<int,int>> sindeg , findeg;
    for(int i=0;i<l;i++)
        findeg.insert({0 , i});
    for(int j=0;j<r;j++)
        sindeg.insert({(0) , j});
    // for(int i=0;i<l;i++) {
    //     adj[c[0][i]].push_back(c[1][i]);
    //     adj[c[1][i]].push_back(c[0][(i+1) % l]);

    //     fout[i].insert(i);
    //     sout[i].insert((i+1) % l);
    //     fin[(i+1) % l].insert(i);
    //     sin[i].insert(i);
    // }

    for(int i=r-1;i>=0;i--) {
        set<pair<int,int>> used;
        for(auto j: findeg) {
            if(used.size()+adj[c[1][i]].size() == x.second)
                break;
            if(sout[i].count(j.second) || sin[i].count(j.second))
                continue;
            used.insert(j);
        }
        if(used.size()+adj[c[1][i]].size() != x.second) {
            cerr << "here2\n";
            cerr<<x.first<<" "<<x.second<<endl;
            cerr<<l<<" "<<r<<endl;
            cerr<<used.size()<<" "<<adj[c[1][i]].size()<<" "<<x.second<<endl;
            cerr<<sin[i].size()<<endl;
            // return;
        }
        for(auto j: used) {
            sout[i].insert(j.second);
            fin[j.second].insert(i);
            adj[c[1][i]].push_back(c[0][j.second]);
            findeg.erase(j);
            findeg.insert({j.first+1 , j.second});
        }
    }


    for(int i=0;i<l;i++) {
        set<pair<int,int>> used;
        for(auto j: sindeg) {
            if(used.size()+adj[c[0][i]].size() == x.first)
                break;
            if(fout[i].count(j.second) || fin[i].count(j.second))
                continue;
            used.insert(j);
        }
        if(used.size()+adj[c[0][i]].size() != x.first) {
            cerr << "here1\n";
        }
        for(auto j: used) {
            // cerr<<j.first<<" "<<j.second<<endl;
            fout[i].insert(j.second);
            sin[j.second].insert(i);
            adj[c[0][i]].push_back(c[1][j.second]);
            sindeg.erase(j);
            sindeg.insert({j.first+1 , j.second});
        }
        // cerr<<endl;
    }
    // if(sindeg.count({2 , 4})) {
    //     cerr<<"YES\n";
    // }

    
    int kk = 0;
    cout<<l*x.first + r*x.second<<endl;
    for(int i=0;i<n;i++) {
        for(int j: adj[i]) {
            cout<<i+1<<" "<<j+1<<endl;
            kk++;
        }
    }
    if(l*x.first + r*x.second != kk) {
        cerr<<l<<" "<<r<<" "<<kk <<" "<< l*x.first + r*x.second<<endl;
    }
}

signed still_me()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("6.in" , "r" , stdin);
    // freopen("6.out" , "w" , stdout);
    tt{
        solve();
    }
    // assert(N <= 1000);
    return 0;
}
Tester's code (C++)
// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}

// -------------------- Input Checker Start --------------------
 
long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}
 
string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
 
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }
 
vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}
 
// -------------------- Input Checker End --------------------

struct node{
   node* sons[2];
   int cnt=0;
};
node* create(){
       node* temp=new node();
       temp->sons[0]=NULL;
       temp->sons[1]=NULL;
       temp->cnt=0;
       return temp;
} 
template<typename node>
struct trie{
   node* root=new node();
   void insert(int p){
       node* temp=root;
       for(int j=30;j>=0;j--){
           temp->cnt++;
           int k=(((1LL<<j)&p)!=0);
           if(temp->sons[k]==NULL){
               temp->sons[k]=create();
               temp=temp->sons[k];
           }
           else{
               temp=temp->sons[k];
           } 
       }
       temp->cnt++;
   }
   void erase(int p){
       node* temp=root;
       for(int j=30;j>=0;j--){
           temp->cnt--;
           if(p&(1<<j))temp=temp->sons[1];
           else temp=temp->sons[0];
       }
       temp->cnt--;
   }
   int query(int x){
       node* temp = root;
       int ans = 0;
       for(int j = 30; j >= 0; j--){
	       	if((1 << j) & x){
	       		if(temp->sons[0] and temp->sons[0]->cnt) {
	       			ans += 1 << j;
	       			temp = temp -> sons[0];
	       		}else{
	       			temp = temp -> sons[1];
	       		}
	       	}else{
	       		if(temp->sons[1] and temp->sons[1]->cnt) {
	       			ans += 1 << j;
	       			temp = temp -> sons[1];
	       		}else{
	       			temp = temp -> sons[0];
	       		}
	       	}
       }	
       return ans;
      // function of query
   }
};
const int maxn  = 1e5 + 5;
int p[maxn];
int sz[maxn];
void clear(int n=maxn){
    rep(i,0,n + 1)p[i]=i,sz[i]=1;
}
int root(int x){
   while(x!=p[x]){
       p[x]=p[p[x]];
       x=p[x];
   }
   return x;  
}
void merge(int x,int y){
    int p1=root(x);
    int p2=root(y);
    if(p1==p2)return;
    if(sz[p1]>=sz[p2]){
        p[p2]=p1;
        sz[p1]+=sz[p2];
    }
    else{
        p[p1]=p2;
        sz[p2]+=sz[p1];
    }
}

const int MOD = hell;
 
struct mod_int {
    int val;
 
    mod_int(long long v = 0) {
        if (v < 0)
            v = v % MOD + MOD;
 
        if (v >= MOD)
            v %= MOD;
 
        val = v;
    }
 
    static int mod_inv(int a, int m = MOD) {
        int g = m, r = a, x = 0, y = 1;
 
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        }
 
        return x < 0 ? x + m : x;
    }
 
    explicit operator int() const {
        return val;
    }
 
    mod_int& operator+=(const mod_int &other) {
        val += other.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
 
    mod_int& operator-=(const mod_int &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
           #if !defined(_WIN32) || defined(_WIN64)
                return x % m;
           #endif
           unsigned x_high = x >> 32, x_low = (unsigned) x;
           unsigned quot, rem;
           asm("divl %4\n"
            : "=a" (quot), "=d" (rem)
            : "d" (x_high), "a" (x_low), "r" (m));
           return rem;
    }
 
    mod_int& operator*=(const mod_int &other) {
        val = fast_mod((uint64_t) val * other.val);
        return *this;
    }
 
    mod_int& operator/=(const mod_int &other) {
        return *this *= other.inv();
    }
 
    friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
    friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
    friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
    friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
 
    mod_int& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }
 
    mod_int& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }
 
    mod_int operator++(int32_t) { mod_int before = *this; ++*this; return before; }
    mod_int operator--(int32_t) { mod_int before = *this; --*this; return before; }
 
    mod_int operator-() const {
        return val == 0 ? 0 : MOD - val;
    }
 
    bool operator==(const mod_int &other) const { return val == other.val; }
    bool operator!=(const mod_int &other) const { return val != other.val; }
 
    mod_int inv() const {
        return mod_inv(val);
    }
 
    mod_int pow(long long p) const {
        assert(p >= 0);
        mod_int a = *this, result = 1;
 
        while (p > 0) {
            if (p & 1)
                result *= a;
 
            a *= a;
            p >>= 1;
        }
 
        return result;
    }
 
    friend ostream& operator<<(ostream &stream, const mod_int &m) {
        return stream << m.val;
    }
    friend istream& operator >> (istream &stream, mod_int &m) {
        return stream>>m.val;   
    }
};
// d1 d2
//

int solve(){
 		int n = readIntLn(1,1e3);

 		vector<int> a = readVectorInt(n,0, n - 1);
 		int k = *max_element(all(a));
 		vector<vector<int>> vec(k + 1);
 		assert(k >= 1);
 		for(int i = 0; i < n; i++){
 			vec[a[i]].push_back(i + 1);
 		}
 		vector<pii> edges;
 		for(int i = 0; i <= k; i++){
 				assert(vec[i].size());
 		}
 		if(k > 2){
 			// sum(f_i * f_j)
 			
 			for(auto u: vec[0]){
 				for(auto v: vec[1]) edges.push_back({u,v});
 			}
 			//0->1
 			for(int col = 2; col <= k; col++){
 				for(auto u: vec[col]){
 					for(auto v: vec[0]) edges.push_back({u,v}); // col -> 0
 					for(auto v: vec[1]) edges.push_back({v,u}); // 1 -> col 

 					for(int t = 2; t < col; t++){
 						for(auto v: vec[t]) edges.push_back({u,v});
 					}	
 				}

 			}
 			cout << edges.size() << endl;
 			for(auto i: edges) cout << i << endl;
 				return 0;
 		}


 		if(vec[0].size() <= 1 or vec[1].size() <= 1){
 			cout << -1 << endl;
 			return 0;
 		}
 		if(vec[0].size() >  vec[1].size()) swap(vec[0], vec[1]);

 		int d1 = 0, d2 = 0;

 		int res = 0;
 		int n1 = vec[0].size();
 		int n2 = vec[1].size();
 		int min_out = (n1 + n2 - 1)/n1;
 		for(int i = min_out; i < n2; i++){
 			int min_pos = n1 - (i*n1 + n2 - 1)/n2;
 			if(min_pos > 0){
 				int tot = min_pos*n2 + i*n1;
 				if(tot > res){
 					res = tot;
 					d1 = i;
 					d2 = min_pos;
 				}
 			}
 		}	
 		//cout << d1 << " " << d2 << endl;
 		if(d1 == 0){
 			cout << -1 << endl;
 			return 0;
 		}
 		priority_queue<pii> pq;
 		vector<set<int>> ind(n + 1);
 		for(auto u: vec[1]){
 			pq.push({0,u});
 		}
 		for(auto v: vec[0]){
 			for(int k = 0; k < d1; k++){
 				auto [d, u] = pq.top(); pq.pop();
 				edges.push_back({v, u});
 				ind[u].insert(v);
 				pq.push({d - 1, u});
 			}
 		}
 		set<pii> st;
 		for(auto u: vec[0]){
 			st.insert({0, u});
 		}
 		for(auto v: vec[1]){
 			int cnt = 0;
 			vector<pii> upds;
 			for(auto [d,u]: st){
 				if(cnt == d2) break;
 				if(ind[v].count(u)) continue;
 				edges.push_back({v, u});
 				upds.push_back({d,u});
 				cnt++;
 			}
 			assert(cnt == d2);
 			for(auto [d,u]: upds){
 				st.erase({d,u});
 				st.insert({d + 1,u});
 			}
 		}

 		cout << edges.size() << endl;
 		for(auto i: edges) cout << i << endl;

 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t = readIntLn(1,100);
    while(t--){
        solve();
    }
    return 0;
}
1 Like

By breaking down this problem into a few cases, it’s possible to solve it without any searching whatever. As explained above, the only nontrivial situation is when there are two colors (K=2.) In this case, let A, X, B, and Y be as in the explanation above, so that there are X vertices colored 0 and Y colored 1, with X\ge Y, and so that the 0-vertices have outdegree A and the 1-vertices have outdegree B. Because of strong connectivity, every 0-vertex must have outdegree at least 1, so we must have A\ge 1 for A to be acceptable, and, again because of strong connectivity, every 0-vertex must have indegree at least 1. For there to be enough edges into the 0-vertices for this, it must be that BY \ge X, i.e., B \ge \lceil X/Y \rceil, for B to be acceptable. Since there are only XY edges available, we also need AX + BY \le XY. Now:

  • Suppose that {\rm gcd}(X, Y) = G > 1. In this case we can take A = Y/G, B = X(1 - 1/G). Since AX + BY = XY, this is obviously the largest number of edges possible.

    Given this choice of A and B, the edges can be placed by grouping the vertices into clumps of G vertices each. Each 0-clump is then connected to each 1-clump, making a complete bipartite graph on the clumps. Each connection uses a total of G^2 edges, G of which go from the vertices in the 0-clump to corresponding vertices in the 1-clump, and G(G-1) of which connect vertices in the 1-clump to all the other vertices in the 0-clump. This obviously gives a strongly connected graph.

  • The remaining possibility is that {\rm gcd}(X, Y) = 1. In this case the problem cannot be solved if Y is 1 or 2, since then X + \lceil X/Y \rceil Y > XY. Otherwise, you can use a well-known theorem which says that if {\rm gcd}(X, Y) = 1, then every integer Z which is at least XY - X - Y + 1 is expressible as Z = AX + BY, with A and B nonnegative integers. We cannot have a total number of edges Z which equals XY since then Y must divide A and X must divide B, meaning that the only possible solutions are A = Y, B = 0 and A = 0, B = X, neither of which are acceptable. Otherwise Z < XY, so A < Y and B < X. In this case A is uniquely determined by Z since its congruence class modulo Y is known. Similarly, B is uniquely determined by Z.

    Since Z = XY is impossible, try Z = XY - 1. If acceptable, this must give the maximum possible number of edges. Since Z is not divisible by Y, we must have A > 0, so A is acceptable. B will also be acceptable unless it is in the set \{0, 1, 2, ..., \lfloor X/Y \rfloor\}. However, these possibilities are ruled out unless the residue class of -1 modulo X is in the set \{0, Y, ..., Y \lfloor X/Y \rfloor\} of residue classes modulo X. This will happen exactly when X is congruent to 1 modulo Y, in which case we will have B = \lfloor X/Y \rfloor. In this case we must decrease Z to XY - 2, which must be acceptable, by similar reasoning.

    We have proven that in this case we can take AX + BY = XY - 1 unless X \mod Y equals 1, in which case we must take AX + BY = XY - 2. One way to place the edges is now to number the 0-vertices 0, \dots, X-1, number the 1-vertices 0, \dots, Y-1, place an edge from the 0-vertex I \mod X to the 1-vertex I \mod Y for I = 0, \dots, AX - 1, and place an edge from the 1-vertex J \mod Y to the 0-vertex J \mod X for J = (X - B)Y, (X - B)Y + 1, …, XY - 1. It’s easy to see that, because of the relative primality of X and Y, this gives a strongly connected graph.