PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Jay Sharma
Tester: Riley Borgard
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Geometry, Maths
PROBLEM:
You are given a plate of dimension M \times M. There are N germs such that each germ lies at a point with integer coordinates within this plate and no two germs lie at the same point. But the exact location of the germs is unknown. Each germ has a unique integer ID between 1 and N.
Your task is to sanitize this plate, i.e. make it germ-free. Each germ requires 1 ml of sanitizer to be killed and you can afford only N ml of sanitizer. However, you also have a germ sensor that works as follows -
It sends a laser beam of light along a straight line A\cdot x+B\cdot y=C and returns two things:
- The ID of the germ having the shortest perpendicular distance to this line. If there are multiple such germs, any of them may be chosen.
- The distance of this germ from the line multiplied by \sqrt{A^2+B^2}.
You are allowed to use this sensor almost 2N times.You can use the sensor or apply sanitizer in any arbitrary order. Note that the sensor does not sense killed germs.
EXPLANATION:
Suppose that we only have a single germ in M \times M plate. How can we find the exact location of this germ? As every germ is denoted by 2 coordinates i.e. (m,n). That is we have two unknowns and hence the minimum equations needed to find the coordinates (m,n) is 2.
We are allowed to use the sensor two times, each time we use a sensor we output an equation of straight line A_1\cdot x+B_1\cdot y+C_1=0. As soon as we output the line we are given the perpendicular distance of the germ from the line multiplied by \sqrt{A_1^2+B_1^2} say d.
Can we find the equation of the perpendicular line that passes through the point (m,n) and has a distance of d units from the input line A_1\cdot x+B_1\cdot y+C_1=0? 
d= \frac{|A_1m+B_1n+C_1|}{\sqrt{A_1^2+B_1^2}}
As it is given that the coordinates of germs are always non-negative integer i.e. m and n are non-negative integers. Also, it is always possible to have A, B and C as non-negative integers, hence we can rewrite the above equation as:
where d is the perpendicular distance from the input line. Since we are given the perpendicular distance multiplied by \sqrt{A_1^2+B_1^2}. Hence multiplying by \sqrt{A_1^2+B_1^2} on both sides in the above equation we get:
Similarly, we will make a query for another line and will find the equation of the perpendicular lin i.e.
Now by equation (i) and (ii) we can easily find the coordinates (m,n) i.e. the exact location of germ. As soon as we find the location of the germ we would kill that germ by applying sanitizer at that coordinate.
What happens if we query two parallel lines here?
- If we input two parallel lines then the perpendicular line that is drawn to these two parallel lines will be the same. Hence we will get only a single equation of a line for point (m, n). Two unknowns and a single equation, hence we will be unable to find the exact location of germs in this case.
One way to make sure that we are always querying non-parallel lines is that the coefficients of x and y are co-prime i.e. gcd(A, B) =1.
Why does this work?
We know that parallel lines have the same slope i.e - \frac{B}{A}. If we output such lines whose coefficients of x and y are co-prime, then we will be always getting unique slopes. Hence the lines will never be parallel to each other.
Now let us extend the problem for N germs. As the sensor doesn’t sense the killed germs, so as soon as we get two equations for the i^{th} germ, we will kill that germ. This ensures that for every germ we will be using the sensor exactly two times.
Hence we will use the sensor 2N times for N germs. Also, we will use N operations to kill all the N germs.
TIME COMPLEXITY:
O(N) per test case
SOLUTIONS:
Setter
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
struct Equation
{
int a,b,d;
};
pair<int,int> solve(Equation p,Equation q)
{
int x = (p.d*q.b-p.b*q.d)/(p.a*q.b-p.b*q.a);
int y = (p.d*q.a-p.a*q.d)/(p.b*q.a-p.a*q.b);
return make_pair(x,y);
}
int32_t main()
{
int tt=1;
cin >> tt;
while(tt--)
{
int n,m;
cin >> n >> m;
vector<Equation> info[n];
bool done = false;
for(int a=1;a<=128;a++)
{
for(int b=1;b<=128;b++)
{
if(gcd(a,b)!=1)
continue;
cout << "1 " << a << " " << b << " 0" << endl;
int u,d;
cin >> u >> d;
u--;
Equation q;
q.a = a;
q.b = b;
q.d = d;
if(info[u].size()>0)
{
Equation p = info[u][0];
pair<int,int> solution = solve(p,q);
cout << "2 " << solution.first << " " << solution.second << endl;
int v;
cin >> v;
if(v==1)
{
done = true;
break;
}
}
else
info[u].push_back(q);
}
if(done)
break;
}
}
return 0;
}
Tester
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
pair<int, ll> ask(int a, int b, int c) {
cout << 1 << ' ' << a << ' ' << b << ' ' << c << endl;
int u; ll d;
cin >> u;
if(u == -1) exit(0);
cin >> d;
return {u, d};
}
void clean(int x, int y) {
cout << 2 << ' ' << x << ' ' << y << endl;
int v;
cin >> v;
if(v == -1) exit(0);
}
void solve() {
int n, m;
cin >> n >> m;
map<int, ll> ma, mb, md;
rep(a, 1, 128) rep(b, 1, 128) {
if(n == 0) return;
if(gcd(a, b) != 1) continue;
int u; ll d;
tie(u, d) = ask(a, b, 0);
if(ma.count(u)) {
int a2 = ma[u], b2 = mb[u]; ll d2 = md[u];
ma.erase(u);
mb.erase(u);
md.erase(u);
n--;
ll det = a * b2 - b * a2;
ll x = (b2 * d - b * d2) / det;
ll y = (-a2 * d + a * d2) / det;
clean(x, y);
}else {
ma[u] = a;
mb[u] = b;
md[u] = d;
}
}
assert(false);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
while(te--) solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n,m;
cin>>n>>m;
map<int,int> a,b,d;
for(int i=1;i<=128;i++)
{
for(int j=1;j<=128;j++)
{
if(__gcd(i,j)==1)
{
cout<<1<<" "<<i<<" "<<j<<" "<<0<<endl;
int u,dis;
cin>>u>>dis;
if(a.count(u))
{
int a1=a[u],b1=b[u],d1=-d[u];
int a2=i,b2=j,d2=-dis;
int den=a1*b2-a2*b1;
int x=(b1*d2-b2*d1)/den;
int y=(a2*d1-a1*d2)/den;
cout<<2<<" "<<x<<" "<<y<<endl;
int v;
cin>>v;
if(v==1)
return;
}
a[u]=i;
b[u]=j;
d[u]=dis;
}
}
}
}
int32_t main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}