memeset's blog

Debugging help on (similar to) a lca problem
By memeset, history, 8 years ago, In English

Hi everyone, I am getting a test case wrong for this problem and have already spent multiple days debugging. Could somebody please take a look at my code and help me find the bug?

A few things about the code: - an Event consists of an array of the lowest indexed people that are contained in a segment, in sorted order.

  • the array e[i][j] is the segment from vertex i to its 2^(j-1)th parent, inclusive, and stores events. e[i][0] is just that node's event, ie a segment with only itself.

  • dp[i][j] is the 2^jth parent of node i.

  • anc returns the kth ancestor of a vertex.

  • mergeevent merges two events' persons that are contained, while maintaining sorted order.

  • removeDup removes duplicates in the array.

Thanks everyone!

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

I couldn't understand your code completely ( specially answering queries part! ). but I had bad feelings about some part of it and I found this testcase :


4 8 1
1 2
2 3
3 4
1 2 3 4 1 2 3 4
1 4 10

you : 7 1 2 3 4 5 6 7
ans : 8 1 2 3 4 5 6 7 8

also consider these parts of your code : 

for(int i = 0; i < m; i++) {
        e[c[i]][0].a[e[c[i]][0].sz] = i + 1;
        e[c[i]][0].sz++;
    }

it can cause overflow!

(x.a[w] < y.a[z] && w < x.sz) always check index before accessing the array!

  • I didn't get the idea behind this : Event y = e[dp[i][max(j - 2, 0)]][j - 1]; why 'j-2' and no 'j-1' ?
  • How you are answering queries by just 3 merges , I thought it must be logarithmic ?
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi,

    The merging is actually a very small time since it only merges arrays of up to size 10 (in the problem statement, you only need the first 10 numbers). So the merging is like a constant and the log part comes from the lca. I took your tips into account and changed my code, and I also found a bug in my removeDup function.

    By the way I resubmitted and still got wrong answer haha.

    Thanks for your help!

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

      Yes, I know it is 10. Problem is not Time , Problem is that I think in answering queries you can't find the solution in constant time and it needs a Logarithmic algorithm.

      That's because you have saved solution for path lengths of 1,2,4,8,16,... . And you are using them for answering the queries so you must break lengths of paths to power of twos and it will need logarithmic time merging ...

      I solved the problem with almost your algorithm but I couldn't find constant time solution for answering the queries. link

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

        Ah, I see what you are saying. My idea was to merge two segments of length 2^something that, when combined, will encompass exactly the entire segment, with possible overlap. Kind of like the idea of a sparse table, which also can be found in constant time, if you know what i'm maybe trying to do?

        Thanks

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

          Yes, very nice. Now I got your idea. I had totally forgotten that trick in sparse table ...

          → Reply