PAPARAZI - Editorial

PROBLEM LINK:

Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest

Author: Yuriy Fedorov
Tester: Felipe Mota
Editorialist: Yuriy Fedorov

DIFFICULTY:

Easy-medium

PREREQUISITES:

Convex Hull

PROBLEM:

Given segments (1, A_1), (2, A_2) \ldots (n, A_n). You need to find the maximum number k such that there is a number i such that the segment between the points (i, A_i) and (i + k, A_{i + k}) does not intersect other segments

QUICK EXPLANATION:

Make the Convex Hull set of point (i, A_i). And answer - Maximum of their neighboring distances

EXPLANATION:

Make the convext Hull set of point (i, A_i).

Note that any pair of neighboring vertices is suitable for us.

Let the red lines be segments of the convex hull, it is clear that the green segments are higher, which means that what we found was clearly not a convex hull.
It is also clear that we are not interested in anything between the points of the convex hull, since the answer between them is clearly less.

So the answer is the maximum among all neighboring points on the convex hull

A convex hull can be constructed in O(n), since the points are initially sorted, but you can add, for example, the points (0, 0) and (n, 0) and simply copy the convex hull algorithm. As a result, the solution is O (n \cdot log(n)) or O(n), depending on the implementation

SOLUTIONS:

Setter's Solution
#include <iostream>
#include <vector>

using namespace std;

struct pt {
	int x, y;
	pt() {}
	pt(int a, int b) {x = a, y = b;}
};

long long operator*(pt a, pt b) {
	return (long long) a.x * b.y - (long long) a.y * b.x;
}

pt operator-(pt a, pt b) {
	return pt(a.x - b.x, a.y - b.y);
}

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	vector<pt> ch = {pt(a[0], 0), pt(a[1], 1)};
	int ans = 1;
	for (int i = 2; i < n; ++i) {
		pt now = pt(a[i], i);
		while (ch.size() > 1 && (now - ch[ch.size() - 2]) * (ch[ch.size() - 1] - ch[ch.size() - 2]) >= 0)
			ch.pop_back();
		ans = max(ans, i - ch.back().y);
		ch.push_back(now);
	}
	cout << ans << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	while (t--)
		solve();
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = readIntLn(1, TEN(4));
	int sum_n = 0;
	while(t--){
		int n = readIntLn(1, 5 * TEN(5));
		vector<int> xs;
		for(int i = 0; i < n; i++){
			int x;
			if(i + 1 == n) x = readIntLn(1, TEN(9));
			else x = readIntSp(1, TEN(9));
			xs.push_back(x);
		}
		using pt = pair<long long, long long>;
		auto cross2 = [&](pt a, pt b){ return a.first * b.second - a.second * b.first; };
		auto cross3 = [&](pt a, pt b, pt c){
			a.first -= b.first; c.first -= b.first;
			a.second -= b.second; c.second -= b.second;
			return cross2(a, c);
		};
		int ans = 0;
		vector<pt> at;
		for(int i = 0; i < n; i++){
			while(at.size() >= 2 && cross3(at[at.size() - 2], at[at.size() - 1], (pt){xs[i], i}) >= 0) at.pop_back();
			if(!at.empty()){
				int d = i - at.back().second;
				ans = max(ans, d);
			}
			at.push_back((pt){xs[i], i});
		}
		cout << ans << '\n';
	}
	return 0;
}
6 Likes

I implemented it without Convex Hull, here’s the submission’s link

4 Likes

My Solution without using Convex Hull :
Solution: 43661401 | CodeChef

Edit: or maybe I unknowingly used a convex hull. I implemented it using a stack and turns out a convex hull is also formed using a stack :sweat_smile:

2 Likes

Using line geometry Paparazi

can u elaborate ur solution approach .

Yeah me too used a stack as well :slight_smile:

Paparazi in python Same approach :smile:

Has anyone solved this by comparing subsequent slopes(gradient) ?

bro isn’t the time complexity of your code N2,

Yeah, even I feel the same. The time complexity is O(N^2). How did it pass all test cases in no time? :thinking:

1 Like

Alternate approach, without hull-

  1. Start at rightmost point, lets for sake of simplicity have 10 points, p1-p10

  2. Calculate recline of p10 to p9-p1 , here recline is (pa-pb)/dist between them
    e.g between p10=3 and p5=8 = (8-3)/5= +1, also sign does matter so pb always is point from which we are computing recline

  3. Now fun stuff, max of recline for p10 to (p9-p1) gives the max distance that is visible from that given spot, also in case of tie save the max distance one, i.e if recline of p10-p5 is 1 and p10-p3 is 1 then we save distance as 7.

  4. Jump to Pb-dist and repeat, also if Pb is at index less than dist no need to jump forward

  5. Java function - taking input array and n as argument-
    private int maxView(int a[],int n)
    {

     int res=1;
     int d[]=new int[n];
     for (int i = a.length-res;i>=res;) 
     {
     	double maxRec=Integer.MIN_VALUE;
     	int dist=0;
     	for (int j = 0; j < a.length-(a.length-i); j++) 
     	{
     		double rec=a[i-j-1]-a[i];
     		rec/=(j+1);
     		if(rec>=maxRec)
     			{dist=j+1;
     			maxRec=rec;}
     			
     	}
     	if(dist>res)
     		res=dist;
     	i-=dist;
     }
     
     return res;
    

    }

  6. Put function in fancy fast reader, without using fancy I/o it passes all test cases in 0.36 sec in java and with it in just 0.20 sec

Solution link- CodeChef: Practical coding for everyone

2 Likes

I have written similar code with N2 time complexity but it passed only subtask 1 and 2 as expected.
this is the submission link- CodeChef: Practical coding for everyone

I just copied this part and analyzed it.

while(i<n-1)
  {
    double slope=LLONG_MIN,t;
    int k=i+1; // Breakpoint 1
    rep(j,i+1,n)
    {
      t=((double)a[j]-a[i])/(j-i);
      if(t>=slope)
      {
        slope=t;
        k=j; // Breakpoint 2
      }
    }
    ans=max(ans,k-i);
    i=k; // Breakpoint 3
  } 

The time complexity is not O(N^2). It is O(N). Just look at the breakpoints I marked. We miscalculated the time complexity as O(N^2)

I also solved it in similay way , i think what we did is a special case of Graham’s scan.

please tell me what is wrong with my code CodeChef: Practical coding for everyone

one of friend solved it , in cpp

Can you please share his code?

please tell why my code is giving WA CodeChef: Practical coding for everyone
I simply iterated from left to right and checked if the next slope is greater than present one(i.e moving anti-clockwise). Else mark the previous one as the pole. Then in the end found the maximum.

@harry_shitt , bro i tried to debug your code , but i don’t know how to find convex hull ( i.e convex hull implementation ) so , i wasn’t able to do it. But , one thing in your code at line 37 , distSq is returning int , but the difference of x can be 10^5 so square can go upto 10^{10} which was too big for int. did you handle this case ?? and also did you handle all the other integer overflow cases , like in orientation ??

Here is the code.