Hi Everyone,
Yesterday I made a post about getting a TLE on Codeforces round #788, problem B. Today I'm making another post, about getting a TLE on Codeforces round #788, problem C :). Once again, I have what I think is a nlog(n) solution, and while it's able to pass the first two pre-tests, it doesn't solve the third in a short enough period of time. I posted my solution below along with a short description of how it works, and I would highly appreciate any feedback on what I did wrong and how I can improve.
Thank you.
Solution: https://codeforces.me/contest/1670/submission/156244281
Explanation:
Read the input into three vectors, "a", "b", and "c"
Create an adjacency list ("graph") between the elements of "a" and "b"
While doing so, mark any elements of "c" with values other than 0 as "bad" in hash_map
Count the # of cycles in the "graph" using DFS and a stack; don't count cycles that include "bad" nodes
Iteratively calculate 2^(# of cycles) and use modular arithmetic to guard against overflow
I think the primary issue with my code is inside the DFS, but I don't know why because I think that by marking visited nodes, the complexity shouldn't exceed nlog(n).
there are many places i think you can optimize
countCycles(map<ll, ll> graph)-> you can use counCycle(map<ll,ll>& graph) as this one won't create new copy again and again which takes lot of time
also you can try using map inplace of unordered_map
Thanks for taking the time to look at my code! Unfortunately, the changes you suggested weren't enough to get my code over the TLE hump ):. I like the profile pic btw.
The function
countCycles(graph)
is being called for every iteration.Instead of
for(i = 0; i < countCycles(graph); ++i)
, store the value ofcountCycles(graph)
in a variable and then iterate .This was exactly the problem- thank you!
Yep, the main reason is that your countCycles function is being called for every iteration, resulting in O(n^2logn). A few more notes though:
Hope it helps!
Thx for your help, these are very good suggestions!