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

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

Автор hell_hacker, история, 7 лет назад, По-английски

Here is the problem

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.

spoj

hell_hacker
7 лет назад
11

Комментарии (11)

Написать комментарий?

hell_hacker

7 лет назад, # |

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

→ Ответить

gabrielsimoes

7 лет назад, # |

← Rev. 2 →

Your code fails for this test:

5
I 6
I 4
I 6
I 2
K 2

EDIT: modified to a shorter one

→ Ответить

gabrielsimoes

7 лет назад, # |

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

→ Ответить

hell_hacker

7 лет назад, # ^ |

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.

→ Ответить

gabrielsimoes

7 лет назад, # ^ |

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.

→ Ответить

hell_hacker

7 лет назад, # ^ |

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.

→ Ответить

gabrielsimoes

7 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

hell_hacker

7 лет назад, # ^ |

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.

→ Ответить

gabrielsimoes

7 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

hell_hacker

7 лет назад, # ^ |

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.

→ Ответить

gabrielsimoes

7 лет назад, # ^ |

← Rev. 4 →

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;
}

→ Ответить