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!
TriviaThe credit for us solving the problem in-contest goes to om_mittal7 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 $$$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$$$).
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/*
* 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[n];
for(int i=2;i<n;i++){
bas[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[i],bas[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;
}
TriviaAlthough 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 of order $$$\frac{n}{2}$$$, which can be constructed using a suitable construction algorithm (reference), 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 (vikram108, ParadigmShift, dhruvsomani).
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$$$.
ProofClearly, $$$\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$$$.
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.
ProofLet $$$(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$$$ 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/*
* 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;
}
Auto comment: topic has been updated by twoplusthree (previous revision, new revision, compare).
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.
i dont have a solid proof, yet this passed.
Do you mean that it is possible to create a Parker Rectangle of an odd order $$$>5$$$?
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.
Oh I see... could you share a link to your submission?
https://codedrills.io/submissions/985574