PROBLEM LINK:
DIFFICULTY:
EASY
PREREQUISITES:
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:
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