Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

LunaticPriest's blog

By LunaticPriest, history, 7 months ago, In English,

Hello, the mightly CodeForces community! It's me with another question because there are only 4 days left until the Turkey Olympiad in Informatics!!! I am trying to write the code that finds the LCA of 2 nodes with NlogN precomputation and logN per query. All the trees that I tested my code against, and all the corresponding edge cases give the correct output, so I don't really know where to fix. I've been debugging it for hours now :( Here is the code. I appreciate all your help, and I promise I will try to do my best to understand and implement your ideas!

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

»
7 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Can you share the link to the problem that you were testing your code with? It would help to debug

PS: for example, if the given graph is not a DAG rooted at node 1, your DFS is wrong, because you are visiting your parent

»
7 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Can it give TL because you reset $$$10005 \cdot 20$$$ values in the precompute function on each testcase?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    He doesn't reset on each query, he reset on each test case ...

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Sorry, that is what I meant. Fixed.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Okay, but he is not reseting 10005*20 on each testcase, he is reseting n*20 on each testcase, if the sum of n * 20 is not enough to solve in TL, it cant be solve with this code anyway

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          I probably should go to sleep, but lines 23 — 27 indicate otherwise.

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            oh, sorry, you are right!

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              The problem is: I don't even get TLE, I get WA. By the way, the graph is a DAG rooted at 1, and there are many people who solved the problem using binary lifting. I still couldn't find the bug ;(

»
7 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Hello,

Do take a look at line 65 :D

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I can't believe it... Thanks for the bug fix that took me hours :(

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It's always helpful to try tests with $$$t > 1$$$

      They help you find bugs involving typos like this, resetting arrays etc..

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        I will do this every time I encounter such problems. thanks for the advice!