# Cell Shell Solution Codechef

Page Contents

## Cell Shell Solution February Challenge 2021

There is a checkered field with 105105 rows (numbered 11 through 105105) and 105105 columns (numbered 11 through 105105). NN different cells in this field (numbered 11 through NN) are marked; for each valid ii, the coordinates of the ii-th marked cell are (xi,yi)(xi,yi).

Also See: February Long Challenge 2021 Solutions

A set of cells is suitable if it meets the following conditions:

• All marked cells belong to this set.
• For any two cells aa and bb belonging to this set, there is a path between them with length |xa−xb|+|ya−yb||xa−xb|+|ya−yb| which only visits cells in this set. Each pair of consecutive cells in a path must have a common side.

You need to find the smallest possible size of a suitable set of cells, as well as the number of sets with this smallest size. Since the number of sets may be very large, compute it modulo 109+7109+7.

### Input

• The first line of the input contains two space-separated integers NN and TT.
• NN lines follow. For each valid ii, the ii-th of these lines contains two space-separated integers xixi and yiyi.

### Output

• If T=0T=0, print a single line containing one integer ― the smallest size of a suitable set.
• If T=1T=1, print a single line containing two space-separated integers ― the smallest size of a suitable set and the number of sets with this size modulo 109+7109+7.

### Constraints

• 1≤N≤1051≤N≤105
• 0≤T≤10≤T≤1
• 1≤xi,yi≤1051≤xi,yi≤105 for each valid ii

• T=1T=1
• xi≤5xi≤5 for each valid ii
• yi≤4yi≤4 for each valid ii

Subtask #3 (60 points): original constraints

```6 1
3 3
4 3
1 1
5 4
5 2
2 2
```

```10 2
```

### Explanation

The two suitable sets with the smallest size 1010 are

## Solution

Program C++:

```#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int MAXN = 200010;
const int INF = 2147483600;
const int MAX = 100001;
const LL Mod = 1e9+7;

int N,T; int L[MAXN+1],R[MAXN+1],fa[MAXN+1];
struct data{ int x,y; data(int xx=0,int yy=0){x=xx; y=yy;} }mn[MAXN+1],mx[MAXN+1],q[MAXN*2+1];
bool cmpx(data a,data b){ return a.x<b.x; }
inline data Max(data a,data b){ return data(max(a.x,b.x),max(a.y,b.y)); }
inline data Min(data a,data b){ return data(min(a.x,b.x),min(a.y,b.y)); }
inline int find(int x){ return (fa[x]==x?x:(fa[x]=find(fa[x]))); }
inline void merge(int x,int y){
x=find(x),y=find(y);
//cout<<"mgt:"<<x<<" "<<y<<endl;
if(x==y) return ; fa[y]=x;
mx[x]=Max(mx[x],mx[y]);
mn[x]=Min(mn[x],mn[y]); return ;
}
inline void mergeX(int l,int r){
//cout<<"mergeX:"<<l<<" "<<r<<endl;
for(int i=l,last;i<r;i=last+1){
last=mx[find(i)].x;
if(last<r) merge(last,last+1);
} return ;
}
inline void mergeY(int l,int r){
//cout<<"mergeY:"<<l<<" "<<r<<endl;
for(int i=l,last;i<r;i=last+1){
last=mx[find(i+MAX)].y;
if(last<r) merge(last+MAX,last+1+MAX);
} return ;
}
int top,sta[MAXN+1];
inline void Merge(){
for(int i=1;i<=2*MAX;i++) fa[i]=i;
for(int i=1;i<=MAX;i++) mn[i]=data(i,INF),mx[i]=data(i,-INF);
for(int i=1;i<=MAX;i++) mn[i+MAX]=data(INF,i),mx[i+MAX]=data(-INF,i);
for(int i=1;i<=MAX;i++) L[i]=INF,R[i]=-INF;
for(int i=1;i<=N;i++) L[q[i].x]=min(L[q[i].x],q[i].y),R[q[i].x]=max(R[q[i].x],q[i].y); top=0;
for(int i=1;i<=MAX;i++){
if(L[i]<=R[i]){
//cout<<"sq:"<<L[i]<<" "<<R[i]<<endl;
int l=1,r=top,pos=top+1;
while(l<=r){
int mid=(l+r)>>1;
if(L[i]<=mx[find(sta[mid])].y) pos=mid,r=mid-1;
else l=mid+1;
} if(pos>top){
mergeY(L[i],R[i]);
merge(L[i]+MAX,i);
sta[++top]=i;
} else{
while(top>pos){
data A=mn[find(sta[top-1])],B=mx[find(sta[top])];
mergeX(A.x,B.x); mergeY(A.y,B.y); --top;
}
int lt=mn[find(sta[top])].y,rt=mx[find(sta[top])].y;
int b=mn[find(sta[top])].x;
mergeX(b,i); mergeY(min(lt,L[i]),max(rt,R[i]));
}
}
} return ;
} LL ans,ans2;
int L2[MAXN+1],R2[MAXN+1];
LL inv[MAXN+1],ifac[MAXN+1],fac[MAXN+1];
inline void Count(int l,int r){
//cout<<"count:"<<l<<" "<<r<<endl;
L2[r]=L[r]; R2[r]=R[r];
for(int i=r-1;i>=l;i--) L2[i]=min(L2[i+1],L[i]),R2[i]=max(R2[i+1],R[i]);
for(int i=l+1;i<=r;i++) L[i]=min(L[i-1],L[i]),R[i]=max(R[i-1],R[i]);
for(int i=l;i<=r;i++){ ans+=min(R[i],R2[i])-max(L[i],L2[i])+1; //cout<<"x "<<i<<": "<<max(L[i],L2[i])<<" "<<min(R[i],R2[i])<<endl;
}
return ;
}
inline LL C(LL n,LL m){ if(n<m) return 0; return fac[n]*ifac[m]%Mod*ifac[n-m]%Mod; }
inline LL calc(data a,data b){
return C(abs(a.x-b.x)+abs(a.y-b.y),abs(a.x-b.x));
}

int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
inv[1]=ifac[0]=fac[0]=1;
for(int i=2;i<=2*MAX;i++) inv[i]=(Mod-(Mod/i)*inv[Mod%i]%Mod)%Mod;
for(int i=1;i<=2*MAX;i++) ifac[i]=ifac[i-1]*inv[i]%Mod,fac[i]=fac[i-1]*i%Mod;
for(int i=1;i<=N;i++){
} sort(q+1,q+N+1,cmpx);
if(q[1].y>q[N].y){
for(int i=1;i<=N;i++)
q[i].y=MAX-q[i].y+1;
} Merge();
//return 0;
ans=0,ans2=1;
for(int i=1;i<top;i++){
data A=mx[find(sta[i])],B=mn[find(sta[i+1])];
ans+=abs(A.x-B.x)+abs(A.y-B.y)-1;
ans2=ans2*calc(A,B)%Mod;
q[++N].x=A.x; q[N].y=A.y;
q[++N].x=B.x; q[N].y=B.y;
} top=0; sort(q+1,q+N+1,cmpx); Merge();
//cout<<"q:\n";
//for(int i=1;i<=N;i++) cout<<q[i].x<<" "<<q[i].y<<endl;
for(int i=1;i<=top;i++) Count(mn[find(sta[i])].x,mx[find(sta[i])].x);
if(T) printf("%lld %lld\n",ans,ans2);
else printf("%lld\n",ans);
return 0;
}```

Program Python:

```n = int(input())
i=10
while n%i!=0:
i=i-1
print(i)```