Need help figuring out why this code is getting TLE. Problem link : 1829D - Gold Rush
void solve1829D()
{
int n, m, cnt = 0;
cin >> n >> m;
set<int> st;
st.insert(n);
while(st.size() > 0)
{
if(st.find(m) != st.end())
{
cout << "YES" << endl;
return;
}
int x = *st.begin();
st.erase(st.begin());
if(x % 3 == 0) {st.insert(x / 3); st.insert((x * 2) / 3);}
}
cout << "NO" << endl;
}
If $$$n$$$ is a large power of $$$3$$$ (say $$$3^k$$$) and $$$m = 2^k$$$, then you will end up with $$$2^{k+1} - 1 = \Theta\left(n^{\log_3 2}\right)$$$ iterations: every time you process an element $$$x$$$ which $$$3$$$ divides $$$p$$$ times, you replace it with two elements which $$$3$$$ divides $$$p-1$$$ times until $$$p = 0$$$, so the x-values you process form a perfect binary tree of height $$$k+1$$$. Because you always choose the smallest value in the set to process and you delete elements once you've processed them, you never end up inserting an element already in the set, so you process each of these $$$2^{k+1} - 1$$$ values separately, even though many are duplicates.
Your time complexity for one test case of this form is $$$\Theta\left(n^{\log_3 2} \log \log n \right)$$$, where the $$$\log \log n$$$ is overhead from the set, which will store $$$\Theta\left(\log n\right)$$$ elements most of the time. This is the worst-case scenario: if $$$n$$$ isn't a power of $$$3$$$ you'll just reach the base case $$$3 \hspace{-4pt} \not| \hspace{2pt} x$$$ faster.
Notice that there is no extra bound on the sum of $$$n$$$ over all test cases, so your overall worst-case complexity is $$$\Theta\left(t n^{\log_3 2} \log \log n\right)$$$, which is too slow for $$$t \approx 10^3$$$ and $$$n \approx 10^7$$$ ($$$\log_3 2 \approx 0.63$$$). (Naively evaluating this for $$$t = 10^3, n = 10^7$$$ yields about $$$1.2 \cdot 10^8$$$ operations, but
std::sethas a significant constant factor.)To fix this, either process the greatest element of the set each time (use
std::greateras your comparator) or maintain another set you don't delete from to avoid repeatedly processing the same value of x. There are only $$$\Theta\left(\log^2 n\right)$$$ distinct elements (they're of the form $$$2^a 3^b, a + b \le k = \Theta\left(\log n\right)$$$), so this should be fast enough.