SAT2020's blog

Another TLE
By SAT2020, history, 3 years ago, In English

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://mirror.codeforces.com/contest/1670/submission/156244281

Explanation:

  1. Read the input into three vectors, "a", "b", and "c"

  2. Create an adjacency list ("graph") between the elements of "a" and "b"

  3. While doing so, mark any elements of "c" with values other than 0 as "bad" in hash_map

  4. Count the # of cycles in the "graph" using DFS and a stack; don't count cycles that include "bad" nodes

  5. 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).

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

there are many places i think you can optimize

problem1
problem2
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The function countCycles(graph) is being called for every iteration.

Instead of for(i = 0; i < countCycles(graph); ++i), store the value of countCycles(graph) in a variable and then iterate .

int X = countCycles(graph) ;
for(i = 0; i < X; ++i){
   // Write Here
}
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This was exactly the problem- thank you!

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

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:

  1. When making adjacency lists, you should use a vector<vector> instead of a set, unless you need your adjacent nodes to be constantly sorted throughout. This reduces it from O(nlogn) to O(m+n)
  2. Similarly, visited and bad can be done with vectors rather than sets.
  3. In general, avoid unordered_maps unless absolutely necessary. There might be some anti-hashmap test. (though prob not relevant in this case)

Hope it helps!

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

    Thx for your help, these are very good suggestions!

    → Reply