MINSUBAR - Editorial

Anyone who codes in java can implement the solution given in editorial using TreeMap.

Refer my code
https://www.codechef.com/viewsolution/18603460

@vijju123, the value of “d” doesn’t matter. Let LHS = 3 - d. we want to want LHS >= something. So, if something = 9 satisfies it, so does 7. After this try to see the construction of temp array for example in the editorial. Then things would be clear.

1 Like

Oh…I was taking 9 in LHS instead of taking it in “something”. Thanks. I will re-read,re-check and re-analyse tomorrow morning and get back to you :slight_smile:

1 Like

@bilalakil check this input :

2

5 5

1 2 3 1 -5

6 6

-1 -2 -3 3 3 -5

your output:
2
-1

correct output:
2
2

@beginner_1111
Can you tell why my solution gives WA.It is giving same ans for above input

Solution Link :
https://www.codechef.com/viewsolution/16654650

Your solution gives “-1” for

1

5 4

-1 1 1 1 1

but the right answer is 4.

1 Like

thanks for test case

please reply!

Divide and Conquer

1 Like

@ksmukta, in this problem we can’t apply binary or ternary search on the prefix array directly as it doesn’t follow the corresponding properties. One way is to do binary search with segment trees which will also pass but it is theoretically slower. Thus, we tried to see if we can deduce something about the array so that if we get an answer for some index, we could try and reduce something about other indices. These type of observations sometimes leads us to building some array (here called the temporary array) and also reduce complexity as well in some cases.

Thank you @beginner_1111 :slight_smile: Much appreciated!