PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Jatin Yadav
Tester: Riley Borgard
Editorialist: Aman Dwivedi
DIFFICULTY
Medium
PREREQUISITES
Graphs, MST, Bridges in a graph
PROBLEM:
There is a hidden undirected connected graph G with n nodes and m edges numbered 0, 1, \ldots m - 1, and a hidden permutation p_0, p_1, \ldots, p_{m-1} of edges. The graph doesn’t contain any self loops or multiple edges.
You only know the value of n and m. You can ask queries. In one query, you give the judge a vector w = [w_0, w_1, \ldots, w_{m-1}] of size m consisting of integers in the range [1, m]. The judge returns n - 1 integers e_0, e_1, \ldots, e_{n-2}, such that the edges numbered e_0, e_1, \ldots, e_{n-2} form a minimum spanning tree of the graph, if the edge numbered p_i had a weight w_i for each i = 0, 1, \ldots m - 1.
You need to find the hidden permutation in at most m queries, or claim that it can’t be found uniquely no matter how many queries you’re allowed to make.
EXPLANATION:
Let us see when the hidden permutation of the edges can be found, and when it is impossible to find the hidden permutation.
Claim: If the graph contains more than 1 bridge, then it is impossible to find the hidden permutation of the edges.
Proof
Suppose we have two bridges say b_1 and b_2 in the graph, then in every query these two edges will always be included and since they can appear in any order. Then it is impossible to decide the order in which these two edges occur.
Hence we can only find the hidden permutation only and only when the number of bridges is either 1 or 0.
Subtask 1:
Given Graph is a Tree.
If the given Graph G is tree then it means that all the edges of this tree are bridge edges. Since if we remove any edge from the graph, the graph will become disconnected i.e the number of connected components will increase.
Since it is impossible to find the permutation of edges, when the graph has more than 1 bridges. Hence for this subtask, all the graphs which have nodes greater than 2 we won’t be able to find the permutation of edges as proved above.
For a tree which has 2 nodes, there is a single edge and hence we can easily guess the permutation even without making a query.
Subtask 2:
Given Graph is a Cycle
If the given graph G is a cycle, then the graph has n nodes and n edges. It means for every query there will be only 1 edge that will be left out. Can we find the position of the left out edge in our permutation ?
Greedy Strategy:
For the i-th query, we will put the i-th weight maximum and remaining all the weights minimum. Hence, the MST of the graph will have all the edges expect this edge, and hence this edge will be left out.
Since the weight of w_i is assigned to p_i it means we will be able to find the p_i in the i-th query. Once we ask all m queries, we will have the permutation of edges.
Finally we can output the permutation of the edges.
Subtask 3:
Original Constraints
Since the judge can output any MST if there are more than MST in the graph. One way to make ensure that there exists unique MST for every query is to query weights in such a way that all the edges would have distinct weights.
Now we are left with finding the permutation of edges in this task. We can again use the greedy way to ask the queries.
Query all cyclic shifts of 1,2,3,…,m−1,m. If 𝑒 is not a bridge edge, then it’ll appear in the cyclic shift starting at 𝑒, but not in the cyclic shift starting at e+1.
Proof
If you query edge 𝑒 with weight 1 in some query, it’ll have weight m in the next cyclic shift. If it was a bridge edge, it would appear in both shifts. Else using properties of an MST, it would not appear in the second shift as there would be another edge with weight <m which would be more optimal.
Case 1:
If there is a edge that appears in the (i+1)^{th} query but not in i^{th} query it means that the edge which is left out in (i+1)^{th} query is the one which we have assigned the maximum weight and hence p_i=left out edge.
Case 2:
If the judge response remains same in consecutive queries it means that for the edge which we have assigned minimum weight in i^{th} query and maximum weight in (i+1)^{th} query, is a bridge edge and hence we increase the number of bridge edges in our graph. If. the number of bridge edges becomes greater than 1, then it means we won 't be able to find the permutation of edges.
Finally output the permutation of the edges.
TIME COMPLEXITY:
O(M^2) per test case.
SOLUTIONS:
Setter
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#endif
vector<int> query(vector<int> W);
const int MAXN = 1024;
bitset<MAXN> mst(int n, vector<int> W){
bitset<MAXN> ret;
cout << "? ";
for(int x : W) cout << x << " ";
cout << endl;
fflush(stdout);
for(int i = 0; i + 1 < n; i++){
int x; cin >> x;
assert(x != -1);
ret[x] = 1;
}
return ret;
}
vector<int> findHiddenPermutation(int n, int m){
vector<int> w(m), perm(m);
iota(all(w), 1);
bitset<MAXN> old = mst(n, w);
bitset<MAXN> init = old, ALL = old;
int bridges = 0;
int which = -1;
for(int i = 2; i <= m + 1; i++){
rotate(w.begin(), w.begin() + 1, w.end());
int pos_1 = find(all(w), 1) - w.begin();
// perm[pos_1] is the smallest edge
// Earlier, it was the heaviest edge
bitset<MAXN> now = i == m + 1 ? init : mst(n, w);
bitset<MAXN> nw = now & ~old;
if(nw.any()){
perm[pos_1] = nw._Find_first();
} else{
// perm[pos_1] is a bridge edge
which = pos_1;
bridges++;
}
old = now;
ALL &= now;
}
if(bridges >= 2) return {-1};
if(bridges == 1){
perm[which] = ALL._Find_first();
}
return perm;
}
int main(){
int subtask, t; cin >> subtask >> t;
while(t--){
int n, m; cin >> n >> m;
vector<int> vv = findHiddenPermutation(n, m);
cout << "! ";
for(int x : vv) cout << x << " ";
cout<<endl;
fflush(stdout);
int verdict;
cin >> verdict;
assert(verdict == 1);
}
}
Tester
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
vi query(int n, vi w) {
cout << "? ";
for(int x : w) cout << x << ' ';
cout << endl;
vi ve(n - 1);
for(auto &x : ve) cin >> x;
return ve;
}
vi findHiddenPermutation(int n, int m) {
vector<vector<bool>> b(m, vector<bool>(m, false));
vi w(m);
rep(i, 0, m) {
rep(j, 0, m) {
w[j] = (i + j) % m + 1;
}
vi q = query(n, w);
for(int x : q) b[x][i] = true;
}
vi bridge, p(m, -1);
rep(i, 0, m) {
int l = 0;
while(l < m && b[i][l]) l++;
if(l == m) bridge.push_back(i);
else {
while(!b[i][l]) l = (l + 1) % m;
p[(m - l) % m] = i;
}
}
if(sz(bridge) >= 2) return {};
for(int x : bridge) {
int i = 0;
while(p[i] != -1) i++;
p[i] = x;
}
return p;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int _, te;
cin >> _ >> te;
while(te--) {
int n, m;
cin >> n >> m;
vi ans = findHiddenPermutation(n, m);
if(ans.empty()) {
cout << "! " << -1 << endl;
}else {
cout << "! ";
for(int x : ans) cout << x << ' ';
cout << endl;
}
cin >> _;
}
}