I really didn’t understand it. I talked to about 10 people and most of them got 1-6 test cases from just bashing after thinking for a long time. One of my friends icped and said they used segtrees, and someone else on reddit said they used Binary Indexed Trees, (i think they’re kinda similar?) but I thought those were gold algorithms.
An observation I had during a contest is that if there is a cow at (a, b) and a cow at (c, d), if there was another cow with x value between a and c and y value between b and d that cow would block off possible subsets containing them. This felt like a useful observation, but I couldn’t figure out the math to go with it, and I was wondering if that was possibly the solution?
I guess that’s part of the solution? Maybe try iterating through all combinations of x-values (like two invisible lines) and see what you can come up with.
For this problem, I iterated over all possible pairs of x-values for the vertical lines of the fence and then found all the possible subsets that you could form with different choices for the horizontal fences. In order to avoid overcounting, you make sure that you always include the two points that lie on your vertical edges lines. If there are a points above the higher edge point and b points below the lower one, there should be (a+1)(b+1) subsets possible, and then use prefix sums to calculate a and b efficiently and solve. This solution probably isn’t that clear, but I’m sure the solution on the USACO website is better and more understandable.