AtCoder Beginner Contest 275 Announcement

AtCoder Beginner Contest 275 Announcement

6 hours ago, # | ← Rev. 2 →   +24 Me: Problem C takes more time than E and F combined. Is there an elegant way to solve C?

• 6 hours ago, # ^ | I found C a lot harder than E,F as well, so I'm also wondering :)

• 6 hours ago, # ^ | I burned some time looking for one but ended up brute forcing on a first edge and early-outing if building the square out from it failed (ccw? either out of bounds or no #)... accounting for duplicates: each square was recorded as the sorted tuple of its corners (hashable for set in python). For a full grid, I got 540... so, it was at least pre-bake-able, but that's probably not 'elegant' in any good sense.

• 6 hours ago, # ^ | You can store all pawns and go through all possible 4 pawns('#') and check whether you can form a square using these 4 pawns or not. Condition to check whether we can form a square:- A). The set of distances for each point to its 3 neighbors must be the same. One possible example:- B). The 2 shortest distances among 3 distances must be the same ( In the above example it is 1 ). My submission:- https://atcoder.jp/contests/abc275/submissions/36069709

• 4 minutes ago, # ^ | Iterate over all the pairs of squares, consider this pair as a side and rotate this 90 degrees (counterclockwise, to do this : note that the slopes of perpendicular lines multiply to -1. so we need to swap dx and dy, multiply dx by -1) twice to get all four coordinates of the square. If all four coordinates have s[i][j] = '#', increase the answer by 1. Final answer will be ans/4 since all 4 sides generate the same square by counterclockwise rotation. Code. I learned this trick from Heno239's submission.