[Solution] Minimise Difference solution codechef | SnackDown 2021 – Online Qualifiers

SnackDown 2021 - Online Qualifiers - CodeChef

Minimise Difference solution codechef

You’re given a simple undirected graph GG with NN vertices and MM edges. You have to assign, to each vertex ii, a number CiCi such that 1CiN1≤Ci≤N and ij,CiCj∀i≠j,Ci≠Cj.

For any such assignment, we define DiDi to be the number of neighbours jj of ii such that Cj<CiCj<Ci.

You want to minimise maxi{1..N}Dimini{1..N}Dimaxi∈{1..N}Di−mini∈{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:

  • 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.

Minimise Difference solution codechef Input Format

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

Minimise Difference solution codechef Output Format

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 NN space separated integers – the ithith of which is CiCi in the corresponding assignment.

Minimise Difference solution codechef Constraints

  • 1T10001≤T≤1000
  • 1N,M31051≤N,M≤3⋅105
  • 1XYN1≤X≠Y≤N
  • The sum of NN across test cases does not exceed 31053⋅105.
  • The sum of MM across test cases does not exceed 31053⋅105.

Minimise Difference solution codechef Sample Input 1 

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

Minimise Difference solution codechef Sample Output 1 

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

Minimise Difference solution codechef Explanation

Test Case 11: The following assignment is optimal:

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

We can see that 33 has two neighbours with smaller values – 11 and 22. Vertex 55 is also its neighbour, but has a larger value. Therefore, D3=2D3=2.

Similarly, we can calculate:

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

Therefore, maxi{1..N}Dimini{1..N}Dimaxi∈{1..N}Di−mini∈{1..N}Di = 202−0 = 22.

Test Case 22: The following assignment is optimal:

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

The values of DD are:

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

Therefore, maxi{1..N}Dimini{1..N}Dimaxi∈{1..N}Di−mini∈{1..N}Di = 101−0 = 11.


Updating Soon…


Minimise Difference solution codechef

Game of Length solution codechef

 

Leave a Comment

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