Did anyone solve and can u share your approach ?
1 Like
read the editorial but unable to understand the code in the editorial .could u explain it?
1 Like
hello @beginner_11111
first of all thanks for sharing this problem learn a lot! 
code : https://ideone.com/5nSRUd
At first we have to think of the valid combinations of animals that reside in the van together. It’s pretty easy to see that the only two valid combinations are (E, C) and (D, M).
So, we will simply break the given set of animals into two set : one containing all the EC pairs and othe with DM.
Now, see we have m zoos and what i have done is find the maximum possible animal that can be transported if we end at index j for every (1<=j<=m) (dp array) and then simply iterate over the indices and build my answer array.
Now, to calculate that dp array we have to make a little observation. suppose there is a pair which ends at that index then what is the best possible answer if we include that pair(as we are interested in finding the best we can get by ending at that index so, atleast one pair should be there such that end_position of that is ‘j’). In this case the answer is (dp[k] + number of pairs of that type in range [k, j]) where 1 <= k <= start_index_of_that_pair. Why? at first think of the upper_bound of k :as we are taking the current_pair into out answer so, we have to start atleast from start_index of that pair and also make sure of the fact that in this range we consider only pairs of a single group(EC or MD) and then simply add the best possible answer upto the last index(previously calculated). Do this for all such pairs that ends at ‘j’.
That’s it if we implement it in brute way we will score 30%. For, 100 we have to speed up the process : " (dp[k] + number of pairs of that type in range [k, j]) where 1 <= k <= start_index_of_that_pair" !
The expensive part is calculating : number of pairs of that type in range [k, j]. as the dp part will be a constant for all the indexes!
For this we have to make another little observation : what happen if we add a pair? Number of pairs of that type for all the positions before start_Index will increment by 1(as if we start before that index and want to calculate number of pairs for that type then this pair definitely adds to our answer) and if we store the dp for an index and then increment that part by 1 then what we have to do is simply find the maximum of all the values. That is we have to perform range_updates and range_max_query which can easily be done with help of segment trees with lazy prop!
Hope this helps! If you still have doubts feel free to ask
1 Like
@pk301 could u please tell y are u doing s1->update(0, m, 0, 1, p.first, 1); when the source destination is p.first . should n’t we do update(0,m,0,p.first,destination,1) because we carry this animal from p.first to its destination?
by the way what is the compare function doing?
“Number of pairs of that type for all the positions before start_Index will increment by 1” see when we are introducing a new pair then it will change the answer(of the expensive part) of all the positions before startIndex by 1 as when we start from a index before startIndex then we have that newly introduced pair in our answer.
If you still have doubt feel free
i write compare function just to make sure of the fact that the pair with same end_index will be together and in sorted manner and for all that pair with same end_index i keep the pairs with greatest startIndex first because when this pair is introduced it will change the answer of all the position before it’s startIndex so, before introducing any pair with lower startIndex we must make sure that this pair will intoduced first!
You can skip this priority_queue implementation by just sorting the pairs in the same way!
1 Like
Can you explain the partial points solution of O(n^2) why is it necessary to go from right to left while choosing animals ?