Max number of disc intersects

[frek]

The task says:
We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].

We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).

The figure below shows discs drawn for N = 6 and A as follows:
https://imgur.com/SC78zxT
A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0


There are eleven (unordered) pairs of discs that intersect, namely:

discs 1 and 4 intersect, and both intersect with all the other discs;
disc 2 also intersects with discs 0 and 3.
Write a function:

int solution(vector<int> &A);

that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Given array A shown above, the function should return 11, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [0..2,147,483,647].

I wrote this correct but not very efficient algorithm with time between O(n log n) and O(n ^ 2):

int solution(std::vector<int>& A) {
	size_t count{ 0 };

	for (size_t i = 0; i < A.size(); ++i)
		for (size_t j = i + 1; j < A.size(); ++j)
			if (A[i] + A[j] >= j - i)
				++count;

	if (count > 10'000'000)
		return -1;
	return count;
}

int main()
{
	std::vector A{ 1, 5, 2, 1, 4, 0};
	std::cout << solution(A) << '\n'; // 11

	return 0;
}

One hint is sorting (to get an O(n log) time), but that doesn't seemingly work well. See:
A: { 1, 5, 2, 1, 4, 0} return value: 11. Sorted array: { 5, 4, 2, 1, 1, 0}
B: { 1, 5, 2, 1, 0, 4} return value: 13. Sorted array: { 5, 4, 2, 1, 1, 0} (the same)

What I need, as usual, is only a hint, not code.

[jonnin]

it will run a little faster without the if.
just say count += (A[i] + A[j] >= j - i);

why did sorting not work? You need to know the original position if you sort, you lost the J value. You must track that somehow.

[lastchance]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution( const vector<int> &A )
{
   vector<pair<int,int>> endsOfIntervals;                      // Store the start and end positions of intervals 
   for ( int J = 0; J < A.size(); J++ )                      
   {
      endsOfIntervals.push_back( { J - A[J], +1 } );
      endsOfIntervals.push_back( { J + A[J], -1 } );
   }
   sort( endsOfIntervals.begin(), endsOfIntervals.end() );     // O(N log N)   

   vector<int> numStarted(2,0);    // Number of intervals started up to and including current position ([0] is a blank)
   vector<int> numEnded(2,0);      // Number of intervals ended   up to and including current position ([0] is a blank)     
   int prev = endsOfIntervals[0].first;
   for ( auto pr : endsOfIntervals )                         
   {
      if ( pr.first != prev )                                  // New position
      {
         numStarted.push_back( numStarted.back() );
         numEnded.push_back  ( numEnded.back()   );
         prev = pr.first;
      }
      ( pr.second > 0 ? numStarted : numEnded ).back()++;
   }

   int counter = 0;
   for ( int j = 1; j < numStarted.size(); j++ )
   {
      int numStart = numStarted[j] - numStarted[j-1];             // number of intervals starting at this point
      counter +=  numStart * ( numStarted[j] - numEnded[j-1] )    // new starts in an interval
                - numStart * ( numStart + 1 ) / 2;                // don't count self or double-count pairs
      if ( counter > 10000000 ) return -1;
   }

   return counter;
}

int main()
{
   cout << solution( { 1, 5, 2, 1, 4, 0 } ) << '\n';
   cout << solution( { 1, 5, 2, 1, 0, 4 } ) << '\n';
}

11
13

frek wrote:

I wrote this correct but not very efficient algorithm with time between O(n log n) and O(n ^ 2):

Your scheme is O(n²)

[frek]

I have been too busy recently.

Your scheme is O(n2)

j doesn't start from beginning there.
I didn't look at your code well, just like you that didn't look at my post when I clearly said I needed a hint not code! :(

Here're an O(n) and then O(n log n) solutions to the task.

int solution( const vector<int> &A ) {

        size_t result{ 0 }, sz { A.size()};
	std::vector<int> dps(sz,0);
	std::vector<int> dpe(sz,0);

	for (size_t i = 0; i < sz; i++)
	{
		dps[i > A[i] ? i - A[i] : 0]++;
		dpe[sz - 1 - i > A[i] ? i + A[i] : sz - 1]++;
	}

	int t = 0;
	for (size_t i = 0; i < sz; i++)      Solution #2
	{
		if (dps[i] > 0)
		{
			result += t * dps[i];
			result += dps[i] * (dps[i] - 1) / 2;
			if (10000000 < result)
				return -1;
			t += dps[i];
		}
		t -= dpe[i];
	}
	return result;
}

int solution(std::vector<int>& A) {
	std::vector<long long> lBond, rBond, cntArr;
	for (size_t i = 0; i < A.size(); ++i) {
		lBond.push_back(i - A[i]);
		rBond.push_back(i + A[i]);
	}

	std::sort(lBond.begin(), lBond.end());
	//  Solution #3
	for (size_t i = 0; i < rBond.size(); ++i) {
		auto upper = std::upper_bound(lBond.begin(), lBond.end(), rBond[i]);
		upper != lBond.end() ?
			cntArr.push_back(std::distance(lBond.begin(), upper) - 1)
			: cntArr.push_back(lBond.size() - 1);
	}

	for (size_t i = 0; i < cntArr.size(); ++i)
		cntArr[i] -= i;

	size_t res = std::accumulate(cntArr.begin(), cntArr.end(), 0);
	return  res > 10'000'000 ? -1 : res;
}

Here's also a video about the solution which seems to be talking about it using simple language but sadly still I can't figure it out how the solution is achieved!! :( https://youtu.be/NYjnoZulqrQ
Do you have a way to tell and help me to understand how the solution has been discovered? I can't get it how the developer has arrived to the solution which works as expected!

[lastchance]

frek wrote:

Your scheme is O(n2)
j doesn't start from beginning there.

You do EXACTLY (1/2)(N-1)N loops. That is O(N²).
(N-1)+(N-2)+...1 =(N-1)N/2

frek wrote:

I didn't look at your code well

That is a shame.

frek wrote:

just like you that didn't look at my post when I clearly said I needed a hint not code!

Sometimes it is necessary to actually code it to see if your ideas work. And once the code is written ...

frek wrote:

when I clearly said I needed a hint not code!

But, nevertheless, you still went to the internet ... to download some code!

frek wrote:

needed a hint not code!

Well, they gave you code ... and a U-bend YouTube video ... and you still didn't get it. So I don't think a hint would have got you far.

[frek]

(N-1)+(N-2)+...1 < N+N+...N in fact and effect.
I can provide you with answers to all your comments above and assure you why you're wrong but let's pick a shorter route and get it straight. I WILL NEVER LOOK AT YOUR CODE WHEN I'D ALREADY MENTIONED THAT I ONLY NEED HINTS.
I still think of you as a good guy due to your previous helps but please stop posting code while I don't need it.
I just like myself to get through the challenge. Afterwards when it's time to code I myself mention that and we will compare our codes. That's better.

Now does any one have an answer to the question I asked in the prior post?

[keskiverto]

On intersection, which of these do intersect?

A[0] = 1
A[1] = 0
A[2] = 1
A[3] = 1

[lastchance]

On intersection, which of these do intersect?

A[0] = 1
A[1] = 0
A[2] = 1
A[3] = 1

"Intersection" is effectively answered by what happens along the x axis.

Interval 0 is the closed interval [-1,1]
Interval 1 is the point x=1
Interval 2 is the closed interval [1,3]
Interval 3 is the closed interval [2,4]

So:

Intervals 0 and 1 intersect at the single point x=1
Intervals 0 and 2 intersect at the single point x=1
Intervals 1 and 2 intersect at the single point x=1
Intervals 2 and 3 overlap from x=2 to x=3

The answer in that case would be 4 pairs. (Which all codes get.)