MINSUBAR - Editorial

I tried the 1st approach given in the editorial but still getting wrong answer on submission!
@likecs @vijju123 @scaly_raptor I have tried all above test cases given in this thread also and getting correct…
Link to my solution. Any test case giving wrong ans or fault in my approach is welcome!!!

I used SQRT decomposition.

First, I calculated the prefix sums and stored the largest one for each block. Then, for each starting subarray index, I checked if there is a good ending index in the same block (pref[j]-pref[i]>=d), if not, I looped through blocks until I found one that had max_bl_pref[bl_j]-pref[i]>=d. If I found one, I had to loop through the individual elements of that block to find the best answer.

1 Like

I tried with 2 pointers. not sure why this gives WA. It passes all cases mentioned above.
https://www.codechef.com/viewsolution/16665379

I have a solution that is like the moving window methods that others have been trying to use. We have to be careful though. The moving-window algorithms on geeksforgeeks are for arrays with positive values. That is extremely important because it means that the sum of all previous values is a monotone increasing sequence. That is not the case here.

To make such a method work we need to create an auxiliary sequence (the same that is used in the editorial). The trick is that the auxiliary sequence needs to be non decreasing. We can do that by removing terms. Each time we would add a term to this auxiliary list we first remove terms from the end until the last term is smaller than the new term. In that way we ensure that the sequence is always monotone increasing. Since we are deleting terms we will also need to keep track of the index of each value in this list.

In total we will add N terms to this auxiliary list. This should give us both time and space complexities of O(N). I have really just eliminated the need for the bisection that was used in the editorial.

Python: CodeChef: Practical coding for everyone

C++: CodeChef: Practical coding for everyone

5 Likes

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