HBIRD - Editorial

Any idea why this fails for the small cases?

I am storing for each i, birds[i] = number of birds with hunger = i. Then a linear iteration over the sorted queries to get the answer.

Exactly the same solution as the editorial. You may refer to the solution here . You may remove the comments to check the execution at various steps.

Happy coding :slight_smile:

N^2*M for the case N=M=335 will come out something around 10^8. How is this computable under given time constraints?

@yougaindra… u dont’t have to store 2e8 triangles…the largest possible triangle is 335 units high,with 335 units base width & has 335 units of diagonal length. It contains about (1+2+3…+335) cells which is about 56280 cells in total.Since the largest value any cell can hold is 50…that gives the largest sum to be about 50 * 56280 = 2814000 (less than 3 *10^6) and the smallest sum would be 0. Creating an array of that length is feasible also doing Binary search over this array can be done under given time constraint.

(If u find it helpful do upvote)

Actually the test cases were weak according to me. Initially I was getting SIGABRT error due to using large memory. (CodeChef: Practical coding for everyone). But changing some parameters on the variable “limit” passed the solution easily for 100 points. Here is the code (CodeChef: Practical coding for everyone).

PS: Though I later managed to get the actual solution as explained in the editorial.

Why should we perform binary search in the end? We could check for the largest index where pi <= G in a single iteration.

grid is NM so we can say there are n horizontal line and m vertical line so number of rectangle is NC2MC2 which n^2m^2 and each rectangle will produce 4 distinct right angle triangle where is flaw in my logic as I get order O(N^2M^2)
@aky1994 @likecs

can someone provide me with some test cases to check the ans!!! why codechef dont provide test cases file!!
it is really annoying!

@aky1994 The total number of birds wont exceed 8e7 which is easily computable within 2 seconds in O(n * m * min ( n , m) ) time complexity.

Enumerating even up to 2e8 triangles is doable within 2 seconds as long as you enumerate efficiently.

But How can we store 2e8 triangles?

You don’t need to store the triangles. You only need to compute the frequency distribution of the sums of the triangles, which can be stored in an array of size H_maxNM < 6 million.

But if you compute frequency distribution in an array why do you need to sort them as mentioned in editorial because this array would already be sorted?

Yes, the array would already be sorted so no need for a separate sorting step. “sorting” is just mentioned in the editorial to emphasize that we need the sums sorted.

1 Like

Also in editorialist’s solution prefix vector ‘ans’ contains sum(ct) elements and from calculations above sum(ct) is 2e18.

in editorialist’s solution prefix vector ‘ans’ contains sum(ct) elements and from calculations above sum(ct) is 2e18, where ct is array containing frequency of different triangles.

No of queries is large - 10**5. That would tle

@yougaindra Well by largest sum I meant the sum of values of all the cells in the largest possible triangle and not the cumulative sum itself.

also the array bound that I had used in my code was 3 *10^6 which worked well.Had this not been the upper limit then I would have got SIGSEGV error.

So apparently you need to store 2e8 values anyway because of ‘ans’. But since CodeChef accepts it, it means we don’t need to worry any more. Also, note that 2e8 is a very loose bound, and most likely you’ll actually need much less.

1 Like

By the way, there’s still a way to not store 2e8 sums but at the cost of making “binary search” more complicated.