We will discuss the solution to Mundane Square from AIO 2026. This is a very difficult problem designed to challenge the very top students in Australia, so do not worry if you are struggling to understand the solution!
Before we look at the subtasks, there are two simple checks that will catch some of the impossible cases.
Each row must contain exactly one 1 and otherwise only 0s. So we just need to decide which column each row's 1 goes in. Column j needs exactly Cj of these 1s.
If the column targets add to N, we can put the 1s of the first C1 rows in column 1, the 1s of the next C2 rows in column 2, and so on. For example, if N = 3 and the column targets are 2, 0, 1, we can construct:
| 1 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 0 | 1 |
If the column targets don't add to N, then the first check from the top of this page tells us the answer is NO. This takes O(N2) time, including printing the square.
The smallness rule means that N ≤ 100 and every target is at most 100. Since K is much larger than any target, the limit on individual cells will never get in our way. So once the row and column targets have the same sum, we should be able to fill the square somehow.
We fill the square one row at a time, from left to right, while storing the amount each column still needs. For each cell, we put in as much as we can: the minimum of the amount the row still needs and the amount the column still needs. We then subtract this value from both remaining amounts.
For example, with row targets 3, 2 and column targets 1, 4:
| 1 | 2 |
| 0 | 2 |
Why does this always work? Before each row, the columns still need a total that is equal to the total of all the rows we haven't filled yet (because the sums started equal and we subtract the same amount from both). In particular, the columns still need at least as much as the current row, so we can always finish filling the row. Once every row is finished, the columns must also be finished. The time complexity is O(N2).
It might be tempting to extend this solution to the remaining subtasks by also taking the minimum with K. However, that does not always work! For example, consider K = 1, row targets 1, 2, and column targets 1, 2. Filling the top-left cell with 1 means the first row is finished and the first column is finished. But now the second row needs 2, and the only column that still needs anything is column 2, which can only take 1 from this row. We get stuck, even though the following valid square exists:
| 0 | 1 |
| 1 | 1 |
So when K is small, we need to be much more careful about where we put things.
We will still fill the square one row at a time, but we must choose the columns more carefully. A row with target Ri needs a 1 in exactly Ri different columns. Which columns should we choose?
Let's think about the example above. Column 2 needs a total of 2, and there are only 2 rows. So column 2 needs a 1 in every row, and if we skip it in the first row it is impossible to finish. More generally, columns that still need a lot have the least room for mistakes, because there are only a limited number of rows left in which to help them. This suggests a greedy idea: in each row, put the 1s in the columns with the largest remaining targets.
Let's try this on sample input 2, where K = 1, the row targets are 2, 3, 2, 3 and the column targets are 2, 2, 3, 3. When columns are tied, we choose the leftmost one.
| Row | Row target | Remaining column targets before | Chosen columns | Row values | Remaining column targets after |
|---|---|---|---|---|---|
| 1 | 2 | 2, 2, 3, 3 | 3, 4 | 0 0 1 1 | 2, 2, 2, 2 |
| 2 | 3 | 2, 2, 2, 2 | 1, 2, 3 | 1 1 1 0 | 1, 1, 1, 2 |
| 3 | 2 | 1, 1, 1, 2 | 4, 1 | 1 0 0 1 | 0, 1, 1, 1 |
| 4 | 3 | 0, 1, 1, 1 | 2, 3, 4 | 0 1 1 1 | 0, 0, 0, 0 |
Every column target is reached, so this is a valid mundane square. It is different from the sample output, which is fine because any valid square is accepted.
To code this, before each row we sort the columns by their remaining targets and put 1s in the first Ri columns. If Ri > N, or one of the chosen columns has a remaining target of 0, then we get stuck and print NO. If the totals were equal and we fill every row successfully, all the column targets must also be satisfied. This takes O(N2 log N) time.
You shouldn't just trust me that this greedy idea always works. Rather than prove it here, we will prove a more general version in the next subtask that also covers this one.
When K is larger than 1, we can put several units into the same cell. We extend the previous greedy idea by placing the units of each row one at a time. Each time, we look at the columns that still need something and whose cell in the current row is still less than K. Out of these, we choose a column with the largest remaining target, add 1 to its cell, and subtract 1 from its remaining target. Once a cell reaches K, we can't use that column again in the current row.
It is important to compare the updated remaining targets after every single unit. It is tempting to instead take the largest column and fill its cell all the way up to K before moving on, but this can fail. For example, let K = 2, the row targets be 2, 4, and the column targets be 3, 3. If the first row puts 2 in either column, the remaining targets become 1, 3. The second row can only put 2 in each column, so the column with 3 can never be finished. The unit-by-unit greedy instead puts one unit in column 1 (leaving 2, 3), and then one unit in column 2 because it is now the largest (leaving 2, 2). The second row can then put 2 in each column.
The video below compares the two ideas on this example.
If the row still needs units but no column is allowed to take one, we print NO. Otherwise we continue until all rows are filled, and print the resulting square.
Why does this greedy algorithm never get stuck when a valid square exists? This is the hardest part of the problem. Try to prove it yourself before reading my proof!
We will use a type of proof called an exchange argument.
In this proof style, we start with a solution that does not match our greedy choices and show that we can change
it bit-by-bit until it does.
Suppose a valid square exists that agrees with every unit our greedy algorithm has placed so far. The greedy algorithm's next choice is to add 1 to column p of the current row. If the valid square already has at least this many units in that cell, it agrees with this choice too and there is nothing to do.
Otherwise, the valid square must put the current row's next unit in some other column, q. Let dp and dq be the remaining targets of these columns, after the units we have already placed. Column q was also allowed to take our next unit (the valid square puts another unit in that cell, so it has room and still needs something). Since the greedy algorithm picked column p, we know that dp ≥ dq.
In the valid square, column p gets no more units in the current row, so all dp of its remaining units must go in later rows. Column q gets at least one more unit in the current row, so fewer than dq of its remaining units go in later rows. So across the later rows, column p has a strictly larger total than column q. This means at least one later row must have a larger value in column p than in column q.
Now we change four cells of the valid square: in the current row, we move 1 from column q to column p, and in that later row, we move 1 from column p to column q. All the row and column sums stay the same. We also need to check that all four cells stay between 0 and K:
The changed square is still valid, and it now agrees with the greedy algorithm's next unit as well as all its earlier choices. Repeating this argument for every unit shows that the greedy algorithm never gets stuck when a valid square exists. So if it does get stuck, no valid square exists and the answer really is NO.
Let's analyse the time complexity of this solution. Let S be the sum of the row targets. We place S units, and finding the best column by looping over all the columns takes O(N) time per unit. Including creating and printing the square, the time complexity is O(NS + N2). The smallness rule gives S ≤ 10 000 and N ≤ 100, so this is fast enough to pass subtasks 1-4 for 90 points. Since subtasks 1-3 are special cases of subtask 4, we don't need to code them separately!
Below is my code in Python and C++ for this subtask. I suggest trying to code the solution yourself and only look at our code after you finish or if you get stuck.
import sys
# N is the size of the square.
N = 0
# K is the largest value allowed in a cell.
K = 0
# R and C contain the row and column targets. Note that the lists start from
# 0, and so the values are R[0] to R[N-1] and C[0] to C[N-1].
R = []
C = []
# Read the values of N, K, and the row and column targets.
N, K = map(int, input().strip().split())
R = list(map(int, input().strip().split()))
C = list(map(int, input().strip().split()))
# This function prints NO and then ends the program
def NO():
print("NO")
sys.exit(0)
# The row and column targets must have the same total
if sum(R) != sum(C):
NO()
# remaining[j] will store the amount column j still needs
remaining = C[:]
# square[i][j] will store the value in row i and column j
square = [[0] * N for i in range(N)]
# Compute the answer
for i in range(N):
# Place the units of row i one at a time
for unit in range(R[i]):
# Find the column with the largest remaining target, out of the columns
# that still need something and whose cell in this row is less than K
best = -1
for j in range(N):
if remaining[j] > 0 and square[i][j] < K:
if best == -1 or remaining[j] > remaining[best]:
best = j
if best == -1:
# There is nowhere to put this unit
NO()
square[i][best] += 1
remaining[best] -= 1
print("YES")
for row in square:
print(*row)
#include <cstdio>
#include <cstdlib> // for exit()
/* N is the size of the square. */
int N;
/* K is the largest value allowed in a cell. */
int K;
/*
* R and C contain the row and column targets. Note that the arrays start from
* 0, and so the values are R[0] to R[N-1] and C[0] to C[N-1].
*/
int R[105];
int C[105];
/* remaining[j] will store the amount column j still needs */
int remaining[105];
/* square[i][j] will store the value in row i and column j */
int square[105][105];
/* This function prints NO and then ends the program */
void NO() {
printf("NO\n");
exit(0);
}
int main(void) {
/* Read the values of N, K, and the row and column targets. */
scanf("%d%d", &N, &K);
for (int i = 0; i < N; i++) {
scanf("%d", &R[i]);
}
for (int j = 0; j < N; j++) {
scanf("%d", &C[j]);
}
/* The row and column targets must have the same total */
int row_total = 0, column_total = 0;
for (int i = 0; i < N; i++) {
row_total += R[i];
column_total += C[i];
}
if (row_total != column_total) {
NO();
}
for (int j = 0; j < N; j++) {
remaining[j] = C[j];
}
/* Compute the answer */
for (int i = 0; i < N; i++) {
// Place the units of row i one at a time
for (int unit = 0; unit < R[i]; unit++) {
// Find the column with the largest remaining target, out of the columns
// that still need something and whose cell in this row is less than K
int best = -1;
for (int j = 0; j < N; j++) {
if (remaining[j] > 0 && square[i][j] < K) {
if (best == -1 || remaining[j] > remaining[best]) {
best = j;
}
}
}
if (best == -1) {
// There is nowhere to put this unit
NO();
}
square[i][best]++;
remaining[best]--;
}
}
printf("YES\n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", square[i][j]);
}
printf("\n");
}
}
For the full problem, S can be as large as 1012, so placing units one at a time is far too slow. We will use exactly the same greedy algorithm, but place many units at once.
It helps to imagine the remaining column targets as stacks of blocks. Each time the greedy algorithm places a unit, it removes a block from a tallest stack that is still allowed. So within one row, the tallest stacks are lowered towards a common height, a bit like water draining out of a tank. The only exception is that we can remove at most K blocks from each stack during one row, so a very tall stack stops being lowered once we've taken K from it.
Let dj be column j's remaining target before the current row, and suppose we lower all the stacks to height L. From column j, this removes min(K, max(0, dj - L)) units: nothing if the stack is already no taller than L, and never more than K. Let's call the total number of units this removes F(L). We want to find the height L where F(L) matches the number of units the row needs.
Lowering the stacks to a higher L can never remove more units, so F(L) gets smaller (or stays the same) as L increases. This means we can use binary search to find the smallest height L where F(L) ≤ Ri. Before we search, we check that Ri ≤ F(0). If not, the row needs more than all of its cells can provide, so we print NO.
Once we have found L, we put min(K, max(0, dj - L)) in each cell of the row. This might place slightly fewer than Ri units, so we may need Ri - F(L) more. These are the next few units the unit-by-unit greedy would place, which come from stacks that are now exactly at height L and whose cells are still less than K. So we add 1 to that many of these columns (any of them will do, since they are tied).
Why are there always enough of these columns? If L > 0, then L being the smallest height that works means F(L-1) > Ri. The difference F(L-1) - F(L) is exactly the number of columns we can add an extra unit to, so there are more than enough. If L = 0, our check before searching means F(0) = Ri, so no extra units are needed. Since we are placing exactly the units the unit-by-unit greedy would place, the proof from subtask 4 still applies.
Let's try an example. Suppose the remaining targets are 3, 3, K = 2, and the row needs 3 units.
Here is a bigger example, with remaining targets 6, 4, 2, 1, K = 3, and a row that needs 6 units. This time the K limit matters: the tallest stack is still above the water level, but we can only take 3 blocks from it.
The video below shows this example using stacks of blocks.
How fast is this? Computing F(L) by looping over all the columns takes O(N) time, and we do this O(log M) times per row, where M is the largest column target. This gives an O(N2 log M) solution, which is roughly 3 × 107 steps. This should be fast enough in C++, but we can do better.
At the start of each row, we sort a copy of the remaining targets and build its prefix sums. Then the targets split into three groups:
Sorting and building prefix sums for every row, searching for its height, and constructing its cells takes O(N2 log N + N log M log N) time overall. This is fast enough to score 100. Our Python code below also passes, but it is fairly close to the time limit, so write your Python solution carefully.
Below you can see the full solution written in Python and C++.
I suggest trying to code the solution yourself and only look at our code after you finish or if you get stuck.
We sort a copy of the remaining targets for the binary search, so the columns in our output stay in their original order.
In C++, we use long long because the totals can be much larger than the range of an int.
import bisect
import sys
# N is the size of the square.
N = 0
# K is the largest value allowed in a cell.
K = 0
# R and C contain the row and column targets. Note that the lists start from
# 0, and so the values are R[0] to R[N-1] and C[0] to C[N-1].
R = []
C = []
# Read the values of N, K, and the row and column targets.
N, K = map(int, input().strip().split())
R = list(map(int, input().strip().split()))
C = list(map(int, input().strip().split()))
# This function prints NO and then ends the program
def NO():
print("NO")
sys.exit(0)
# The row and column targets must have the same total
if sum(R) != sum(C):
NO()
# Compute the answer
# From now on, C[j] stores the amount column j still needs
square = []
for need in R:
# Sort a copy of the remaining targets and build its prefix sums
ordered = sorted(C)
prefix = [0]
for c in ordered:
prefix.append(prefix[-1] + c)
# F(L) is the number of units we place if we lower the stacks to height L
def F(L):
first = bisect.bisect_right(ordered, L) # targets <= L give 0
capped = bisect.bisect_left(ordered, L + K) # targets >= L+K give K
middle = prefix[capped] - prefix[first] - L * (capped - first)
return middle + K * (N - capped)
if need > F(0):
# This row needs more than its cells can provide
NO()
# Binary search for the smallest height L with F(L) <= need
low = 0
high = ordered[-1]
while low < high:
L = (low + high) // 2
if F(L) <= need:
high = L
else:
low = L + 1
L = low
# Lower every stack to height L, taking at most K from each
row = [min(K, max(0, c - L)) for c in C]
# Place the last few units in columns that are tied at height L
extra = need - sum(row)
for j in range(N):
if extra > 0 and row[j] < K and C[j] - row[j] == L:
row[j] += 1
extra -= 1
# Update the amount each column still needs
for j in range(N):
C[j] -= row[j]
square.append(row)
print("YES")
for row in square:
print(*row)
#include <cstdio>
#include <cstdlib> // for exit()
#include <algorithm> // for std::min, std::max, std::sort, std::lower_bound, and std::upper_bound
#include <vector> // for std::vector
/* N is the size of the square. */
int N;
/* K is the largest value allowed in a cell. */
long long K;
/*
* R and C contain the row and column targets. Note that the arrays start from
* 0, and so the values are R[0] to R[N-1] and C[0] to C[N-1].
*/
long long R[1005];
long long C[1005];
/* square[i][j] will store the value in row i and column j */
long long square[1005][1005];
/* ordered will store a sorted copy of the remaining targets, and prefix will store its prefix sums */
std::vector<long long> ordered;
std::vector<long long> prefix;
/* This function prints NO and then ends the program */
void NO() {
printf("NO\n");
exit(0);
}
/* F(L) is the number of units we place if we lower the stacks to height L */
long long F(long long L) {
// targets <= L give 0
int first = std::upper_bound(ordered.begin(), ordered.end(), L) - ordered.begin();
// targets >= L+K give K
int capped = std::lower_bound(ordered.begin(), ordered.end(), L + K) - ordered.begin();
long long middle = prefix[capped] - prefix[first] - L * (capped - first);
return middle + K * (N - capped);
}
int main(void) {
/* Read the values of N, K, and the row and column targets. */
scanf("%d%lld", &N, &K);
for (int i = 0; i < N; i++) {
scanf("%lld", &R[i]);
}
for (int j = 0; j < N; j++) {
scanf("%lld", &C[j]);
}
/* The row and column targets must have the same total */
long long row_total = 0, column_total = 0;
for (int i = 0; i < N; i++) {
row_total += R[i];
column_total += C[i];
}
if (row_total != column_total) {
NO();
}
/* Compute the answer */
// From now on, C[j] stores the amount column j still needs
for (int i = 0; i < N; i++) {
long long need = R[i];
// Sort a copy of the remaining targets and build its prefix sums
ordered.assign(C, C + N);
std::sort(ordered.begin(), ordered.end());
prefix.assign(N + 1, 0);
for (int j = 0; j < N; j++) {
prefix[j+1] = prefix[j] + ordered[j];
}
if (need > F(0)) {
// This row needs more than its cells can provide
NO();
}
// Binary search for the smallest height L with F(L) <= need
long long low = 0, high = ordered[N-1];
while (low < high) {
long long L = (low + high) / 2;
if (F(L) <= need) {
high = L;
} else {
low = L + 1;
}
}
long long L = low;
// Lower every stack to height L, taking at most K from each
long long extra = need;
for (int j = 0; j < N; j++) {
square[i][j] = std::min(K, std::max(0LL, C[j] - L));
extra -= square[i][j];
}
// Place the last few units in columns that are tied at height L
for (int j = 0; j < N; j++) {
if (extra > 0 && square[i][j] < K && C[j] - square[i][j] == L) {
square[i][j]++;
extra--;
}
}
// Update the amount each column still needs
for (int j = 0; j < N; j++) {
C[j] -= square[i][j];
}
}
printf("YES\n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%lld ", square[i][j]);
}
printf("\n");
}
}