Can anyone please tell me what is “dnc” in the editorialist solution?
@likecs
Could you please give the intuition behind building the temporary array. How you thought of building the array in such a way?
ksmukta ,temporary array is nothing but a map only in which we are having record of previous prefix array …they are sorted …by value and also by index for closeness so as to search for “p[j]” which is <=p[i]-d
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.
My solution is giving WA. Can somebody help me figure out what is wrong in my code?
Link: https://www.codechef.com/viewsolution/16689042
My prefix array is built in such a way that it will be in increasing order of both the prefix sum and indices.
Much appreciated!Anyone who codes in java can implement the solution given in editorial using TreeMap.
Refer my code
https://www.codechef.com/viewsolution/18603460