For the Dec 2020 Silver Problem 2, Rectangular Pasture, I have an O(n^4) algorithm which solves only the first few test cases. I can’t find any insights to speed it up. Could anyone give me a hint? Like, before I look at the official solution I really want to have the key insight myself but I need a hint.
Say you had two boundaries. How would you determine how many subsets of cows can be enclosable with fences that stick to those two boundaries?
thank you! wow it only took an hour to get a hint. what a lovely community you are. I will think about this.
I suggest you think about how you would define a subset if say, you fix the boundaries like @SansPapyrus683 said.
I don’t think it was meant to be that way(?)
Please disregard the flag (above). I misunderstood the comment.
Many forums on the internet are low activity or low quality of posting. I’m new to this forum so I didn’t have much hope I would get a good hint at all, let alone so quickly. I see that I need to recalibrate my expectations - a wonderful forum.
Yeah, sorry for the misunderstanding. My bad. The way you phrased the comment usually implies sarcasm.
It was a slight manic way to phrase the comment, so my bad too.
Turns out I had already understood the implications of counting cows that fall within two parallel boundary lines. I knew that there were O(n^2) steps needed to find every pair of boundary lines. I also knew that I was going to need to count points positioned in rectangular regions and choose pairs of coordinates, but I only knew an O(n^2) way to do that. So I ended up looking at the solution and learned that there is an O(1) way to count or sum items in sub-rectangles. I won’t say it here to avoid spoilers but I’m sure y’all know what I’m talking about.