doesn’t it ever happen to you that you’re wandering around aimlessly at home, open a drawer looking for something to eat, find a bag of avocados and end up coming up with a problem for the OCI regionals? no? …

i haven’t set that many problems so far, but i think the way i came up with my very first one was kind of funny.

i had just been to the farmers market and bought a bag of avocados. when i opened the drawer a couple of days later, i saw that, despite having bought them at the same ripeness level, they looked quite different. that’s when i thought, some avocados do ripen faster than others and that maybe, and only maybe, their ripeness could be modeled as a linear function of time.

thats when i came up with the following idea:

You have $N$ avocados whose ripeness level starts from 0 at $t = 0$ and you know their ripening rate $A_i$. An avocado can be eaten if its ripeness level is at least $x_{min}$. You will be given $Q$ queries of the form

$\text{How many avocados can you eat by time } t_i \text{?}$

the solution was fairly straightforward. since all avocados started at $0$ you could sort the slopes and do binary search. after a while, we decided to add another constraint $x_{max}$ so you’d need to binary search twice, also because it makes sense that avocados eventually spoil.

there was also a way to solve it by sorting the queries and using two pointers, but the intended solution i had in mind was binary searching.

anyway, i don’t think its a wow problem,but i still have a soft spot for it, since it was my first one.

here’s the problem if you want to check it out :>