SOPC014 Editorial

PROBLEM LINK:

Practice
Contest

Author: Shriram Chandran
Editorialist: Shriram Chandran

DIFFICULTY:

Easy

PREREQUISITES:

Math.

PROBLEM:

Given an input N find a maximal cardinal set of lattice points in the square formed between (0,0), (0,N), (N,0) and (N,N) such that the Manhattan distance between any two of them is at least N.

EXPLANATION:

Let us ignore the border line for the time being.

Consider the space inside the square. Let us divide this into four different regions by a line along the center in the horizontal and vertical directions.

Now assume that the answer is greater than 4. Thus, by Pigeon Hole Principle, we obtain that there is at least one region with more than one point. But, since the dimension of each small region is N/2 * N/2, the Manhattan distance between those two points will be less than 2*N/2 = N, which is a contradiction.

Thus, the answer is always less than or equal to 4.

Now for even N alone, we observe that on adding corner points, you can take the centre (N/2,N/2) and make 5 points with the 4 corners of the square.

Thus the optimal solution has 4 points for all odd N and 5 for all even N.

All correct answers have been awarded AC verdict.

SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
void solve()
{
    int n;
    cin>>n;
    vector<pair<int,int>> ans;
    ans.push_back(make_pair(0,0));
    ans.push_back(make_pair(0,n));
    ans.push_back(make_pair(n,0));
    ans.push_back(make_pair(n,n));
    if(n%2==0)
        ans.push_back(make_pair(n/2,n/2));
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
        cout<<ans[i].first<<" "<<ans[i].second<<endl;
}
 
int main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
} 
1 Like