I was solving 2063C - Remove Exactly Two and my idea (close to the editorial) is to brute force the first vertex to remove. And then to be clever, after updating the degrees of all adjacent vertices of that first vertex, when it comes to finding the subsequent max(degrees). Using a max-heap, that's easily doable in O(nlog(n)) and the editorial partially points in that direction.

The solution I wrote is similar but consists of having this list:

    degrees_list_counter: list[int] = [0] * (max(degrees) + 1)
    for degree in degrees:
        degrees_list_counter[degree] += 1

This allows me to brute force in that manner:

    best_ans: int = 0
    for node_first in range(n):  # BRUTE FORCE THE FIRST VERTEX
        ans: int = 1
        ans += degrees[node_first] - 1
        # UPDATE DEGREES_LIST_COUNTER
        for neighbour in graph[node_first]:  # THIS IS, LIKE IN A DFS, NOT MAKING ANYTHING QUADRATIC
            degrees_list_counter[degrees[neighbour]] -= 1
            degrees[neighbour] -= 1
            degrees_list_counter[degrees[neighbour]] += 1
        degrees_list_counter[degrees[node_first]] -= 1
        degrees[node_first] = 0
        degrees_list_counter[degrees[node_first]] += 1
        # NOW THAT DEGREES_LIST_COUNTER IS UPDATED
        # FIND THE VERTEX WITH THE HIGHEST DEGREE
        i: int = len(degrees_list_counter) - 1
        while i > 0 and degrees_list_counter[i] == 0:  
            # THIS LOOKS LIKE THIS MAKES THE SOLUTION QUADRATIC
            i -= 1
        ans += (i - 1) if i > 0 else -1

        best_ans = max(best_ans, ans)

Here, I claim that the solution is linear despite this while loop:

• If there is a vertex with super high degree and all the others have a low degree, I will end up with a linear time in that while loop only once.

• If there is (strictly) more than one vertex with super high degree, I will literally never end up with a linear time in that while loop.

• If there is no vertex with super high degree, well, no need to worry about traversing that while loop.

Is this true? Or am I wrong and this is hackable?

Full solution: https://codeforces.net/contest/2063/submission/306341538