Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Debugging help on (similar to) a lca problem
Автор memeset, история, 8 лет назад, По-английски

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!

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

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

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

    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!

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

      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

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

        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

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

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

          → Ответить