Soluție HackerRank pentru Clique. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Clique

Cerinta completa

A clique in a graph is set of nodes such that there is an edge between any two distinct nodes in the set. Finding the largest clique in a graph is a computationally difficult problem. Currently no polynomial time algorithm is known for solving this. However, you wonder what is the minimum size of the largest clique in any graph with [Expresie matematică indisponibilă în copia arhivată] nodes and [Expresie matematică indisponibilă în copia arhivată] edges.

For example, consider a graph with [Expresie matematică indisponibilă în copia arhivată] nodes and [Expresie matematică indisponibilă în copia arhivată] edges. The graph below shows [Expresie matematică indisponibilă în copia arhivată] nodes with [Expresie matematică indisponibilă în copia arhivată] edges and no cliques. It is evident that the addition of any [Expresie matematică indisponibilă în copia arhivată] edge must create two cliques with [Expresie matematică indisponibilă în copia arhivată] members each.

image

Input Format

The first line contains an integer [Expresie matematică indisponibilă în copia arhivată], the number of test cases.

Each of the next [Expresie matematică indisponibilă în copia arhivată] lines contains two space-separated integers [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

Output Format

For each test case, print the minimum size of the largest clique that must be formed given [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].

Sample Input

3  
3 2  
4 6  
5 7

Sample Output

2  
4  
3

Explanation

For the first case, we have two cliques with two nodes each:

image

For the second test case, the only valid graph having [Expresie matematică indisponibilă în copia arhivată] nodes and [Expresie matematică indisponibilă în copia arhivată] edges is one where each pair of nodes is connected. So the size of the largest clique cannot be smaller than [Expresie matematică indisponibilă în copia arhivată].

image

For the third test case, it is easy to verify that any graph with [Expresie matematică indisponibilă în copia arhivată] nodes and [Expresie matematică indisponibilă în copia arhivată]. The [Expresie matematică indisponibilă în copia arhivată] solid lines in the graph below indicate the maximum edges that can be added without forming a clique larger than [Expresie matematică indisponibilă în copia arhivată]. The dashed lines could connect any two nodes not connected by solid lines producing a clique of size [Expresie matematică indisponibilă în copia arhivată].

image
Hints
Turan’s theorem gives us an upper bound on the number of edges a graph can have if we wish that it should not have a clique of size [Expresie matematică indisponibilă în copia arhivată]. Though the bound is not exact, it is easy to extend the statement of the theorem to get an exact bound in terms of [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată]. Once this is done, we can binary search for the largest [Expresie matematică indisponibilă în copia arhivată] such that [Expresie matematică indisponibilă în copia arhivată]. See: Turan’s Theorem

Limbajul de programare folosit: python3

Cod:

#!/bin/python3

def turan_edges(n, r):
    q, rem = divmod(n, r)
    within = rem * (q + 1) * q // 2 + (r - rem) * q * (q - 1) // 2
    total = n * (n - 1) // 2
    return total - within


def min_largest_clique(n, m):
    if m > n * (n - 1) // 2:
        return n + 1
    lo, hi = 1, n
    while lo < hi:
        mid = (lo + hi) // 2
        if turan_edges(n, mid) >= m:
            hi = mid
        else:
            lo = mid + 1
    return lo


if __name__ == '__main__':
    t = int(input().strip())
    out = []
    for _ in range(t):
        n, m = map(int, input().split())
        out.append(str(min_largest_clique(n, m)))
    print('\n'.join(out), end='')

Scor obtinut: 1.0

Submission ID: 464610611

Link challenge: https://www.hackerrank.com/challenges/clique/problem

Clique