m_nigam01's blog

By m_nigam01, history, 3 months ago, In English

Hello, my basic thinking is if I can connect all elements in x iterations. then x+1, x+2... can be ignored.

https://codeforces.com/contest/1830/submission/234754662

https://codeforces.com/contest/1830/submission/234753813

This is my submission in python and c++ one I've converted using help from gpt.

Thank you for reply.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

cond() has complexity $$$O(n^2 \log n)$$$.

Explanation

A faster solution would be just calling cond() once, with $$$m = n$$$, and return $$$i$$$ if the set size is $$$n$$$, but it's still too slow.

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Because this

auto cond = [](const vector<pair<int, int>> &edges, int m, int n) {
        set<int> s{1};
        for (int i = 0; i < m; ++i)
        {
            for (auto [u, v] : edges)
            {
                if (s.count(u))
                {
                    s.insert(v);
                }
                if (s.count(v))
                {
                    s.insert(u);
                }
            }
        }
        return s.size() == n;
    };

works in $$$O(m \cdot n\log n)$$$ or, in general, $$$\Omega(ans \cdot n\log n)$$$ (that is, the cond() complexity is $$$O(n^2\log n)$$$, because $$$ans = O(n)$$$)