#### 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 asa 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 witha 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 base[n];↵
for(int i=2;i<n;i++){↵
base[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(base[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>↵
↵
↵
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
↵
Finally, when I did manage to cook up solutions with
↵
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 $
↵
$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(
↵
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
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
for(int i=2;i<n;i++){↵
bas
}↵
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
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 $
↵
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>↵
↵
