JasonMendoza2008's blog

What is the complexity? Is this hackable?
By JasonMendoza2008, history, 3 days ago, In English

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

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it +6 Vote: I do not like it

I agree with your analysis. The DFS part takes amortized $$$|E(G)| = n - 1$$$ time, and the other part takes $$$O(n)$$$. Just to spell out formally what you already suggested — let $$$T(v)$$$ be the time taken in the while loop while $$$v$$$ is the first node. Then,

$$$ T(v) = \Delta(G) - \Delta(G \setminus v) $$$

Now, let $$$x$$$ be any vertex of max degree.

  • If $$$v$$$ is not a neighbor of $$$x$$$, and is not $$$x$$$ itself, then $$$\Delta(G) = \Delta(G\setminus v)$$$.

  • If $$$v$$$ is a neighbor of $$$x$$$, then $$$\Delta(G \setminus v) \ge \Delta(G) - 1$$$.

  • If $$$v = x$$$, then it could be the case that $$$T(v) = O(n)$$$. But, summing over all $$$v$$$, we have

$$$\sum_{v \in V} T(v) \le \sum_{v \not \in Nb(x) \cup \{x\}} 0 + \sum_{v \in Nb(x)} 1 + \sum_{v = x} n$$$
$$$= 0 + deg(x) + n$$$
$$$\le 2n$$$
$$$=O(n)$$$

Let's say the analysis did not work out so nicely in this problem, and there was a counterexample where the amortized time was quadratic. Your solution would still work perfectly, if instead of maintaining degrees_list_counter, you kept a multiset of the degrees, and you were guaranteed that "return max element from a multiset" was a "fast" operation.

In C++, they have dict, set, and multiset, which all are kept in order (I think they are BBST behind the scenes), and can return their max entry/key in log time.

The reason I bring this up: I also compete in Python, but sometimes I face a problem where an ordered set is just inherently the "right" data structure. Then I become sad and submit in C++ instead. It is probably good to learn some C++ for such cases. You can also use recursion more freely over in C++ world, which can be fun.

→ Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for spelling out formally my thoughts, that's what I needed to be convinced!

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

[email protected]

→ Reply