Weird behaviour of code

1

link to problem https://www.spoj.com/problems/HORRIBLE/
link to my code
https://pastebin.com/37PzHRSQ
when i am running the code 4-5 times on same test case the answer gets changed.i have used treap ds and rand function in it. for ex consider below test case given in problem also:
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8
0 5 7 14
1 4 8
correct ans
80
508
but on doing same 4-5 times mostly ans gets changed and it shows
80
494
I have just begin with treaps and unable to identify the bug . (please ignore reverse function in my code)
please help @galencolin @ssjgz @everule1

2

(!)

Having said that, with the test input you’ve given, I always get:

80
508

so far. The debug flags don’t raise any Undefined Behaviour, though this doesn’t necessarily mean there isn’t any.

Edit:

Aha - just saw a:

80
494

Edit2:

Seeding srand with the same value seems to make it always output the same thing, for me - I can’t yet see any indication that the difference in output is due to anything but the use of rand().

1 Like
3

yes please help

4

Er … stop throwing in random numbers if you want the same output every time … ? I’m not sure what you want from us, here XD

2 Likes
5

but in treaps the priorities of nodes are generated randomly only and it should not change the output anyway .also its showing wrong ans and maybe this is the reason
correct me if i am wrong .

6

Try it again, replacing:

srand(time(NULL));

with

srand(5);

NB: I’ve never heard of treaps, which is why I was so utterly confused - looking into them now :slight_smile:

2 Likes
7

thanks , now it is not giving different answers but i am unable to understand the reason of it.
can u tell me the what differnce it makes.
though still my code is getting wrong ans :pensive:
it would be helpful if u can tell the bug because it is pretty standard question but still gives wrong ans
edit still i got a 494

8

Giving it a fixed seed just makes sure it generates an identical sequence of random numbers each time, and so should make your program deterministic (assuming there’s no other sources of non-determinism in your code).

I’ve no idea what the bug is - why don’t you write a brute force solution and random testcase generator and try and find the smallest failing testcase (i.e. where the brute force solution doesn’t match your current solution) that you can, and work from there?

Or just use a segment three, like everyone else? :slight_smile:

2 Likes
9

Or just use a segment three, like everyone else

Blockquote
yeah i could do that but i was trying to implement lazy propagation using treaps as they have other functionalities also,though i am unable to do it.Also from where i read it, there only was the question for practice so i thougt to give it a try.if u find the bug please tell.
thanks anyways

1 Like