PROBLEM LINK:
Author: Naman Jain
Tester: Raja Vardhan Reddy
Editorialist: Rajarshi Basu
DIFFICULTY:
Easy
PREREQUISITES:
Implementation, Geometry
PROBLEM:
Given are N towers (1 \leq N \leq 2000) which are either of the following two forms:
- Type 0: A line segment between the points (x_i, 0) and (x_i, a_i), i.e. upwards from the floor.
- Type 1: A line segment between the points (x_i, H) and (x_i, a_i), i.e. downwards from the ceiling.
For each obstacle, you need to find the number of endpoints of other obstacles (not including itself) that are visible from its endpoint. Two endpoints are visible from each other if the line segment joining them does not intersect or touch any other obstacle.
QUICK EXPLANATION:
For each tower, go right, and maintain the minimum and maximum slopes possible for the next point. As we go right, the minimum permissible slope will increase, and the maximum will decrease. At each tower, calculate the slope, see if it’s permissible, update the maximums and minimums, as well as the answer. To maintain the slopes, maintain denominator and numerator, instead of slope in a double. Complexity: O(n^2).
DETAILED EXPLANATION:
I will elaborate on the solution in terms of step-by-step observations. But first and foremost, the input might not be sorted by x[i], hence let’s first sort it (by x[i]).
Also, as a clarification, when I talk about slope between two towers, I ALWAYS mean slope between the endpoints. In particular, slope between towers i and j necessarily means \frac{a[j]-a[i]}{x[j]-x[i]}.
Observation 1
N can go up to just 2000, hence we are looking for a O(n^2) solution probably.
Observation 2
Let’s say we want to figure out whether two towers, say i and j, are visible from each other. The key is to figure out if there is any tower k ( i < k < j) such that either of the two conditions is violated:
- if tower k is of type 0, then the slope of k and i less than i and j.
- if tower k is of type 1, then slope of k and i more than i and j.
Just implementing this search as stated takes O(n) time for every pair of tower. Since there are O(n^2) towers, total complexity comes down to O(n^3)
Observation 3
While computing whether tower i and j are mutually visible, instead of checking for each tower in (i,j) and finding which specific tower blocks visibility, it would have had sufficed if we had known:
- For all towers k of type 0 in range (i,j), what is the maximum slope for any pair of towers k and i.
- For all towers k of type 1 in range (i,j), what is the minimum slope for any pair of towers k and i.
Let these slopes be max and min. Let slope of tower i from j is slp. Towers i and j are visible from each other, as long as min < slp < max.
Observation 4
Let us fix one of the towers i. As we increase j, notice how the value of min always increases, and max always decreases. This can be explained by simple intuition. Any tower that was there for j_{prev} is still there for j_{curr} (j_{curr} > j_{prev}). Hence, the towers that contributed towards min and max are still there, and hence min can only increase, while max can only decrease. So, by just increasing j_{curr}, we can consider the slope of j_{curr} and i, update min and max if needed, without the need to again go over all the towers k \in (i,j_{curr}).
More explanation
For better intuition, think about the min as a line that is rotating anticlockwise, and the line with max slope as a line moving clockwise, as we go towards the right. The space between these lines constitutes our permissible region. If the new tower has its edge inside this space, its visible. But now, it also blocks our visibility region as we go further right. Hence, depending on the type of the tower, we either move our lower line upwards (ie, anticlockwise), or move down our upper line (ie, clockwise), thereby updating our permissible visible region.
Implementation 1
While calculating the answer for a particular tower, we don’t really need to go both left and right. Going in only one direction is enough. When we identify a valid tower j while iterating for the fixed tower i, we increase the answer for both i and j.
Implementation 2
An important part of the problem is how to maintain the slopes. If we try to maintain the slopes in doubles, we will have precision issues. Not good to handle
Instead, for each slope, we keep the numerator and denominator separately. The below code should explain.
code
#define llint long long int
llint num1 = 1443,denom1 = 24324; // random examples
llint num2 = 4342,denom2 = 134;
// bad code: has precision errors
double x1 = 1.0*num1/denom1;
double x2 = 1.0*num2/denom2;
if(x1 < x2){}`
// good code : no precision error
if(num1*denom2 < num2*denom1){}
Time Complexity
For each of the fixed towers i, we do a linear pass from [i+1,..., N] which takes O(N) time. Hence overall, for having to fix a total of N towers, we get a total time complexity of O(N^2).
QUICK REMINDERS:
Don’t keep debug print statements while submitting 
Oh, and don’t forget to use 64bit integers, since the multiplication while comparing fractions might give integers up to 10^{18}.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
return os << "(" << P.first << "," << P.second << ")";}
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define I insert
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define vi vector<int>
#define pii pair<int, int>
#define vpii vector< pii >
const int M = 2005;
int t[M], x[M], a[M];
ll cross(int p, int q, int r){
ll x1, y1, x2, y2;
x1 = x[q]-x[p]; y1 = a[q]-a[p];
x2 = x[r]-x[p]; y2 = a[r]-a[p];
return x1*y2 - y1*x2;
}
bool visible(int p, int q, int &lbi, int &ubi){
bool ret = true;
if(ubi != -1){
ll cr = cross(p, ubi, q);
if(cr<0){
if(t[q]==1) ubi = q;
}
else ret = false;
}
else{
if(t[q]==1) ubi = q;
}
if(lbi != -1){
ll cr = cross(p, lbi, q);
if(cr>0){
if(t[q]==0) lbi = q;
}
else ret = false;
}
else{
if(t[q]==0) lbi = q;
}
return ret;
}
#define all(i) i.begin(), i.end()
void solve(){
int H; cin>>H;
int N; cin>>N;
vpii ord;
bool smx=0;
for(int i=0;i<N;i++){
cin>>t[i]>>x[i]>>a[i];
ord.pb({x[i], i});
}
sort(ord.begin(), ord.end());
vi ans(N, 0);
for(int i=0;i<N;i++){
int p = ord[i].S;
int lbi = -1; int ubi = -1;
for(int j=i+1;j<N;j++){
int q = ord[j].S;
if(visible(p, q, lbi, ubi)){
ans[p]++; ans[q]++;
}
}
}
for(int i=0;i<N;i++)cout<<ans[i]<<" ";
cout<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
int T; cin>>T;
while(T--) solve();
}
Tester's Solution
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
int typ[2005],x[2005],a[2005],cnt[2005];
vii vec;
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int h,n,fl_max,fl_min,i,id1,id2,max_den,max_num,den,num,min_num,min_den,j;
cin>>h>>n;
vec.clear();
rep(i,n){
cnt[i]=0;
cin>>typ[i]>>x[i]>>a[i];
vec.push_back(mp(x[i],i));
}
sort(all(vec));
rep(i,n-1){
id1=vec[i].ss;
id2=vec[i+1].ss;
fl_max=0;
fl_min=0;
if(typ[id2]==0){
fl_max=1;
max_num=a[id2]-a[id1];
max_den=x[id2]-x[id1];
}
else{
fl_min=1;
min_num=a[id2]-a[id1];
min_den=x[id2]-x[id1];
}
cnt[id1]++;
cnt[id2]++;
f(j,i+2,n){
id2=vec[j].ss;
num=a[id2]-a[id1];
den=x[id2]-x[id1];
if(fl_max==1 && fl_min==1){
if(num*max_den>den*max_num && num*min_den<den*min_num){
cnt[id1]++;
cnt[id2]++;
}
}
else if(fl_max==1){
if(num*max_den>den*max_num){
cnt[id1]++;
cnt[id2]++;
}
}
else{
if(num*min_den<den*min_num){
cnt[id1]++;
cnt[id2]++;
}
}
if(typ[id2]==0){
if(fl_max==0){
fl_max=1;
max_num=a[id2]-a[id1];
max_den=x[id2]-x[id1];
}
else if(num*max_den>den*max_num){
max_num=a[id2]-a[id1];
max_den=x[id2]-x[id1];
}
}
else{
if(fl_min==0){
fl_min=1;
min_num=a[id2]-a[id1];
min_den=x[id2]-x[id1];
}
else if(num*min_den<den*min_num){
min_num=a[id2]-a[id1];
min_den=x[id2]-x[id1];
}
}
}
}
rep(i,n){
cout<<cnt[i]<<" ";
}
cout<<"\n";
}
return 0;
}
Editorialist's Solution
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define vv vector
using namespace std;
const int INF = 1e9;
const int MAXN = 1e5+5;
const ll MOD = 1e9 + 7;
ll fxp(ll a, ll b){
if(b == 0)return 1;
if(b%2 == 0){
ll c = fxp(a,b/2);
return (c*c)%MOD;
}
return (a*fxp(a,b-1))%MOD;
}
//#define data pair<pair<ll,ll>,pair<int,int> >
struct data{
int t;
int x;
int a;
int id;
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
ll h;
cin >> h >> n;
data arr[n];
FOR(i,n)cin >> arr[i].t >> arr[i].x >> arr[i].a,arr[i].id = i;
sort(arr,arr+n,[&](data d1,data d2){
return d1.x < d2.x;
});
int ans[n];
FOR(i,n)ans[i] = 0;
FOR(i,n){
ll num_up,num_down,denom_up,denom_down;
bool gotType0 = 0;
bool gotType1 = 0;
FORE(j,i+1,n-1){
ll h = arr[j].a - arr[i].a;
ll w = arr[j].x - arr[i].x;
bool posFromBelow = 0;
if(!gotType0)posFromBelow = 1;
else{
if(h*denom_down > w*num_down){ // means seeable
if(arr[j].t == 0)denom_down = w;
if(arr[j].t == 0)num_down = h;
posFromBelow = 1;
}
}
bool posFromAbove = 0;
if(!gotType1)posFromAbove = 1;
else{
if(h*denom_up < w*num_up){ // means seeable
if(arr[j].t == 1)denom_up = w;
if(arr[j].t == 1)num_up = h;
posFromAbove = 1;
}
}
if(posFromBelow and posFromAbove)ans[arr[i].id]++,ans[arr[j].id]++;
if(!gotType1 and arr[j].t == 1){
gotType1 = 1;
denom_up = w;
num_up = h;
}
if(!gotType0 and arr[j].t == 0){
denom_down = w;
num_down = h;
gotType0 = 1;
}
}
}
FOR(i,n)cout << ans[i] << " ";cout << endl;
}
return 0;
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 