Atcoder HHKB Programming Contest 2020 Problem Squares [Need help]

Revision en1, by yesnomaybe, 2020-10-12 10:08:12

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English yesnomaybe 2020-10-12 10:08:12 1093 Initial revision (published)