EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2) Editorial [2002A — Distanced Coloring](https://mirror.codeforces.com/contest/2002/problem/A)
idea & solution: [user:xcyle,2024-08-12]
<spoiler summary="Hint 1">
Consider the case with $n=m=k$.
</spoiler>
<spoiler summary="Hint 2">
Generalize the solution for all $n,m,k$.
</spoiler>
<spoiler summary="Tutorial">
It can be shown that for any $k\times k$ subgrid, the colors we use must be pairwise distinct. Thus, we have an lower bound of $\min(n,k)\cdot\min(m,k)$. We can show that this lower bound is indeed achievable by coloring the upper-left $\min(n,k)\cdot\min(m,k)$ subgrid with distinct colors, and copy-pasting it to fill the rest of the grid.
Time complexity: $O(1)$.
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int t, n, m, k;
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &m, &k);
printf("%d\n", min(n, k)*min(m, k));
}
return 0;
}
~~~~~
</spoiler>
[2...
Full text and comments »
