MATCHSTICK WA

general
1

Hey guys was trying to solve http://www.codechef.com/problems/MSTICK/ by using segment trees but everytime WA comes up …heres my code http://www.codechef.com/viewsolution/3653425 please help…:frowning:

2

Comments and better variable names make it much easier for others to help you.

3

according to u i have the above commented the above code plzzz do reply http://www.codechef.com/viewsolution/3655624

4

hey yr plzzz reply has been stuck for past 4 days unable to find the bug…:frowning:

5

any body plzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

6

???/

7

Your code is perfect but there is one basic error of floating point numbers having less precision can give approximate/nearby values for large input hence you should store integer values in the segment tree until and unless required. There was one more error of initialization in your code due to which it was giving wrong answer. The initialization of the variable m1 wasn’t done which I initialized to a negative value and hence it got accepted. The solution Id of your code is

http://www.codechef.com/viewplaintext/3661719

You should try debugging the code by writing a brute force method of the solution and taking a difference of the output obtained by both of your solutions.

2 Likes
8

Hmm, I did notice the same thing yesterday and resubmitted the code with a proper initialization, which raises another question - why it did not get accepted. See the code here: http://www.codechef.com/viewsolution/3660162. Heh, :)!

9

OK, sometimes it is a good thing to go through the related questions. As I replied to @vermashubhang’s comment I also initialized the variable (m1) you missed in your original solution - 3653425 (the not commented one) - but that was just 1 out of 2 mistakes and alone was not enough to get AC. Obeying the instructions from this answer, i.e. replacing float’s with double’s, made the rejected solution got AC: http://www.codechef.com/viewsolution/3661794.

PS: Thank you for this question, because I learned a lot today :).

1 Like
10

@monkeybrain Yeah! you are right I actually changed the query output values in the segment tree to integer and got it accepted. The actual error was the error of precision which I didn’t notice. Thanks…

11

floating point precision i did notice that part but was missing the init of m1 …thannx a lot for ur reply…was a grt learning days with mstick

12

@wonder Please accept the solution if you are satisfied so that the question could be closed.

13

yeah…sure enough…:slight_smile:
I did got AC

14

@wonder Please accept the answer on the forum.