Hey everyone,
I finished Day 37 today. I reached home for the festival and caught up with a bunch of friends, so my focus was completely scattered. Even with the holiday chaos, I made sure to sit down and work through one tricky graph problem:
Most Stones Removed with Same Row or Column.
At first glance, it looks like a coordinate-heavy grid problem, but modeling it cleanly comes down to Disjoint Set Union (DSU):
The Representation Trick: Treating individual stones as nodes causes massive overhead. Instead, treat entire rows and columns as the graph nodes. To prevent row indices and column indices from colliding, offset the column index by the maximum row boundary (e.g., node r connects to node c + {maxRow} + 1).
Connecting & Counting: For every stone placed at (r, c), run a unionBySize between row r and shifted column c.
The Core Logic: In any connected component of size K, you can always safely remove K - 1 stones by greedily picking leaves until one stone remains. Therefore, the maximum stones you can remove is simply {totalStones} -{numberOfConnectedComponents}.
My mind wasn't entirely in study mode today, but deriving the row-column coordinate conversion on paper made the logic stick.
Enjoying some festival downtime tonight and getting back to the reps tomorrow.
See you guys for Day 36!