PROBLEM LINK:
Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah
DIFFICULTY:
EASY
PREREQUISITES:
Testing
PROBLEM:
Given an undirected acylic graph, find a graph where minimum number of vertices to remove from the graph such that the maximum degree of the nodes of the graph decreases by at least 1 is less than (n+(k-1)t)/(2k). Here where n is the number of vertices, k is the maximum degree of the original graph, and t is the number of vertices having the degree k.
QUICK EXPLANATION:
There is no such graph, since the formula is from a research paper. Yet the setter missed a case where it was a totally disconnected graph. Containing nodes but none of them connected to each other.
EXPLANATION:
There is no such graph, since the formula is from a research paper. Yet the setter missed a case where it was a totally disconnected graph. Containing nodes but none of them connected to each other. This results in infinity, disproving the original research finding.
SOLUTIONS:
Solution by coders
2
0 0
0 0