Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Forget the current layout. Since Bob can rearrange the whole board, only the counts of colors matter. The grid’s initial rows are mostly a red herring.
If some color appears too many times, the other colors are the only things that can “break” rows and columns of that color. Ask: how many non- candies are needed so that no row is entirely color ?
To stop a color from forming a monochromatic row, every row must contain at least one candy that is not . That already needs at least non- candies.
If the most frequent color appears times, then the number of candies not of that color is . A valid arrangement can exist only if
So we need .
The whole solution is just: count the maximum frequency . Print YES iff . For construction intuition, put one non-dominant candy in each row, then fill the remaining cells however; every row is broken, and every column automatically has at least one row whose cell is not forced into being all one color. For , the inequality correctly says NO.
Because we may rearrange the board arbitrarily, the original positions mean absolutely nothing. Toss that layout in the trash; only the multiset of colors matters.
Suppose color appears times. If a row becomes entirely color , that row is bad. To prevent this from happening for the most frequent color, every row must contain at least one candy whose color is not .
There are exactly
candies whose color is not . Since there are rows, we need at least one such candy in every row, so a necessary condition is
Equivalently,
If this fails for the most frequent color, then by pigeonhole principle some row will contain only that color no matter how we rearrange. Game over.
Now assume every color appears at most
Let be a most frequent color. Then there are at least candies not equal to . Put one non- candy in each row. Now no row can be entirely color .
Could some row be entirely another color ? No, because appears no more often than , and the same bound gives enough room to avoid forcing a full row of as well. More directly, the only possible obstruction is a color appearing so often that there are fewer than other candies available to break all rows. Since the maximum frequency satisfies the bound, no color has that obstruction.
Columns are not a separate monster hiding under the bed. The same argument works for columns too: for any color , avoiding a monochromatic column of only requires at least one non- candy in each of the columns, which is possible under the exact same bound.
So the condition is both necessary and sufficient:
For , this says , which is false, so the answer is correctly NO: a row/column is always monochromatic. Brutal, but fair.
For each test case:
YES iffEach test case reads numbers and does constant expected-time hash table updates, so the complexity is
per test case, with memory
in the worst case for distinct colors.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
unordered_map<int, int> freq;
int best = 0;
for (int i = 0; i < n * n; i++) {
int x;
cin >> x;
best = max(best, ++freq[x]);
}
cout << (best <= n * n - n ? "YES" : "NO") << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
unordered_map<int, int> freq;
int best = 0;
for (int i = 0; i < n * n; i++) {
int x;
cin >> x;
best = max(best, ++freq[x]);
}
cout << (best <= n * n - n ? "YES" : "NO") << '\n';
}
return 0;
}