MSTICK - Editorial

editorial
, , , ,
41

Nice :slight_smile:
I think test cases can be prepared to fail this solution :slight_smile:
But I do appreciate the intelligence used in the solution.

42

  1. Strange that. Not sure why that happened. May be your code was just under time limit and using vector took little extra to make it TLE.

  2. You can use single tree, but with addition data that is the tree will have two data in each node - max, min both. You will need to define a struct to accomplish this. Although it creates one tree but the complexity of code is not much simplified, I think.

p.S. Happy to know that you liked the problem :slight_smile:

1 Like
43

@mkagenius ok got it… using stuct yeah that had to be obvious! :stuck_out_tongue:
but if someone can still help me with my first doubt! :slight_smile:

2 Likes
44

In this question you have to answer Q queries. So, surely you have to find all four minimum & maximums for different ranges every time for every query. So, now if you have answer a single query you have to run your program of O(N) complexity all four times. Then if you have to answer Q query then complexity will be O(NQ). But using this algorithm you can answer a query in O(log N) time which is smaller than O(N). All what is required is that you have to preprocess the array into a segment tree which takes O(N) time. This gives a <O(N), O(logN)> approach which is way faster than O(NQ).

45

Umm, a segment tree takes linear memory while a sparse table takes NlogN space. These are also the bounds for preprocessing time. Sparse table’s advantage is that it answers queries in O(1) rather than O(logN).

46

i too did this problem referring to topcoder tuts. i had the same question as you, and answer is pretty straight forward. ie If someone gave you bubble sort algorithm to sort in ascending order and then told you to modify it for descending order sorting,what changes will you make? That’s right, that’s the answer. just play with greater than/less than signs :slight_smile: you can check my solution, i have done same approach as you are talking about and also have included topcoder algo in comments. AC code’s link is there 2 questions above yours. PS- there might be better approach bt mine answers ur doubt:)

4 Likes
47

haha well explained :stuck_out_tongue:

48

I’ve an exactly similar code which got AC: CodeChef: Practical coding for everyone

The only difference is printing of decimal simply based on Modulo 2 for the diff instead of using “double” precision. Wonder if the precision of double caught up on you given that bi’s could be of the order of 10^8?

49

@sunny_patel: It is so because you are passing the “vector” by value and not by reference (and thus triggering the “copy” on every call). Try changing the argument to initializeA, initializeB to “vector const &” instead.

1 Like
50

That is true. Double precision should give up to 15 digits precision atleast. Infact your solution gives AC to me… :slight_smile: CodeChef: Practical coding for everyone [ used C++ 4.3.2 with include for cmath]

51

Err… Ain’t it correct? In case2, ‘3’ gets burned out from one side and then ‘12’ burns out from the other (only) side again, taking 3+12 = 15? (similarly 14 for case3)

1 Like
52

Just change float to double in line 117 to get AC. :slight_smile:

2 Likes
53

Thanks a lot ! Finally got it accepted :slight_smile:

54

Or you can just change the sign of the data items and use the same code (minimum) for both. My solution is based upon this trick.

55

i answered in the other topic. your solution’s worst case is when the input sequence of sticks is sorted.

56

Showing invalid Solution ID…

57

The above formula is correct. Analyze.

58

Got the reason for runtime error. But still I have doubt about how the solutions using two arrays of size 10000 are getting accepted.

59

Finally accepted.! But still have the above doubt.

60

I think it returns wrong answer for

6
3 4 5 1 2 3
3
0 0
1 2
0 2

last test is 6, not 7 as your code returns.

1 Like