MINDIFF1 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest

DIFFICULTY:

EASY

PREREQUISITES:

Greedy

PROBLEM:

Given an undirected graph with N vertices and M edges. Determine any permutation array C of length N such that, \max\limits_{1\le i\le N} D_i-\min\limits_{1\le i\le N} D_i is minimised, where D_i is the number of neighbours j of i such that C_i>C_j.

EXPLANATION:

Claim: \min\limits_{1\le i\le N} D_i is always equal to 0.

Proof

Consider the node x such that C_x=1. All neighbours y of x have C_y > C_x, making D_x=0. All elements of D are non-negative, and thus the minimum value over all D_i is 0.

The problem is then to minimise \max\limits_{1\le i\le N} D_i.

Let’s solve the problem by fixing the values for the nodes, in decreasing order. That is, we first assign a node to have value N, then assign a node to have value N-1 and so on, in some optimal fashion.
What’s special in this method? When we assign some node a value, we are guaranteed that the nodes assigned after it have a smaller value; therefore, it is easy to see that the value of D_i is equal to the number of unassigned nodes at the time of assigning node i a value, that are neighbours of i.

We binary search to find the answer. Let solve(k) return True if it’s possible to assign values to the nodes such that \max\limits_{1\le i\le N} D_i \le k and False otherwise.

To determine solve(k) for a particular k, we use the following greedy strategy, combined with the above method -
For each x from N\to1, assign some unassigned node with \le k unassigned neighbours, the value x. If at any point, there exists no unassigned node with \le k unassigned neighbours, return False. Else, return True.

Proof of optimality can be found here.

Implementation

How do we quickly determine an unassigned node with \le k unassigned neighbours? Maintain an ordered set of pairs (cnt_i,i), where cnt_i represents the number of unassigned neighbours of node i.

On assigning some node a value, remove the corresponding pair from the set. Also, modify the values of all unassigned neighbours (reduce cnt_i of each unassigned neighbour i by 1) to reflect the current status.

To determine an unassigned node with \le k unassigned neighbours, it suffices to take the node represented by the first element (assuming it is sorted in ascending order) in the set, which corresponds to the node with the least number of unassigned neighbours. Make sure to return False if the cnt value of this node is > k.

TIME COMPLEXITY:

Running a binary search to find the answer takes O(\log N). Maintaining the ordered set takes O(M\log N), since there are at most M updates done to the elements of the set.
The total time complexity is therefore:

O(M\log^2 N)

per test case.

SOLUTIONS:

Editorialist’s solution can be found TBA.

BONUS:

Solve the problem in O(M\log N).
Editorialists solution for the same can be found here.

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

2 Likes
2

why can’t we sort the array in decreasing order of number of neighbors and assign increasing node numbers?

7 Likes
3

What would be your answer to this testcase?

1
5 7
1 3
1 4
1 5
2 3
2 4
3 5
4 5

4

Consider this tc -
1
10 9
1 2
2 3
2 4
2 5
5 6
6 7
7 8
7 9
7 10
If you do it that way , then ans will come out to be 2.
the actual ans is 1.

2 Likes
5

i did something similar, it does not work may be because, when you have similar number of neighbors, it is not obvious to pick optimal one.

6

i don’t understand how it is obvious to pick any unassigned node with ≤ k unassigned neighbours.I do have raw intuition that why it might be a obvious thing to pick any node but not concrete one.

1 Like
7

if we have a triangle between 7,9 and 10 nodes, then one of them will have D=2 right?

8

Hey everyone! I would like to propose an alternative (yet not very different) method:

  1. The observation that when you assign the highest possible C to a node, its D is equal to the number of unassigned neighbors of that node, is critical even in this solution.
  2. Thus we may say that each edge of the graph is associated with a D value of 1, i.e. it will increase the D value 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 the Dmax of the graph is minimum.
  3. Since we plan to remove the edges, the D of a node assigned the greatest value of C available is now the degree of that node since only unassigned edges (edges leading to unassigned nodes) are present in our graph.
  4. 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 of Dmax.
  5. 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.
  6. 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.
  7. 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
9

There is no cycle
10 9 are no. of nodes and edges
Visualize it properly

1 Like
10

pls can anyone help why this code is giving TLE. it has same complexity as editorial.

Code

11

Here is my solution. There are two observations:

  1. Answer for the graph is >= answer for any subgraph (because an ordering of graph vertices induces an ordering on subgraph vertices).
  2. 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
12

can you please share your code ? what do you mean by induced graph ?

13

Induced subgraph
My solution
Setters solution from top post uses the same approach.

3 Likes
14

thanks , but your explanation only actually helped me to get AC in one go ,

https://www.codechef.com/viewsolution/52683805

thanks again <3

15

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
16

This greedy explanation is senseless until you provide some proof.

2 Likes
17

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.
              }
       }
}
18

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.

19

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
20

My solution. Hope you all find this helpful/