Блог пользователя SAT2020

Another TLE
Автор SAT2020, история, 3 года назад, По-английски

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:

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

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

there are many places i think you can optimize

problem1
problem2
→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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
}
→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

→ Ответить