ICPC Asia West Continent Final Contest 2023 — Problem A and E

Revision en7, by twoplusthree, 2024-04-13 13:13:59

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
Tags icpc, unofficial editorial, proofs, constructive algorithms, asia west

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English twoplusthree 2024-04-13 13:13:59 2 Tiny change
en6 English twoplusthree 2024-04-12 11:14:28 102 Fixed typos and other errors
en5 English twoplusthree 2024-04-11 23:15:10 0 Added tags (published)
en4 English twoplusthree 2024-04-11 23:11:44 769 Added trivia for 'E. Basic Vocabulary'
en3 English twoplusthree 2024-04-11 22:49:21 3797 Added trivia for 'A. Basic Vocabulary'
en2 English twoplusthree 2024-04-11 21:44:43 6395 Added 'E. Parker Rectange'
en1 English twoplusthree 2024-04-11 20:56:48 2826 Initial revision (saved to drafts)