hell_hacker's blog

Stuck in http://www.spoj.com/problems/ORDERSET/

By hell_hacker, history, 7 years ago, In English

Here is the problem

Here is my solution

I tried to solve it using treaps.

I keep on getting WA. In another attempt I tried to store values in map for checking duplicates(i won't insert when duplicates) but I got TLE. Can anyone help me in finding out the bug. Thanks.

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

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

Auto comment: topic has been updated by hell_hacker (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Your code fails for this test:

5
I 6
I 4
I 6
I 2
K 2

EDIT: modified to a shorter one

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

I like to start debugging treaps by commenting srand and always printing a tree traversal to see if everything is ordered, etc..

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

    Thank you for your help. I am new to this data structure. When running your provided input many times I am getting 4 sometimes and sometimes 6. I don't know why.

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

      Have you disabled "srand"? If you are seeding the random numbers with a different seed everytime, and your treap is bugged, then things like that can happen.

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

        Disabled as in srand(time(NULL)) or not using it at all? And I also read that one has to make sure all the priority values have to be distinct in a treap. How do we take care of that. Isn't it possible for rand() to return the same value twice over a large number of times.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          Pseudo-random number generators work like this: from a seed number, they generate all the other numbers. If you seed it with "srand" with the same seed every time, it will always produce the same numbers. Doesn't mean it will produce repeated numbers, only the same sequence of numbers. However, if you don't comment that line, your program will always generate a different sequence of numbers, which in turn produces a different tree (as node priorities will be different across different executions). So, to produce always the same tree, you should comment that line, but it should work fine nevertheless.

          EDIT: what you're doing in your code is seed rand with a different number everytime, as time(0) returns the current time.

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

            Yep, I removed the srand line now it gives proper output for both the inputs you provided. output 1 : 0 4 2 invalid output 2: 4

            But still WA on SPOJ.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              ← Rev. 2   Vote: I like it +1 Vote: I do not like it

              Try this one:

              7
I 4
I 5
I 7
I 7
I 6
I 2
K 5

              Try producing other tests and using them to debug your code. Print the tree traversal, and the value of the nodes you are entering into when searching for an element. It should give enough input to debug.

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

                I found a problem. The insert function. Could you tell me how to take care of duplicates. In insert function I had an if condition that if value of key of root is equal to value of key of the node to be inserted i just return. But if root key is not equal to key of node to be inserted and has lower priority it will be added.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                  ← Rev. 4   Vote: I like it +2 Vote: I do not like it

                  You could keep both the key (value) and a counter (how many are represented on the node).

                  EDIT: sorry, you actually should check whether an element has already been added or not, as according to the problem statement, an element is only added if it is not in the tree yet. You should check if the element exists, then add it it doesn't.

                  EDIT2: Something like this:

                  bool find(node* t, int val)
{
    if (!t) return 0;
    else if (t->key < val) return find(t->r, val);
    else if (t->key > val) return find(t->l, val);
    else return 1;
}
                  → Reply