### twoplusthree's blog

By twoplusthree, history, 7 weeks ago,

#### 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 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 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.

Looking forward to your thoughts and suggestions!

## A. Basic Vocabulary

Trivia

We assume WLOG that $b_1>b_2$. The number of digits in the base-$b_1$ representation of $n$ is therefore not greater than that in base-$b_2$. Hence, if a solution exists, $(n)_{b_1}$ must be a prefix of $(n)_{b_2}$. 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 $2b_1>n$, what must be the constraint on $b_2$ for $(n)_{b_1}$ to be a prefix?

Let $n-b_1=x$, then $n=[1,x]_{b_1}$. Note that $x>0$ since $b_1<n$.

Thus we have,

$n=[1,x,\underbrace{\cdots}_{k \ \text{digits}}]_{b_2} \implies n=(b_2^{k+1}+x \cdot b_2^k)+r \implies n=(b_2+x)b_2^k+r \ \ \ \ \ (k>0, r<b_2^k)$

Thus, $(b_2+x)$ is the quotient obtained on dividing $n$ by $b_2^k$.

$(b_2+x)b_2^k \leq n \leq (b_2+x+1)b_2^k-1$

Now, we note that $1 \leq x \leq b_2-1$, since $x$ is a non-zero digit in base-$b_2$. Therefore,

$\boxed{(b_2+1)b_2^k \leq n \leq (2b_2)b_2^k-1} \cdots (1)$

If there exists any $b_2$, $k$ satisfying the above inequality, then we can derive $b_1$ as follows:

• $q \leftarrow \Big\lfloor\frac{n}{b_2^k}\Big\rfloor$
• $x \leftarrow q-b_2$
• $b_1 \leftarrow n-x$

We observe that the upper bound of $(1)$ strictly increases with $b_2$ for a given $k$. Therefore, it is optimal to choose the largest value of $b_2$ such that $(b_2+x)b_2^k \leq n$, which can be found in $\mathcal{O}(\log(n^{\frac{1}{k}}))$ by Binary Search. Since $b_2 \geq 2$, we must test at most $\log_2{(n)}$ values of $k$.

Note that all this while, we are operating under the assumption that $2b_1<n$. Let's observe the case when $k=1$. We have,

$(b_2+1)b_2 \leq n \leq 2b_2^2-1$

Now, consider how we find $b_2$. 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 $b_2$ went beyond the lower bound for $b_2+1$? For visualisation, one could try imagining that for every $b_2$ 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$.

$2b_2^2-1 \geq (b_2+1+1)(b_2+1) \implies b_2^2-3b_2-3 \geq 0$

which is true $\forall b_2 \geq 4$.

Therefore, we conclude that $\forall n \geq (4+1)(4)=20$, $\exists b_1,b_2$ such that $2b_1>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\geq 20$, we test solely for $k=1$ as described before and report the answer obtained.

Code

## E. Parker Rectangle

Trivia

Given $r+c=n \implies c=n-r$. We assume WLOG that $r\leq c \implies 0<r\leq \frac{n}{2}$.

Let $M_{r \times c}$ be the constructed matrix. Let $S$ be the sum of all elements in $M$. Let $R_i$ denote the sum of elements in the $i^{th}$ row and $C_j$ denote the sum of elements in the $j^{th}$ 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 $M_{00}$.

Claim: There exists no Parker Rectangle of odd order greater than $5$.

Proof

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:

$A_{ij}=(i+j)\%m$
$B_{ij}=(2i+j)\%m$

For example, when $m=3$,

$A=\begin{bmatrix}0&1&2 \cr 1&2&0 \cr 2&0&1\end{bmatrix}$

$B=\begin{bmatrix}0&1&2 \cr 2&0&1 \cr 1&2&0\end{bmatrix}$

And, when $m=4$,

$A=\begin{bmatrix}0&1&2&3 \cr 1&2&3&0 \cr 2&3&0&1 \cr 3&0&1&2\end{bmatrix}$

$B=\begin{bmatrix}0&1&2&3 \cr 2&3&0&1 \cr 0&1&2&3 \cr 2&3&0&1\end{bmatrix}$

Claim: For any given $i,j$ the ordered pair $(A_{ij},B_{ij})$ is unique.

Proof

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$,

$M_6=\begin{bmatrix}0&4&8 \cr 5&6&1 \cr 7&2&3\end{bmatrix}$

And, when $m=4$,

$M_8=\begin{bmatrix}0&5&10&15 \cr 6&11&12&1 \cr 8&13&2&7 \cr 14&3&4&9\end{bmatrix}$

#### 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$,

$R_i=\displaystyle\sum_{j=0}^{m-1}M_{ij}=\displaystyle\sum_{j=0}^{m-1}\alpha A_{ij}+B_{ij}=\alpha \displaystyle\sum_{j=0}^{m-1}A_{ij}+\displaystyle\sum_{j=0}^{m-1}B_{ij}=\frac{(m-1)m}{2}(\alpha +1)$

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,

$\displaystyle\sum_{i=0}^{m-1}B_{ij}=\begin{cases}2(0+2+...+m-2)=\frac{m(m-2)}{2} & \text{if } j \text{ is even} \cr 2(1+3+...+m-1)=\frac{m^2}{2} & \text{if } j \text{ is odd}\end{cases}$

And therefore,

$C_j=\begin{cases}\frac{(m-1)m}{2}\alpha+\frac{m(m-2)}{2} & \text{if } j \text{ is even} \cr \frac{(m-1)m}{2}\alpha+\frac{m^2}{2} & \text{if } j \text{ is odd}\end{cases}$

Hence, the maximum absolute difference $=\frac{m^2}{2}-\frac{m(m-2)}{2}=m \leq \lceil \frac{n}{2}\rceil$.

Code
• +70

 » 7 weeks ago, # |   0 Auto comment: topic has been updated by twoplusthree (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 for parker rectangle, i used the idea of magic squares and if n is odd, then pick middle (n-1)/2 elements and add them in a seperate row, remaining numbers i created a magic square.
•  » » 7 weeks ago, # ^ |   0 i dont have a solid proof, yet this passed.
•  » » 7 weeks ago, # ^ |   0 Do you mean that it is possible to create a Parker Rectangle of an odd order $>5$?
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 i am not sure of that, i meant my method would give some kind of compact parker square, i just need to verify whether if those conditions satisfy, if yes print it or else -1.
•  » » » » 6 weeks ago, # ^ |   0 Oh I see... could you share a link to your submission?
•  » » » » 6 weeks ago, # ^ |   0