ICPC Asia West Continent Final Contest 2023 — Problem A and E
Difference between en5 and en6, changed 102 character(s)
#### Motivation↵

A few weeks back I had the opportunity to attend the [ICPC Asia West Continent Finals 2023](https://codedrills.io/contests/icpc-asia-west-continent-final-contest-2023) along with my teammates [user:VS-Codes,2024-04-11] and [user:om_mittal7,2024-04-11], 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 a few days back..↵

Looking forward to your thoughts and suggestions!


## [A. Basic Vocabulary](https://codedrills.io/contests/icpc-asia-west-continent-final-contest-2023/problems/basic-vocabulary)↵

<spoiler summary="Trivia">↵
The credit for us solving the problem in-contest goes to [user:om_mittal7,2024-04-11] who noticed that there was exactly $\frac{1}{2}$ chance that any given $n$ would have $(n-1,2)$ as a valid solution. Thereafter he tried extrapolating the idea to few more cases, and we ended up coding the following algorithm (without proof):↵

For $b_2$ in $2, 3, \cdots 1000$ let $[d_k,d_{k-1}, \cdots, d_1,d_0]_{b_2}$ be the base-$b_2$ representation of $n$. If there exists $b_1>b_2$ such that $d_k \cdot b_1+d_{k-1}=n$ and $
b_1>d_k,d_{k-1}<b_1$, then $(b_1, b_2)$ is an answer. If nothing is found, print $-1$.↵

$1000$ was chosen as an arbitrarily high number that looked 'safe enough' (lol), Fortunately, the solution passed, leaving us relieved yet perplexed. However, when I tried later, I was completely stuck on how to prove its correctness.↵

It was only after I abandoned all previous ideas, and started from scratch with a completely new set of observations that I was able to chalk up the following proof, after which it became quite clear as to why this solution is correct. Sometimes a shift in perspective works wonders :-D↵

_Fun fact_: Brute forcing for values upto $10000$ revealed to me that ${1,2,3,4,5,8,11,19}$ were the only inputs in that range for which the answer was $-1$. This suspiciously small bound turns up quite organically in the proof, which is one of the reasons why math is so beautiful (Spoiler: These are also the **only** inputs with answer $-1$).↵
</spoiler>↵

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(
\sqrt{nn^{\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.↵

<br>↵

<spoiler summary="Code">↵
```c++17↵
/* ↵
 * author: twoplusthree ↵
 * created: 11.04.2024 20:24:53 ↵
 */↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
#define all(x) (x).begin(),(x).end()↵
using vi=vector<int>;↵
void solve(){↵
  int n;↵
  cin>>n;↵
  if(n>=20){↵
    int b;↵
    int low,hig,mid;↵
    low=2;↵
    hig=1e9+5;↵
    while(low<=hig){↵
      mid=(low+hig)/2;↵
      if((mid+1)*mid<=n){↵
        b=mid;↵
        low=mid+1;↵
      }else{↵
        hig=mid-1;↵
      }↵
    }↵
    assert(2*b*b
>-1>=n);↵
    int q=n/b;↵
    int x=q-b; assert(1<=x&&x<=b-1);↵
    cout<<(n-x)<<" "<<b<<"\n";↵
  }else{↵
    auto tobase=[](int x,int b)->vi{↵
      vi res;↵
      while(x>0){↵
        res.push_back(x%b);↵
        x/=b;↵
      }↵
      reverse(all(res));↵
      return res;↵
    };↵
    vi bas
e[n];↵
    for(int i=2;i<n;i++){↵
      bas
e[i]=tobase(n,i);↵
    }↵
    auto isprefix=[](vi& v1,vi& v2)->bool{↵
      int n=(int)v1.size();↵
      if((int)v2.size()<n){↵
        return false;↵
      }↵
      for(int i=0;i<n;i++){↵
        if(v1[i]!=v2[i]){↵
          return false;↵
        }↵
      }↵
      return true;↵
    };↵
    for(int i=2;i<n;i++){↵
      for(int j=2;j<i;j++){↵
        if(isprefix(bas
e[i],base[j])){↵
          cout<<i<<" "<<j<<"\n";↵
          return;↵
        }↵
      }↵
    }↵
    cout<<-1<<"\n";↵
  }↵
  return;↵
}↵
signed main(){↵
  ios::sync_with_stdio(false);↵
  cout.tie(nullptr);↵
  int tt=1;↵
  cin>>tt;↵
  for(int i=1;i<=tt;i++){↵
    //cout<<"Case #"<<i<<": ";↵
    solve();↵
  }↵
  return 0;↵
}↵
```↵
</spoiler>↵

---↵

## [E. Parker Rectangle](https://codedrills.io/contests/icpc-asia-west-continent-final-contest-2023/problems/parker-rectangle)↵

<spoiler summary="Trivia">↵
Although we were unable to solve this problem in-contest, we had managed to make the pivotal claim about the case when $n$ is odd (albeit without proof).↵

One possible solution to the problems is where the answer for even $n$ is any [Magic Square](https://en.wikipedia.org/wiki/Magic_square) of order $
n\frac{n}{2}$, which can be constructed using a suitable construction algorithm ([reference](https://mathworld.wolfram.com/MagicSquare.html)), which we unfortunately did not know at the time of the contest :(↵

However, a far simpler and arguably more elegant solution to the problem exists which was mainly inspired by the submission made by Team **cns_lena_chahiye_tha** ([user:vikram108,2024-04-11], [user:ParadigmShift,2024-04-11], [user:dhruvsomani,2024-04-11]).↵
</spoiler>↵

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$.↵

<spoiler summary="Proof">↵
Clearly, $\max(R_i)\geq\frac{S}{r}$ and $\min(C_j)\leq\frac{S}{c}$ $\implies \max(R_i)-\min(C_j)\geq S\cdot\frac{c-r}{rc}$↵

From the problem statement, $S\cdot\frac{c-r}{rc} \leq \lceil\frac{n}{2}\rceil$↵

Since all the elements of $M$ are *distinct*, we can say $S\geq \displaystyle\sum_{i=0}^{rc-1}i=\frac{(rc-1)\cdot rc}{2}$.↵

Hence, ↵
$$\frac{(rc-1)\cdot rc}{2}\cdot \frac{c-r}{rc} \leq \lceil\frac{n}{2}\rceil \implies \frac{(rc-1)(c-r)}{2} \leq \lceil\frac{n}{2}\rceil \implies \frac{(nr-r^2-1)(n-2r)}{2} \leq \lceil\frac{n}{2}\rceil$$↵

When $n=2m+1$,↵

$\frac{(2mr+r-r^2-1)(2m+1-2r)}{2} \leq m+1$↵

$\implies \frac{(2mr+r-r^2-1)(2m+1-2r)}{2} \leq m+1$↵

$\implies f(r)=2r^3-(6m+3)r^2+(4m^2+4m+3)r-(4m+3)\leq 0$↵

Studying the above function, we find that the curve first increases and then decreases in $0<r\leq \frac{2m+1}{2}$.↵

Putting $r=1$, we get $f(1)=4m^2-6m-1 >0 \ \forall m>1$↵

Putting $r=m$, we get $f(m)=m^2-m-3 >0 \ \forall m>2$↵

Hence, we can conclude that there does not exist any integral value of $r \in (0,\frac{n}{2}]$ such that the above condition is satisfied when $m>2$.$.↵
</spoiler>↵

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}$$<br>↵
$$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}$$<br>↵
$$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.↵

<spoiler summary="Proof">↵
Let $(A_{i_1j_1},B_{i_1j_1})=(A_{i_2j_2},B_{i_2j_2})$.↵

Hence,↵
$$i_1+j_1\equiv i_2+j_2 \pmod m \ ... (1)$$↵
$$2i_1+j_1\equiv 2i_2+j_2 \pmod m \ ... (2)$$↵

By $(2)-(1)$,↵
$$i_1\equiv i_2 \pmod m \implies j_1\equiv j_2 \pmod m$$↵

But,↵
$$0 \leq i_1,i_2,j_1,j_2 < m \implies i_1=i_2, \ j_1=j_2$$↵
</spoiler>↵

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$.↵

<br>↵

<spoiler summary="Code">↵
```c++17↵
/* ↵
 * author: twoplusthree ↵
 * created: 02.04.2024 01:30:38 ↵
 */↵
#include <bits/stdc++.h>↵
using namespace std;↵
//#define int long long↵
#define all(x) (x).begin(),(x).end()↵
using vi=vector<int>;↵
void solve(){↵
  int n;↵
  cin>>n;↵
  if(n&1){↵
    if(n==3){↵
      cout<<"1 2\n";↵
      cout<<"0 1\n";↵
    }else if(n==5){↵
      cout<<"2 3\n";↵
      cout<<"0 3 4\n";↵
      cout<<"5 2 1\n";↵
    }else{↵
      cout<<-1<<"\n";↵
    }↵
  }else{↵
    int nn=n/2;↵
    vector<vi> A(nn,vi(nn));↵
    for(int i=0;i<nn;i++){↵
      for(int j=0;j<nn;j++){↵
        A[i][j]=(i+j)%nn;↵
      }↵
    }↵
    vector<vi> B(nn,vi(nn));↵
    for(int i=0;i<nn;i++){↵
      for(int j=0;j<nn;j++){↵
        B[i][j]=(2*i+j)%nn;↵
      }↵
    }↵
    vector<vi> ans(nn,vi(nn));↵
    for(int i=0;i<nn;i++){↵
      for(int j=0;j<nn;j++){↵
        ans[i][j]=nn*A[i][j]+B[i][j];↵
      }↵
    }↵
    cout<<nn<<" "<<nn<<"\n";↵
    for(int i=0;i<nn;i++){↵
      for(int j=0;j<nn;j++){↵
        cout<<ans[i][j]<<" ";↵
      }↵
      cout<<"\n";↵
    }↵
  }↵
  return;↵
}↵
signed main(){↵
  ios::sync_with_stdio(false);↵
  cout.tie(nullptr);↵
  int tt=1;↵
  cin>>tt;↵
  for(int i=1;i<=tt;i++){↵
    //cout<<"Case #"<<i<<": ";↵
    solve();↵
  }↵
  return 0;↵
}↵
```↵
</spoiler>↵

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)