Problem Link : https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_d
Can someone please help me with the solution of the above problem?
My idea was to inverse the problem, so instead of calculating non overlapping configurations we can calculate total number of overlapping configurations and subtract it from total possible combinations of placing red & blue squares in a given area. Calculating total combinations is trivial. But I couldn't figure out how to calculate the overlapping combinations (I tried fixing square A and then calculate how to place B such that it strictly overlaps). But couldn't handle multiple cases (both squares needs to be inside the square area and how to avoid double counting etc). Thought some inclusion-exclusion could be used. But I am stuck now and not able to figure it out.
Solution from top rank contestant : https://atcoder.jp/contests/hhkb2020/submissions/17295052
Seems like a pretty straight forward solution but not able to understand. Can someone please help?
Found this solution : https://blog.csdn.net/justidle/article/details/109024249
Google translate doesn't work that well and I didn't get it. But perhaps others can check it out. Would be glad if someone could help with the solution.
Well, you missed another hint. To have overlapping squares. You need overlapping in both x axis and y axis. Thus you can transform the problem into finding overlapping lines. Let, $$$X$$$ be the number of overlapping lines. Ans is simple $$$X^2$$$.
How to count overlapping of lines. WLOG $$$A >= B$$$. Two cases.
1. $$$B$$$ is completely inside $$$A$$$.
2. $$$B$$$ is not completely inside $$$A$$$.
Calculating these two things is trivial.
Thank you. But I am not able to wrap my head around it. What do you mean by overlapping lines exactly? Sorry, but can you please elaborate your solution a bit more?
Let's say 2 lines be in parallel to x-axis denoted by endpoints $$$(x1, y1), (x2, y1)$$$ and $$$(x3, y2), (x4, y2)$$$. They are overlapping in x-axis if $$$max(x1, x3) < min(x2, x4)$$$
There are 3 cases for the orientation of the 2 squares:
Case 1: Both their x and y values are disjoint. We can represent the intervals of x value each square takes on each as chunks. We basically have a chunk of length $$$A$$$, a chunk of length $$$B$$$, and $$$N-A-B$$$ other "chunks" of length 1. Using stars and bars, there are $$$(N-A-B+2)*(N-A-B+1)$$$ ways to place these chunks. We do the same for y, counting the number of ways to position 2 disjoint chunks of length $$$A$$$ and $$$B$$$. Each set of x and y orientations maps to a unique orientation of the squares. Therefore, there are a total of $$$[(N-A-B+2)*(N-A-B+1)]^2$$$ orientations.
Case 2: Their x's are disjoint but their y values overlap. We can use the same "chunk" technique to construct the x orientations of the squares; there are $$$(N-A-B+2)*(N-A-B+1)$$$ ways to do so. The y-intervals of the squares, however, can be placed in any way such that they are not disjoint (#total-#disjoint). There are $$$N-A+1$$$ possible locations for the y-interval of the first square, and $$$N-B+1$$$ for the second, giving $$$(N-A+1)(N-B+1)$$$ total possible y-orientations. The number of valid y positionings is thus $$$(N-A+1)(N-B+1)-(N-A-B+2)*(N-A-B+1)$$$. Accounting for both x and y, we count $$$(N-A-B+2)*(N-A-B+1)*[(N-A+1)(N-B+1)-(N-A-B+2)*(N-A-B+1)]$$$ ways to construct this case.
Case 3: Their y's are disjoint but their x values overlap. This is symmetric to Case 2, so we get another $$$(N-A-B+2)*(N-A-B+1)*[(N-A+1)(N-B+1)-(N-A-B+2)*(N-A-B+1)]$$$ ways.
Add these, simplify if you want, and you get the answer. Alternatively, you can use complementary counting.
Really neat and easy to understand. Thanks. :)