Can Someone tell me the logic for this M-Code problem

https://www.codechef.com/MCOD2020/problems/MBARS/
why they r dividing the array into 2 halves

If the question would had constraints like N <= 16 then we could have tried a very simple approach of trying out every subset of the array A and check if the sum of the subset lies in the range [L,H] but since the question has N <= 32… So now we need to use an approach , the idea of which revolves pretty much around the previous approach for N <= 16…

Now the approach is to divide the given array into two halves of size N/2…consider I sort the array and name the array with elements [1,N/2] as low and with elements [N/2 + 1,N] as high… then we find out sum of every subset for the two arrays and store them… Now you can easily answer the question of finding combinations for the two smaller array low and high (just iterate over the sum arrays)… But to answer our original question we need to find out the cases when we pick some elements from the left array and some from the right array and find out that the sum of this subset lies in the range [L,H]… this i have done using the lower bound and upper_bound function… The link to my solution is - https://www.codechef.com/viewsolution/35741610

Let me know if you got the idea or I need to elaborate it more :slight_smile:

3 Likes

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

i exactly did what you did
why im getting WA

Overflow for min_req,max_req and count…

i dont get it

i made very little modifications to your code and then also im getting WA
https://www.codechef.com/viewsolution/35759945

in your code just change max_req, min_req and count variables used to long long int and you will get AC…

In my code I had intentionally pushed 0 to sum1 and sum2 to counter the cases in which we take empty subset from left side and take a subset whose sum lies in range [L,H] from right side(same goes for vice versa case)… since you have not pushed those 0s…this is why the answer you are getting is wrong