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;
}