This was Code Jam's first-ever five-problem Qualification Round! Our easiest and hardest problems, Vestigium and Indicium, were both about the traces of Latin squares (and both of their names roughly mean "trace" in Latin). Vestigium was an implementation problem; Indicium was more daunting, but could be solved in various ways from case work to bipartite matching. Of the middle three problems, Nesting Depth and Parenting Partnering Returns were tractable options for scoring enough points to advance, and ESAb ATAd was a difficult interactive problem (a sequel to last year's Dat Bae problem) with a satisfying solution.
Only 1 minute and 53 seconds into the round, arknave submitted the first correct solution of Code Jam 2020! And it didn't even take an hour for xiaowuc1, a legendarily fast Qual Round solver, to earn a perfect score. cki86201 and Benq followed with their own perfect scores to claim second and third place, and Golovanov399 and Snuke rounded out the top 5 that managed a perfect score within the first 2 hours. Despite the difficulty of the last two problems, 340 users earned a perfect score!
We had over 96000 registrants, 44434 (22222 + 22212) of whom submitted at least one attempt, and 40697 of whom earned at least one point. Over 30000 contestants qualified for the Round 1s by scoring 30 points or more. All of these numbers are records for Code Jam! Just like last year, we were happy to see submissions in each of our supported languages.
Thank you for joining us for another Qual Round, and we'll see many of you again in Round 1A in a week. (Remember that you can keep trying Round 1s as long as you have not already advanced to Round 2.) If you did not make it to Round 1 this time, we strongly encourage you to try again in 2021, since these things take time and practice! In either case, one way to train is to compete in Kick Start rounds throughout the year...
Cast
Vestigium: Written by the Code Jam team. Prepared by Mohamed Yosri Ahmed.
Nesting Depth: Written by Pablo Heiber. Prepared by Artem Iglikov.
Parenting Partnering Returns: Written by Pablo Heiber and Ian Tullis. Prepared by Jonathan Irvin Gunawan.
ESAb ATAd: Written by Pablo Heiber. Prepared by Pi-Hsun Shih.
Indicium: Written by Darcy Best and Ian Tullis. Prepared by Trung Thanh Nguyen and Ian Tullis.
Solutions and other problem preparation and review by Mohamed Yosri Ahmed, Liang Bai, Darcy Best, Timothy Buzzelli, John Dethridge, Kevin Gu, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Andy Huang, Artem Iglikov, and Pi-Hsun Shih.
Analysis authors:
Vestigium means "trace" in Latin. In this problem we work with Latin squares and matrix traces.
The trace of a square matrix is the sum of the values on the main diagonal (which runs from the upper left to the lower right).
An N-by-N square matrix is a Latin square if each cell contains one of N different values, and no value is repeated within a row or a column. In this problem, we will deal only with "natural Latin squares" in which the N values are the integers between 1 and N.
Given a matrix that contains only integers between 1 and N, we want to compute its trace and check whether it is a natural Latin square. To give some additional information, instead of simply telling us whether the matrix is a natural Latin square or not, please compute the number of rows and the number of columns that contain repeated values.
The first line of the input gives the number of test cases, T. T test cases follow. Each starts with a line containing a single integer N: the size of the matrix to explore. Then, N lines follow. The i-th of these lines contains N integers M_{i,1}, M_{i,2} ..., M_{i,N}. M_{i,j} is the integer in the i-th row and j-th column of the matrix.
For each test case, output one line containing Case #x: k r c
,
where x
is the test case number (starting from 1),
k
is the trace of the matrix, r
is the number of
rows of the matrix that contain repeated elements, and c
is the
number of columns of the matrix that contain repeated elements.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 100.
1 ≤ M_{i,j} ≤ N, for all i, j.
3 4 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 4 2 2 2 2 2 3 2 3 2 2 2 3 2 2 2 2 3 2 1 3 1 3 2 1 2 3
Case #1: 4 0 0 Case #2: 9 4 4 Case #3: 8 0 2
In Sample Case #1, the input is a natural Latin square, which means no row or column has repeated elements. All four values in the main diagonal are 1, and so the trace (their sum) is 4.
In Sample Case #2, all rows and columns have repeated elements. Notice that each row or column with repeated elements is counted only once regardless of the number of elements that are repeated or how often they are repeated within the row or column. In addition, notice that some integers in the range 1 through N may be absent from the input.
In Sample Case #3, the leftmost and rightmost columns have repeated elements.
tl;dr: Given a string of digits S, insert a minimum number of opening and closing parentheses into it such that the resulting string is balanced and each digit d is inside exactly d pairs of matching parentheses.
Let the nesting of two parentheses within a string be the substring that occurs strictly between them. An opening parenthesis and a closing parenthesis that is further to its right are said to match if their nesting is empty, or if every parenthesis in their nesting matches with another parenthesis in their nesting. The nesting depth of a position p is the number of pairs of matching parentheses m such that p is included in the nesting of m.
For example, in the following strings, all digits match their nesting
depth: 0((2)1)
, (((3))1(2))
, ((((4))))
,
((2))((2))(1)
. The first three strings have minimum length among
those that have the same digits in the same order, but the last one does not
since ((22)1)
also has the digits 221
and is
shorter.
Given a string of digits S, find another string S', comprised of parentheses and digits, such that:
The first line of the input gives the number of test cases, T. T lines follow. Each line represents a test case and contains only the string S.
For each test case, output one line containing Case #x: y
, where
x
is the test case number (starting from 1) and y
is the string S' defined above.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ length of S ≤ 100.
Each character in S is either 0
or 1
.
Each character in S is a decimal digit between 0
and
9
, inclusive.
4 0000 101 111000 1
Case #1: 0000 Case #2: (1)0(1) Case #3: (111)000 Case #4: (1)
The strings ()0000()
, (1)0(((()))1)
and
(1)(11)000
are not valid solutions to Sample Cases #1, #2 and
#3, respectively, only because they are not of minimum length. In addition,
1)(
and )(1
are not valid solutions to Sample Case
#4 because they contain unmatched parentheses and the nesting depth is 0
at the position where there is a 1.
You can create sample inputs that are valid only for Test Set 2 by removing the parentheses from the example strings mentioned in the problem statement.
Cameron and Jamie's kid is almost 3 years old! However, even though the child is more independent now, scheduling kid activities and domestic necessities is still a challenge for the couple.
Cameron and Jamie have a list of N activities to take care of during the day. Each activity happens during a specified interval during the day. They need to assign each activity to one of them, so that neither of them is responsible for two activities that overlap. An activity that ends at time t is not considered to overlap with another activity that starts at time t.
For example, suppose that Jamie and Cameron need to cover 3 activities: one running from 18:00 to 20:00, another from 19:00 to 21:00 and another from 22:00 to 23:00. One possibility would be for Jamie to cover the activity running from 19:00 to 21:00, with Cameron covering the other two. Another valid schedule would be for Cameron to cover the activity from 18:00 to 20:00 and Jamie to cover the other two. Notice that the first two activities overlap in the time between 19:00 and 20:00, so it is impossible to assign both of those activities to the same partner.
Given the starting and ending times of each activity, find any schedule that does not require the same person to cover overlapping activities, or say that it is impossible.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer N, the number of activities to assign. Then, N more lines follow. The i-th of these lines (counting starting from 1) contains two integers S_{i} and E_{i}. The i-th activity starts exactly S_{i} minutes after midnight and ends exactly E_{i} minutes after midnight.
For each test case, output one line containing Case #x: y
, where x
is
the test case number (starting from 1) and y
is IMPOSSIBLE
if there
is no valid schedule according to the above rules, or a string of exactly N characters
otherwise. The i-th character in y
must be C
if the i-th activity
is assigned to Cameron in your proposed schedule, and J
if it is assigned to
Jamie.
If there are multiple solutions, you may output any one of them. (See "What if a test case has multiple correct solutions?" in the Competing section of the FAQ. This information about multiple solutions will not be explicitly stated in the remainder of the 2020 contest.)
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 ≤ S_{i} < E_{i} ≤ 24 × 60.
2 ≤ N ≤ 10.
2 ≤ N ≤ 1000.
4 3 360 480 420 540 600 660 3 0 1440 1 3 2 4 5 99 150 1 100 100 301 2 5 150 250 2 0 720 720 1440
Case #1: CJC Case #2: IMPOSSIBLE Case #3: JCCJJ Case #4: CC
Sample Case #1 is the one described in the problem statement. As mentioned above, there are other
valid solutions, like JCJ
and JCC
.
In Sample Case #2, all three activities overlap with each other. Assigning them all would mean someone would end up with at least two overlapping activities, so there is no valid schedule.
In Sample Case #3, notice that Cameron ends an activity and starts another one at minute 100.
In Sample Case #4, any schedule would be valid. Specifically, it is OK for one partner to do all activities.
Last year, a research consortium had some trouble with a distributed database system that sometimes lost pieces of the data. You do not need to read or understand that problem in order to solve this one!
The consortium has decided that distributed systems are too complicated, so they are storing B bits of important information in a single array on one awesome machine. As an additional layer of security, they have made it difficult to obtain the information quickly; the user must query for a bit position between 1 and B, and then they receive that bit of the stored array as a response.
Unfortunately, this ultra-modern machine is subject to random quantum fluctuations! Specifically, after every 1st, 11th, 21st, 31st... etc. query is sent, but before the response is given, quantum fluctuation causes exactly one of the following four effects, with equal probability:
0
becomes
a 1
, and vice versa.Moreover, there is no indication of what effect the quantum fluctuation has had each time. The consortium is now concerned, and it has hired you to get its precious data back, in whatever form it is in! Can you find the entire array, such that your answer is accurate as of the time that you give it? Answering does not count as a query, so if you answer after your 30th query, for example, the array will be the same as it was after your 21st through 30th queries.
This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.
Initially, your program should read a single line containing two integers T and B: the number of test cases and the number of bits in the array, respectively. Note that B is the same for every test case.
Then, you need to process T test cases. In each case, the judge begins with a predetermined B-bit array; note that this array can vary from test case to test case, and is not necessarily chosen at random. Then, you may make up to 150 queries of the following form:
0
or 1
, the value it currently has stored at bit
position P, or N
if you provided a malformed line (e.g., an
invalid position).
Then, after you have made as many of the 150 queries above as you want, you must make one more exchange of the following form:
0
or 1
, representing the bits
currently stored in the array (which will not necessarily match the
bits that were initially present!)
Y
if your answer was correct, and uppercase
N
if it was not (or you provided a malformed line).
If you receive Y
, you should begin the next test case,
or stop sending input if there are no more test cases.
After the judge sends N
to your input stream, it will not send
any other output. If your program continues to wait for the judge after
receiving N
, your program will time out, resulting in a Time
Limit Exceeded error. Notice that it is your responsibility to have your
program exit in time to receive a Wrong Answer judgment instead of a Time
Limit Exceeded error. As usual, if the memory limit is exceeded, or your
program gets a runtime error, you will receive the appropriate judgment.
Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
B = 10.
B = 20.
B = 100.
You can use this testing tool to test locally or on our servers. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. The interactive runner was changed after the 2019 contest. Be sure to download the latest version. For more information, read the Interactive Problems section of the FAQ.
You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.
Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.
The following interaction corresponds to Test Set 1.
t, b = readline_int_list() // reads 100 into t and 10 into b. // The judge starts with the predetermined array for this test case: // 0001101111. (Note: the actual Test Set 1 will not necessarily // use this array.) printline 1 to stdout // we ask about position 1. flush stdout // Since this is our 1st query, and 1 is 1 mod 10, the judge secretly and // randomly chooses one of the four possible quantum fluctuation effects, as // described above. It happens to choose complementation + reversal, so now // the stored value is 0000100111. r = readline_chr() // reads 0. printline 6 to stdout // we ask about position 6. flush stdout // Since this is our 2nd query, and 2 is 2 mod 10, the judge does not choose // a quantum fluctuation effect. r = readline_chr() // reads 0. ... // We have omitted the third through tenth queries in this example. ... printline 1 to stdout // we decide to ask about position 1 again. flush stdout // Since this is our 11th query, and 11 is 1 mod 10, the judge secretly and // randomly chooses a quantum fluctuation effect, and happens to get // reversal, so now the stored value is 1110010000. r = readline_chr() // reads 1. printline 1110110000 to stdout // we try to answer. why?!?! flush stdout ok = readline_chr() // reads N -- we have made a mistake! exit // exits to avoid an ambiguous TLE error
Indicium means "trace" in Latin. In this problem we work with Latin squares and matrix traces.
A Latin square is an N-by-N square matrix in which each cell contains one of N different values, such that no value is repeated within a row or a column. In this problem, we will deal only with "natural Latin squares" in which the N values are the integers between 1 and N.
The trace of a square matrix is the sum of the values on the main diagonal (which runs from the upper left to the lower right).
Given values N and K, produce any N-by-N "natural Latin square" with trace K, or say it is impossible. For example, here are two possible answers for N = 3, K = 6. In each case, the values that contribute to the trace are underlined.
2 1 3 3 1 2
3 2 1 1 2 3
1 3 2 2 3 1
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line containing two integers N and K: the desired size of the matrix and the desired trace.
For each test case, output one line containing Case #x: y
, where
x
is the test case number (starting from 1) and y
is IMPOSSIBLE
if there is no answer for the given parameters or
POSSIBLE
otherwise. In the latter case, output N more
lines of N integers each, representing a valid "natural Latin square"
with a trace of K, as described above.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
N ≤ K ≤ N^{2}.
T = 44.
2 ≤ N ≤ 5.
1 ≤ T ≤ 100.
2 ≤ N ≤ 50.
2 3 6 2 3
Case #1: POSSIBLE 2 1 3 3 2 1 1 3 2 Case #2: IMPOSSIBLE
Sample Case #1 is the one described in the problem statement.
Sample Case #2 has no answer. The only possible 2-by-2 "natural Latin squares" are as follows:
1 2 2 1
2 1 1 2
These have traces of 2 and 4, respectively. There is no way to get a trace of 3.
One simple way to check whether the values in a row or column are a permutation of the values from 1 to N is to sort them and then step through them, checking whether the sorted list starts at 1 and increases by 1 each time. Another option, which avoids the sort and takes time linear in N, is to look at the values one by one and store each one in a hash table-based data structure. If we ever find that a value is already in the set, then that row or column contains a repeated value. Because there are N values and the problem guarantees that they are integers between 1 and N, inclusive, the absence of duplicates implies that we have a permutation as desired.
Finding the trace is also straightforward — iterate through the rows taking the i-th value from the i-th row, and add the values together.
To solve Test Set 1, we can put an opening parenthesis before each group of 1
s and a
closing parenthesis after.
We can use the following trick to simplify the implementation: prepend and append one extra
0
to S. Then the implementation is just replacing 01
with
0(1
and 10
with 1)0
, which can be written in one line of
code in some programming languages. Don't forget to remove the extra 0
s from the
end of the resulting string!
For convenience, let's once again use the trick described above: prepend and append extra
0
s to S, and then scan S from left to right.
Suppose we see some number A immediately followed by some larger number B and suppose all of the previously inserted parentheses would leave A at the right nesting depth — that is, there are exactly A unmatched opening parentheses preceding A, and no unmatched closing parentheses. For B to be at nesting depth B we need to add at least B - A opening parentheses. We can just do that and nothing else, to keep the final string length minimal. Any additional opening parentheses we would add would need to be closed before B, which would needlessly lengthen the string. Similarly, if we see some number A immediately followed by some smaller number B, we can just insert A - B closing parentheses. And in the case when A is equal to B, we don't need to add anything.
We don't need any parentheses before the temporary 0
in the beginning, or after the one in the end, so we can just drop them before printing the
result.
Since we only add p parentheses when at least p are needed, the resulting string is of minimum length.
The problem can be solved using only string replacements. First, replace each
digit D with D (
s, then the digit itself, then D
)
s. Then eliminate all instances of )(
, collapsing
the string each time, until there are no more to remove.
Here's a Python3 implementation:
for C in range(int(input())): rawstr = ''.join([int(x) * '(' + x + ')' * int(x) for x in str(input())]) for _ in range(9): rawstr = rawstr.replace(')(', '') print("Case #{}: {}".format(C+1, rawstr))
We can solve this test set by naively trying every possible subset of activities to be covered by Jamie and assign the rest of the activities to be covered by Cameron. For each subset of activities, we can check whether a pair of activities overlap for each pair of activities. An activity with start time s_{1} and end time t_{1} overlaps with another activity with start time s_{2} and end time t_{2} if the time intersection is not empty (i.e., max(s_{1}, s_{2}) < min(t_{1}, t_{2})).
The running time of this solution is O(2^{N} × N^{2}), which is fast enough to solve Test Set 1.
We can solve this test set by greedily assigning the activities in increasing order of start time. For each activity (in increasing order of start time), we can check whether Jamie or Cameron can be assigned to cover the activity and assign the activity to whomever can be assigned to (or arbitrarily if both partners can be assigned). The check can be done by iterating all activities that have been previously assigned to Jamie and Cameron.
The greedy assignment is correct because the only way that the assignment fails is when there is a time that is covered by three activities. In such a case, there is indeed no valid assignment. When deciding who to assign an activity with start time s, only activities with start times no later than s have been assigned. Therefore, if both Jamie and Cameron have some activity assigned with end time later than s, it means that there are three activities that use the time between s and s + 1, and therefore, there is no possible assignment. If an assignment is possible, there cannot be any set of three activities that pairwise overlap, so by the contrapositive of the the previous argument, we will be able to assign the activity to at least one of Jamie or Cameron at every step.
The running time of this solution is O(N^{2}), which is fast enough to solve this test set. To optimize the solution to O(N log N) time, we can efficiently check whether an activity can be assigned to Jamie or Cameron by keeping track of the end time of the last activity assigned to each partner and comparing this to the start time of the new activity. In this case, only O(N) extra time is needed after sorting the activities by their start time.
Another possible approach to solve this test set is to construct a graph with N nodes, each representing one activity. We add an edge connecting a pair of nodes if the pair of activities represented by the nodes overlap (see Test Set 1 section for details on how to check if two intervals overlap). This graph is commonly known as an interval graph.
Therefore, the problem is equivalent to finding a partition of nodes C and J such that every edge connects a node in C and a node in J, as we can assign all activities represented by nodes in C to Cameron and all activities represented by nodes in J to Jamie. The running time of the algorithm to find the partition (or report if one does not exist) is linear on the size of the graph. The graph has N nodes and O(N^{2}) edges, which means the solution requires O(N^{2}) time to build the graph and O(N^{2}) time to run the partition algorithm, so also O(N^{2}) time overall.
In Test Set 1, there are only 10 positions in the string. We can query for each of them and then submit the complete string, without having to worry about any quantum fluctuations (which would only happen if we submitted an 11th query).
Here is one of various ways to solve the second test set. We begin by querying for the first ten positions in the real string, then create a "possibility set" containing all 1024 20-character strings that begin with those 10 characters. Then we update our "possibility set" to contain all strings that could have arisen from those strings after the next quantum fluctuation. The correct answer is in here somewhere — now we need to narrow the set down!
Before making each subsequent query, we first find the string index (between
1 and 20) at which the proportion of 0
s and 1
s
among the strings in our possibility set is most nearly even. Then we query
the real string at that index, and eliminate from the possibility set any
strings that are not consistent with that information. Whenever we can
indeed find a position with even proportions, we are guaranteed to cut the
size of the set in half, but if there is no such position, we may not be
able to eliminate that many possibilities. We can continue in this way,
remembering to expand the possibility set every time there is a quantum
fluctuation, until only one possibility remains, which must be the answer.
It is not easy to prove that this strategy will converge upon an answer. Intuitively, we can observe that a quantum fluctuation increases the size of the possibility set by at most 4, and even if we somehow only cut the possiblity set by 20% with each pruning, we would still easily beat that factor-of-4 increase and make enough progress to finish within 150 queries. Moreover, it would not be possible for the strings in the possibility set to all be distinct while being so similar at every individual position (recall that we always pick the position that will be most useful to us in the worst case). Also, Test Set 2 is a Visible Verdict set, so we might as well just submit our answer and see.
The above strategy will not work for 100-character strings, since the possibility set would be astronomically huge. Fortunately, there is a much simpler approach.
Observe that if we can find two positions that are equidistant from the
center of the string and have the same value, we can use them to detect when
a quantum fluctuation has included a complementation (with or without a
reversal). Suppose, for example, that the two ends of the string are
0
just before a quantum fluctuation. After the fluctuation, we
can check the first one. If it is 1
, then there was a
complementation; if not, there wasn't one. This is true regardless of
whether that quantum fluctuation included a reversal.
Now suppose that we continue to check pairs of positions in this way, moving inward one step at a time. After every quantum fluctuation, we must spend one query to check for complementation so we can update our existing knowledge about the string if there has been one. If every pair turns out to be a "same pair" like the first pair, then we never needed to care about reversals anyway (since the string is palindromic), and we are done.
But what if, in the course of this, we find a "different pair"? Such pairs are helpful in their own way! If we query the first position of a "different pair" after a quantum fluctuation and we find that that bit has changed, then we know that either a complementation or reversal has happened, but not both.
Once we have such a "different pair", we can use it in conjunction with the "same pair", spending 2 out of every 10 queries to learn exactly what happened in each quantum fluctuation. For example, if the first position of our "same pair" stayed the same but the first position of our "different pair" did not, we know that the quantum fluctuation included a reversal but no complementation.
In the above analysis, we assumed we would encounter a "same pair" first. If the first pair is different, though, we can proceed until we encounter a "same pair"; if we never encounter one, then we do not care about the distinction between complementation and reversal, because the operations are equivalent for that particular string. If we do encounter a "same pair", though, then we can proceed as above.
How many queries will we need in the worst case? We can use all of our first 10 to gather data, since whatever happened in the quantum fluctuation at the start of the problem is unknowable and does not matter. After that, we may need to use up to 2 out of every 10 queries to reorient ourselves before spending the remaining 8 gathering data. So, to be sure we can find the entire string, we will need 10 queries, plus 11 more sets of 10 queries in which we learn 8 positions each time, (to get us to 98 positions known), plus 2 more queries for a final reorientation, plus 2 more to get the last two positions. That is a total of 124, which is well within the allowed limit of 150.
Last year, we had the
Dat Bae problem
about deletions from a string in a database; the name was
Data Base
, altered in a way that reflected the theme.
ESAb ATAd
is similar, with case change serving as a rough
equivalent of complementation. (Imagine how much the Code Jam team has
enjoyed trying to type the name correctly each time!)
There are a few different options for solving test set 1. Since there are only 44 possible cases, one option is to generate all answers by hand or via a program that is run locally, then submit a program that dispenses those. Another approach is to notice that there are not many different Latin squares for N ≤ 5 (see the number of Latin squares here), and check them all. To generate all Latin squares, we can recursively fill in the cells one by one. For each cell, we try all N possible values. For each one, we ensure that it does not conflict with any cells in the same row or same column. Since there are at most 161280 Latin squares to consider, this is quite quick.
Unfortunately, once N gets even slightly large, there are way too many Latin squares to generate them all (for N = 11, for example, there are 776966836171770144107444346734230682311065600000 different Latin squares).
There are many creative ways to solve this test set. The Code Jam forum is a good place to share and discuss different solutions! For example, we can directly create Latin squares with the appropriate trace by modifying structured Latin squares (for example, by modifying circulant Latin squares). Below, we discuss an easy-to-implement idea which is a little tricky to come up with and uses a graph algorithm in the middle!
First, we start by dealing with the impossible cases. If K = N+1, then the only
possible diagonals have exactly one 2
and N-1 1
s. However, if
N-1 of the diagonal
elements are 1
, then the only location for the 1
in the remaining
row must be on
the diagonal, so we cannot make a sum of N+1. Similarly, we cannot make a sum
of N^{2}-1 since the only possible diagonal is one N-1
and N-1 N
s.
We will now show a construction which works for every other case (with 2 additional small cases that don't work, see below). One of the main insights needed is that all possible sums are achievable using a diagonal with almost all values the same. In particular, we may assume that at least N-2 values are the same: AAAA ... AABC for some A, B, C (not necessarily all different).
For example, if N = 10 and K = 20, we can choose A = 2, B = 2, and C = 2. If N = 10 and K = 55, we can choose A = 6, B = 4, and C = 3. We already showed above that A = B if and only if A = C. We leave it as an exercise to show that all values for K between N and N^{2} are possible with these constraints. (Note: you have to be a little careful with N = 3. If B = C, then A = B = C for a similar reason; so with N = 3, neither K = 5 nor K = 7 will have solutions). To find the appropriate values of A, B, and C, we can brute force all possible triples and check whether the chosen diagonal will work.
Now that we know what the diagonal looks like, how do we actually find a Latin square that has this diagonal? To do that, we will fill in the unfilled cells row by row. We will use bipartite matching to find a valid row. In one bipartition, we have N vertices for the N cells in that row. In the other bipartition, we have N vertices for the N numbers that can be placed into the cell. Make an edge between the cell vertex on the diagonal and the number vertex that was decided on. For every other cell, make an edge between a cell vertex and a number vertex if that number can be put into that cell without breaking the Latin square properties.
We can greedily pick any perfect matching for each row starting with the rows with B and C on their diagonal. Once we have filled in these two rows, we can use Hall's Marriage Theorem to show that we will never run into any issues (so long as the conditions above about A, B, C are met).
This section is dedicated to proving the above claim that Hall's theorem holds. We will assume in this section that the reader is comfortable with Hall's theorem. A one sentence high-level reminder of Hall's theorem: All subsets of one bipartition have a neighborhood that is at least as large as the original subset if and only if the graph has a perfect matching.
For the explanation here, we will make the top two rows with B and C on their diagonal
as the top two rows. We'll assume that these two rows are already filled in (and leave the
proof you can do this to the reader). The important part is that the top-left 2 × 2
submatrix is CA
/AB
. Now imagine that we have filled in
N-k rows (and have k mostly empty rows). Consider this example with N = 8
and k = 3.
(?
means filled in, but it doesn't matter with what and _
means not filled in yet):
CA?????? AB?????? ??A????? ???A???? ????A??? _____A__ ______A_ _______A
For each of the N-1 non-A
"cell vertices", the N-k vertices on the left
of the diagonal have a degree of k and the k-1 vertices on the right of the diagonal
have a degree of k-1 (because the number A
is also restricted).
For each of the N-1 non-A
"number vertices", each number originally had
degree N and we have removed at least N-k of those edges since the number
appeared once in the top N-k rows. Thus, the maximum degree of the "number vertices"
is k.
We will ignore the "cell vertex" and the "number vertex" corresponding to the forced diagonal entry since that will be forced in our matching (and leaving it out makes our math below easier).
Let X be a subset of "cell vertices". Let m = |X|. We must show that |N(X)| ≥ m in order to utilize Hall's theorem (where N(X) is the set of "number vertices" that are adjacent to at least one vertex in X). We have 2 separate cases:
Case 1: m ≤ k-1.
Since the degree of each vertex in X is at least k-1, the number of edges leaving X is at least m × (k-1). Consider the "number vertices" that these edges are absorbed into. Since the maximum degree of "number vertices" is k, there are at least (m × (k-1))/k "number vertices" that absorb these edges. That is, |N(X)| ≥ (m × (k-1))/k = m-m/k. Since m ≤ k-1, we have that m/k < 1. So |N(X)| > m-1. Since |N(X)| is an integer, we have |N(X)| ≥ m as desired.
Case 2: m ≥ k.
Consider the edges leaving X. At most k-1 of them have degree k-1, and the remaining have degree k. Thus, the number of edges leaving X is at least (k-1) × (k-1) + (m-(k-1)) × k. Since the maximum degree of "number vertices" is k, there are at least ((k-1) × (k-1) + (m-(k-1)) × k)/k "number vertices" that absorb these edges. That is, |N(X)| ≥ ((k-1) × (k-1) + (m-(k-1)) × k)/k = m - (1 - 1/k). Since 1 - 1/k < 1, we have |N(X)| > m-1. Since |N(X)| is an integer, we have |N(X)| ≥ m as desired.
Thus, in all cases, the conditions for Hall's theorem are satisfied, so there exists a perfect matching and we can iteratively complete the Latin square.