PROBLEM LINK:
Setter: Shubham
Tester: Hritesh Maurya
Editorialist: Anuj Patel
DIFFICULTY:
Medium
PREREQUISITE:
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(chrono::steady_clock::now().time_since_epoch().count());
//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;
vector<vector<int>> adj;
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) {
adj.resize(n);
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);
adj[v].push_back(m);
adj[u].push_back(m + 1);
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 id = adj[v][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(0, i, 1);
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]){
d.add_edge(i, u, 1);
}
}
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")
#pragma comment(linker, "/stack:200000000")
#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;
vector<vector<int>> adj;
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) {
adj.resize(n);
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);
adj[v].push_back(m);
adj[u].push_back(m + 1);
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 id = adj[v][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]]){
grp.add_edge(i+1,n+it,1);
// cout<<i+1<<" "<<n+it<<endl;
}
for(i=0;i<n;i++){
grp.add_edge(0,i+1,1);
// cout<<0<<" "<<i+1<<endl;
}
for(i=n+1;i<=2*n;i++){
grp.add_edge(i,2*n+1,1);
// 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;
}
}