if we have a triangle between 7,9 and 10 nodes, then one of them will have D=2 right?
Hey everyone! I would like to propose an alternative (yet not very different) method:
- The observation that when you assign the highest possible
Cto a node, itsDis equal to the number of unassigned neighbors of that node, is critical even in this solution. - Thus we may say that each edge of the graph is associated with a
Dvalue of 1, i.e. it will increase theDvalue of either of its ends when both are assigned a value. Therefore, the problem is now to one by one remove all the edges such that theDmaxof the graph is minimum. - Since we plan to remove the edges, the
Dof a node assigned the greatest value ofCavailable is now the degree of that node since only unassigned edges (edges leading to unassigned nodes) are present in our graph. - To choose which element should get the max
C, we may observe that the node having the minimum degree currently in the graph is the best option since any other choice would yield a higher value ofDmax. - Once we assign the node the greatest value, we may now delete it’s outgoing edges, and continue till all the nodes are assigned a value.
- The optimization comes here. Steps 4 and 5 only actually require the degree of a node, so instead of dealing with edges, we might just use the degree of the nodes.
- Now, to find the node with minimum degree and update the degrees, we may maintain a segment tree for them.
This way the complexity is O(M log N) which is just slightly better and I think it’s a bit easier to understand.
My solution : CodeChef: Practical coding for everyone
PS I hadn’t figured out the minimum D would always be zero.
5 Likes
There is no cycle
10 9 are no. of nodes and edges
Visualize it properly
1 Like
Here is my solution. There are two observations:
- Answer for the graph is >= answer for any subgraph (because an ordering of graph vertices induces an ordering on subgraph vertices).
- Let S be the smallest degree of a vertex in the graph. Then the answer is >= S. (Because the vertex labeled N has >= S neighbors and they all have smaller labels.)
Now take any vertex V of the smallest degree S, and let G’ be the induced graph on the remaining vertices. The observations show that Ans(G) >= max(S, Ans(G’)). We can construct an example when the equality is reached: find a solution for G’ and assign label N to the vertex V.
This gives the following algorithm: put all vertices in min-priority queue with priority=degree. Repeatedly extract the smallest-degree vertex, assign a label to it (starting with N) and decrease priorities of its neighbors. Complexity is M log N.
7 Likes
can you please share your code ? what do you mean by induced graph ?
thanks , but your explanation only actually helped me to get AC in one go ,
https://www.codechef.com/viewsolution/52683805
thanks again <3
By the way, the solution to this problem could be found on the net if you looked carefully. See this paper for example: https://arxiv.org/pdf/1212.2178.pdf (page 17).
1 Like
This greedy explanation is senseless until you provide some proof.
2 Likes
Can you please verify my logic:-
Logic:- maintain a min_heap whose each element is (e,i) where i is a node/index and e is the number of edges connected to it. we also maintain 2 separate arrays one stores e for each index i and the other is used to check if a certain index i has already been assigned a value or not.
// start with x = n ,ans=0 ...............(x= value to be assigned to a node; ans= Answer)
while(x>0):
{
pop (e,i) from the heap; //(e,i) is element with minimum value of e
if( i already has an assigned value) continue;
else
{
assign value x to i;
ans= max(ans, e);
x--;
for all nodes j connected to i :
{ ej--; //ej = number of edges connected to index j;
add (ej,j) to the heap; //Note: some element (ej+a,j) might already be present in the heap. But this value will always be popped after the element (ej,j) and get skipped.
}
}
}
I was too lazy to provide a proof for the greedy used in my initial solution (which is given in the bonus section) so I resorted to using this slower, albeit easier to explain solution.
Addressing your point, I don’t see how a proof for the greedy selection in the editorial is hard to deduce. Anyway, here’s a rough sketch -
Since we want to ensure D_i \le K for all i, we only assign a value to a node with \le K unassigned neighbours.
Say at some point in our greedy approach, we aren’t able to select a node that matches this constraint. Let’s assume there exists some other sequence of nodes S=\{s_1,s_2,\dots\,s_N\} which, when assigning values to in decreasing order (node s_i is assigned value N-i+1), we get a valid solution.
Now, since an assignment only reduces the number of unassigned neighbours of a node (and never increases it), we can iterate over S and assign values (from the point we are stuck at) to the corresponding nodes (ignoring nodes whose values we already set), to get a valid solution.
But this is only possible if in each assignment, the number of unassigned neighbours is \le K, a contradiction to our proposition, and we are done.
What if we use max priority queue and assigning start from 1 , and decreasing the degree of adjacent vertices of the graph?
Answer lies in this test case only. lol
1
10 9
1 2
2 3
2 4
2 5
5 6
6 7
7 8
7 9
7 10
2 Likes
My solution. Hope you all find this helpful/
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<vector> a(n);
vector in(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
a[u].push_back(v);
a[v].push_back(u);
in[u]++;
in[v]++;
}
set<pair<int, int>> st;
for (int i = 0; i < n; i++) {
st.insert(make_pair(in[i], i));
}
int ans = 0;
vector ans_a(n);
int fill_no = n + 1;
while (!st.empty()) {
fill_no–;
auto curr = st.begin();
st.erase(curr);
int adj_nodes_cnt = curr->first;
int curr_node = curr->second;
ans = max(ans, adj_nodes_cnt);
ans_a[curr_node] = fill_no;
for (auto adj_node : a[curr_node]) {
if (in[adj_node] > 0) {
in[adj_node]--;
in[curr_node]--;
st.erase(make_pair(in[adj_node] + 1, adj_node));
st.insert(make_pair(in[adj_node], adj_node));
}
}
}
cout << ans << ‘\n’;
for (int i = 0; i < n; i++) {
cout << ans_a[i] << " ";
}
cout << ‘\n’;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tc;
cin >> tc;
while (tc–) {
solve();
}
return 0;
}
Exactly, what I had thought but I couldn’t execute it efficiently.
I have a very simple solution for the solve(k) function mentioned in the editorial that works in O(M)
As mentioned in the official editorial, we will assign each node in decreasing order, but maintaining queue instead of a set
Lets say we check if max Di <= k
We maintain the number of unassigned neighbours of each node, starting with unassigned[i] = degree[i] . When we assign for node u , we will update unassigned[v]-- for all v that is a neighbour of u . We will also maintain a queue of all nodes with the number of unassigned neighbours that is <= k, which can be easily checked and added to the queue when updating unassigned[v]-- . If the whole graph is saturated, then we can safely declare that it is possible to assign each node so that max [i] <= k .
Combined with binary search, the time complexity is O(MlogN)
My implementation: here
Why the greedy is correct? Would someone please help explain?
why not just assigning larger values to nodes having lower degrees work??
because in any assignment, the order does not matter, only the set of assigned nodes at the end of the assignment matters. This is because we are already assuming that the answer(max D) is k. The number of unassigned neighbors can only decrease or stay the same after each assignment. So any vertex that has number of unassigned neighbors<=k at any point can be assigned a value; we can assign it now or later, it does not matter. You can think that each value of k has a set of nodes that are “assignable”, and we are trying to find the smallest value of k such that this set includes all the nodes of the graph.
1 Like