yesnomaybe's blog

By yesnomaybe, history, 16 months ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
16 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
16 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay, I think I can explain... One thing to notice that if two square overlaps then there length and breadth of one rectangle must cross the breadth and length of the other rectangle so we need to discard those and we should count only the where the dimension don't overlap as mentioned i.e solution of the integral equation above which is shows the conditions of non-overlapping squares and subtract those which were counted twice due to rotations if u need further explanation u can ask

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)$$$

»
16 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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.