wrong answer in matchstick problem

i am getting wrong answer for this question http://www.codechef.com/problems/MSTICK/ . please help in correcting my algorithm, i cant find any error http://www.codechef.com/viewsolution/2308249

you have considered that all queries are dependent on the previous queries. however they are independent of each other. you have to solve each test case considering the starting state given in the question.As each time you modify the input array b , you get wrong answer for all queries after the first one as time required for burning changes for subsequent queries . also you will require advanced data structures for fast querying as O(n) solution for each test case will give TLE.

1 Like

Could anyone point out what’s wrong in my code its working fine on all the test cases but giving WA on submission??

thanks for finding the error. for this question see this accepted solution http://www.codechef.com/viewsolution/2193135
i think runtime of this algorithm is O(nlgn) which is greater than O(n), then how it is accepted. i think divide and conquer approach is applied here.

O(n lgn) is the accepted time limit. what i meant is you cannot use O(n) querying time in each test case. you need to use O(n lgn) pre-processing at the start to speed up querying min and max in each test case.the queries can be done in O(lg n)(setter’s soln) or O(1) time- (tester’s soln)

ok i got it. building the segment tree takes O(nlgn) and total querying time is O(Q(logn+k)).mine querying time was O(Qn). thanks