Minimise Difference Solution codechef

Minimise Difference Solution codechef

You’re given a simple undirected graph G with N vertices and M edges. You have to assign, to each vertex i, a number Ci such that 1CiN and ij,CiCj.

For any such assignment, we define Di to be the number of neighbours j of i such that Cj<Ci.

You want to minimise maxi{1..N}Dimini{1..N}Di.

Output the minimum possible value of this expression for a valid assignment as described above, and also print the corresponding assignment.

Note: Minimise Difference Solution codechef

  • The given graph need not be connected.
  • If there are multiple possible assignments, output anyone.
  • Since the input is large, prefer using fast input-output methods.

Input Format Minimise Difference Solution codechef

  • First line will contain T, number of testcases. Then the testcases follow.
  • The first line of each test case contains two integers N,M – the number of vertices and edges in the graph respectively.
  • The next M lines each contain two integers – X,Y, denoting that there exists an edge between vertex X and vertex Y.

Output Format Minimise Difference Solution codechef

The output of each test case consists of two lines:

  • The first line contains the minimum possible value of the expression described above.
  • The second line contains N space separated integers – the ith of which is Ci in the corresponding assignment.

Constraints Minimise Difference Solution codechef

  • 1T1000
  • 1N,M3105
  • 1XYN
  • The sum of N across test cases does not exceed 3105.
  • The sum of M across test cases does not exceed 3105.

Sample Input 1 Minimise Difference Solution codechef

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

Sample Output 1 Minimise Difference Solution codechef

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

Explanation Minimise Difference Solution codechef

Test Case 1: The following assignment is optimal:

  • C1=1
  • C2=2
  • C3=3
  • C4=4
  • C5=5

We can see that 3 has two neighbours with smaller values – 1 and 2. Vertex 5 is also its neighbour, but has a larger value. Therefore, D3=2.

Similarly, we can calculate:

  • D1=0
  • D2=1
  • D3=2
  • D4=2
  • D5=2

Therefore, maxi{1..N}Dimini{1..N}Di = 20 = 2.

Test Case 2: The following assignment is optimal:

  • C1=5
  • C2=3
  • C3=1
  • C4=2
  • C5=4

The values of D are:

  • D1=1
  • D2=1
  • D3=0
  • D4=1
  • D5=1

Therefore, maxi{1..N}Dimini{1..N}Di = 10 = 1.

Leave a Reply

Your email address will not be published. Required fields are marked *

*