MINSUBAR - Editorial

can you please explain the “editorialist approach” a little more. I didn’t get it. Why does we are storing prefix of right and suffix of left?

1 Like

Basicslly … the zest of the question is clear

task one:->you have to maintain a prefix array.

task two:->iterate over prefix array,for each item you have to find an element (>=prefix[i]-d if looking forward) or (<=prefix[i]-d if looking backward) of the item being processed (and closest also)…this can be done using expensive data structures for time optimality like segment trees , priority queues,sqrt decomposition technique,or maintaining maps etc…

task three:->find the optimal answer

for more clarity refer : 12697 — Minimal Subarray Length - Codeforces

i have a doubt in the first approach given above…

in the test case-

1

6 0

-1 -1 -1 0 -1 -1

the final array of pairs on which binary search has to be applied ends up being:

({-5,5})(as per your approach)

this automatically diminishes the chances of getting any sub string ending with 1, 2, 3 or 4 as its ending
index while in the given test case answer should be 3. please help.

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?

you can check my code here: 1cSFwO - Online C++0x Compiler & Debugging Tool - Ideone.com

very easy map implementation

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

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.

Can someone please tell why I am getting WA

https://www.codechef.com/viewsolution/16694570

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!