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?
1 Like
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.
1 Like
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.
1 Like