Motivation
A few weeks back I had the opportunity to attend the ICPC Asia West Continent Finals 2023 along with my teammates VS-Codes and om_mittal7, where we encountered the following problems as a part of the contest problemset. We weren't able to solve E in contest, and that kept bugging me for quite a while. I was especially motivated to try and prove the claims that we had made in the contest, which proved to be quite a hard challenge.
Finally, when I did manage to cook up solutions with a reasonably sound proofs, the underlying ideas and the little observations made along the way felt so elegant that I decided to document it here for future reference, and to share with the community. I hope these ideas turn out to be useful for someone stuck in a similar place as I was a few days back.
A. Basic Vocabulary
We assume WLOG that b1>b2. The number of digits in the base-b1 representation of n is therefore not greater than that in base-b2. Hence, if a solution exists, (n)b1 must be a prefix of (n)b2. Here (x)b represents the base-b representation of the integer x.
Let's start off by observing that any number n when represented in base b, where 2b>n is of the form [1,n−b]b. Considering 2b1>n, what must be the constraint on b2 for (n)b1 to be a prefix?
Let n−b1=x, then n=[1,x]b1. Note that x>0 since b1<n.
Thus we have,
Thus, (b2+x) is the quotient obtained on dividing n by bk2.
Now, we note that 1≤x≤b2−1, since x is a non-zero digit in base-b2. Therefore,
If there exists any b2, k satisfying the above inequality, then we can derive b1 as follows:
- q←⌊nbk2⌋
- x←q−b2
- b1←n−x
We observe that the upper bound of (1) strictly increases with b2 for a given k. Therefore, it is optimal to choose the largest value of b2 such that (b2+x)bk2≤n, which can be found in O(log(√n)) by Binary Search. Since b2≥2, we must test at most log2(n) values of k.
Note that all this while, we are operating under the assumption that 2b1<n. Let's observe the case when k=1. We have,
Now, consider how we find b2. We choose the largest value that satisfies the lower bound and check whether it satisfies the upper bound. What if the upper bound for a certain b2 went beyond the lower bound for b2+1? For visualisation, one could try imagining that for every b2 there is a certain interval in which n must lie for the inequality to hold. What happens when these intervals start to overlap? Then we'd be guaranteed a solution for any value of n.
which is true ∀b2≥4.
Therefore, we conclude that ∀n≥(4+1)(4)=20, ∃b1,b2 such that 2b1>n and (1) holds for k=1.
Thus, we finally have our complete solution. For n<20 the trivial brute force algorithm is fast enough. For n≥20, we test solely for k=1 as described before and report the answer obtained.
E. Parker Rectangle
Given r+c=n⟹c=n−r. We assume WLOG that r≤c⟹0<r≤n2.
Let Mr×c be the constructed matrix. Let S be the sum of all elements in M. Let Ri denote the sum of elements in the ith row and Cj denote the sum of elements in the jth column of M.
For convenience, we consider the matrices to be 0-indexed, that is, the first element of the first row of M is denoted as M00.
Claim: There exists no Parker Rectangle of odd order greater than 5.
By inspection, it is trivial to construct Parker Rectangles of order 3 and 5, such as the ones below:
M_3=\begin{bmatrix}0&1\end{bmatrix}
M_5=\begin{bmatrix}0&3&4 \cr 5&2&1\end{bmatrix}
For n=2m, we use the following method of construction:
Let r=c=m. We define two m \times m matrices A and B as follows:
For example, when m=3,
And, when m=4,
Claim: For any given i,j the ordered pair (A_{ij},B_{ij}) is unique.
We now define an injection g:\mathbb{Z}_m\times \mathbb{Z}_m \rightarrow \mathbb{Z} as g(x,y)=\alpha x+y where \alpha \geq m. For the purposes of this construction let us consider \alpha = m.
We then construct the Parker Rectangle M_n as M_{ij}=g(A_{ij},B_{ij}).
For example, when m=3,
And, when m=4,
Proof of correctness
Note that by construction, each row in matrices A and B contains the numbers 0 \ ... \ m-1 exactly once (can be proved using the Pigeonhole principle).
Hence \forall i,
When m is odd, each column in A and B also contains contains the numbers 0 \ ... \ m-1 exactly once. Thus C_i=\frac{(m-1)m}{2}(\alpha +1) \ \forall i, and so the maximum absolute difference =0 \leq \lceil \frac{n}{2}\rceil.
When m is even, the even-indexed columns in B contain the even numbers 0,2,\ ... \ m-2 repeated twice, and the odd-indexed columns contain the odd numbers 1,3, \ ... \ m-1 repeated twice.
Hence,
And therefore,
Hence, the maximum absolute difference =\frac{m^2}{2}-\frac{m(m-2)}{2}=m \leq \lceil \frac{n}{2}\rceil.