JPUFF - Editorial

Practice

Setter: Shubham
Tester: Hritesh Maurya
Editorialist: Anuj Patel

Medium

Flows

EXPLANATION:

Create a bipartite graph with 2∗N nodes: nodes on one side representing the indices and the other representing the values. Add edge from source to nodes on one side and add edge from nodes on other side to sink with capacity = 1. Add edge (capacity = 1) from a node x to a node representing a value V if x is a divisor of V and x is between 1 and n.

Note that the network formed is a unit network (all edges have capacity equal to 1).

Use maxflow algorithm (e.g. dinic). Print the matches.

SOLUTION:

Setter’s Solution

``````#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx2")

#define sync ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
#define unq(a) sort(all(a));a.resize(unique(all(a)) - a.begin())
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
//#define endl '\n'
//mt19937 rng(0);
using pii = pair<int , int>;

int inline max(const int x, const int y){return (x > y ? x : y);}
int inline min(const int x, const int y){return (x < y ? x : y);}
int inline abs(const int x){return (x < 0 ? -x : x);}

const int MAX = 1e5 + 5;
struct FlowEdge {
int v, u;
long long cap, flow = 0;
FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};

struct Dinic {
const long long flow_inf = 1e18;
vector<FlowEdge> edges;
int n, m = 0;
int s, t;
vector<int> level, ptr;
queue<int> q;

Dinic(int n, int s, int t) : n(n), s(s), t(t) {
level.resize(n);
ptr.resize(n);
}

void add_edge(int v, int u, long long cap) {
edges.emplace_back(v, u, cap);
edges.emplace_back(u, v, 0);
m += 2;
}

bool bfs() {
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : adj[v]) {
if (edges[id].cap - edges[id].flow < 1)
continue;
if (level[edges[id].u] != -1)
continue;
level[edges[id].u] = level[v] + 1;
q.push(edges[id].u);
}
}
return level[t] != -1;
}

long long dfs(int v, long long pushed) {
if (pushed == 0)
return 0;
if (v == t)
return pushed;
for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
int u = edges[id].u;
if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1)
continue;
long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
if (tr == 0)
continue;
edges[id].flow += tr;
edges[id ^ 1].flow -= tr;
return tr;
}
return 0;
}

long long flow() {
long long f = 0;
while (true) {
fill(level.begin(), level.end(), -1);
level[s] = 0;
q.push(s);
if (!bfs())
break;
fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, flow_inf)) {
f += pushed;
}
}
return f;
}
};

int main(){

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

//sync

vector<vector<int>> fac(MAX);
for (int i = 1; i < 1001; i++){
for (int j = i; j < MAX; j += i){
fac[j].push_back(i);
}
}
int t = 1;
cin >> t;
for (int tc = 1; tc <= t; tc++){
int n;
cin >> n;
vector<int> p(n);
// Note :: p[i] < MAX
for (int i = 0; i < n; i++){
cin >> p[i];
assert(1<=p[i] && p[i]<=95000);
}

for(int i=1;i<n;i++)
{
assert(p[i]>=p[i-1]);
}

Dinic d(2 * n + 2, 0, 2 * n + 1);
vector<vector<int>> g(n + 1);
for (int i = 1; i <= n; i++){
d.add_edge(n + i, 2 * n + 1, 1);
}
for (int i = 0; i < n; i++){
for (const int& x : fac[p[i]]){
if (x > n) break;
g[x].push_back(n + i + 1);
}
}
for (int i = 1; i <= n; i++){
for (const int& u : g[i]){
}
}
ll mxflow = d.flow();
assert(mxflow == n);
vector<pii> ed;
int l, r;
for (FlowEdge& e : d.edges){
l = min(e.v , e.u);
r = max(e.v , e.u);
if (e.flow != 1 or l < 1 or r > 2 * n){
continue;
}
ed.push_back({l , r});
}
assert(ed.size() == n);
sort(all(ed));
for (int i = 0; i < n; i++){
assert(ed[i].fi == i + 1);
assert(p[ed[i].se - n - 1] % (i + 1) == 0);
cout << p[ed[i].se - n - 1] / (i + 1) << " ";
} cout << endl;
}
cerr << "processor time: " << clock() / (double) CLOCKS_PER_SEC << "s    ";
return 0;
}
``````

Tester’s Solution

``````#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;

struct FlowEdge {
int v, u;
long long cap, flow = 0;
FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};

struct Dinic {
const long long flow_inf = 1e18;
vector<FlowEdge> edges;
int n, m = 0;
int s, t;
vector<int> level, ptr;
queue<int> q;

Dinic(int n, int s, int t) : n(n), s(s), t(t) {
level.resize(n);
ptr.resize(n);
}

void add_edge(int v, int u, long long cap) {
edges.emplace_back(v, u, cap);
edges.emplace_back(u, v, 0);
m += 2;
}

bool bfs() {
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : adj[v]) {
if (edges[id].cap - edges[id].flow < 1)
continue;
if (level[edges[id].u] != -1)
continue;
level[edges[id].u] = level[v] + 1;
q.push(edges[id].u);
}
}
return level[t] != -1;
}

long long dfs(int v, long long pushed) {
if (pushed == 0)
return 0;
if (v == t)
return pushed;
for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
int u = edges[id].u;
if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1)
continue;
long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
if (tr == 0)
continue;
edges[id].flow += tr;
edges[id ^ 1].flow -= tr;
return tr;
}
return 0;
}

long long flow() {
long long f = 0;
while (true) {
fill(level.begin(), level.end(), -1);
level[s] = 0;
q.push(s);
if (!bfs())
break;
fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, flow_inf)) {
f += pushed;
}
}
return f;
}
};

int main()
{
flash;
int T,n,i,j;
cin>>T;
while(T--)
{
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
map<int,vector<int>> fac;
for(i=0;i<n;i++)
{
int x = a[i];
if(fac[x].size()>0)
continue;
fac[x].push_back(1);
if(x>1 && x<=n)
fac[x].push_back(x);
for(j=2;j*j<=x;j++){
if(x%j==0){
if(j<=n)
fac[x].push_back(j);
if(j*j!=x && (x/j)<=n)
fac[x].push_back(x/j);
}
}
}

// debug_(PRINT FACTORS)
// {
//     for(auto it:fac){
//         cout<<it.first<<" : ";
//         for(auto kt:it.second)
//             cout<<kt<<" ";
//         cout<<endl;
//     }
// }

Dinic grp(2*n+2,0,2*n+1);
for(i=0;i<n;i++)
for(auto it:fac[a[i]]){
// cout<<i+1<<" "<<n+it<<endl;
}
for(i=0;i<n;i++){
// cout<<0<<" "<<i+1<<endl;
}
for(i=n+1;i<=2*n;i++){
// cout<<i<<" "<<2*n+1<<endl;
}
int flw = grp.flow();
int ans[n+1]={0};

for(FlowEdge &it:grp.edges){
int val = it.v;
int ind = it.u;
if(val==0 || ind==(2*n+1))
continue;
if(it.flow==1)
ans[ind-n] = a[val-1]/(ind-n);
// cout<<a[val-1]<<" "<<ind-n<<endl;
}
for(i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
}
``````