Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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

Revision en5, by twoplusthree, 2024-04-11 23:15:10

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

Trivia

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,nb]b. Considering 2b1>n, what must be the constraint on b2 for (n)b1 to be a prefix?

Let nb1=x, then n=[1,x]b1. Note that x>0 since b1<n.

Thus we have,

n=[1,x,k digits]b2n=(bk+12+xbk2)+rn=(b2+x)bk2+r     (k>0,r<bk2)

Thus, (b2+x) is the quotient obtained on dividing n by bk2.

(b2+x)bk2n(b2+x+1)bk21

Now, we note that 1xb21, since x is a non-zero digit in base-b2. Therefore,

(b2+1)bk2n(2b2)bk21(1)

If there exists any b2, k satisfying the above inequality, then we can derive b1 as follows:

  • qnbk2
  • xqb2
  • b1nx

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)bk2n, which can be found in O(log(n)) by Binary Search. Since b22, 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,

(b2+1)b2n2b221

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.

2b221(b2+1+1)(b2+1)b223b230

which is true b24.

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 n20, we test solely for k=1 as described before and report the answer obtained.


Code

E. Parker Rectangle

Trivia

Given r+c=nc=nr. We assume WLOG that rc0<rn2.

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.

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)