m_nigam01's blog

By m_nigam01, history, 3 months ago,

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.

 » 3 months ago, # |   +10 cond() has complexity $O(n^2 \log n)$. ExplanationIf the tree is a line, and $m = n$, you add one edge for each $i$, and you spend $O(n \log n)$ for each $i$, so you spend $O(n^2 \log n)$ in total.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 →   0 Because this auto cond = [](const vector> &edges, int m, int n) { set 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)$)