PRLADDU-Editorial

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

DIFFICULTY:

Easy

PREREQUISITES:

ad-hoc, basic math

PROBLEM:

Given equal number of red (villager) and blue (dinosaur) points on a straight line (multiple points can share the same location), join each red point with a unique blue point by a line such that the sum of lengths of all lines is minimum.

EXPLANATION:

We first compute the lower bound on the total length on lines, and then show that the lower bound is in fact achievable.

Lower Bound on the Total Length:

Suppose we pick a point p on the line which does not coincide with any of the red or blue points, now let us find out the minimum number of lines that will pass through this point in any arrangement.

Let us say that there are r red points and b blue points on the left of point p, then there can be two cases:

  1. r >= b. This means we have (r - b) extra red points to the left of p, these points can only be connected to the blue points on the right of p. Hence, there will be at least (r - b) lines that will cross the point p, and will join the blue points on the right of p.
  2. r < b. In this case at least (b - r) lines will cross the point p, and will join red points on the right of p.

In other words at least |r - b| lines will cross the point p, which is the absolute difference between the red and blue points on the left of p. Now, we can consider all intervals between two consecutive point locations, and find the minimum number of lines containing these intervals.

In the problem we are given an array D[], such that if D[i] is non-negative that means there are D[i] red points at (i, 0), otherwise there are -D[i] blue points at (i, 0).

Now consider the interval between the points (i, 0) and (i + 1, 0). Based on the above observation, it can be seen that there will at least |D[1] + D[2] + … + D[i]| lines crossing this interval (Note that D[i] values are signed, hence their sum computes the difference between red and blue points).

Minimum length of lines = \Sum (minimum number of lines crossing the interval [(i, 0), (i + 1, 0)]), where the sum goes over i from 1 to (N - 1), N being the size of array D.

The following pseudocode can compute this bound in linear time.

int64_t bound(int *D, int N) {
	int64_t ans = 0;
	int64_t curr = 0;
	
	for (int i from 1 to N) {
		curr += D[i];
		ans += abs(curr);
	}
	return ans;
}

Lower Bound is Achievable:

Now we show that the lower bound computed in the above section is in fact achievable.

We use the following strategy to create lines: Start from the leftmost location (1, 0) and create |D[1]| active lines with source either red (if D[i] >= 0), or blue (if D[i] < 0), we extend these active lines to the right. Each time we encounter a location containing red or blue points, we either start more active lines or stop some of the active lines, using the following rules.

  1. If the active lines have red (blue) sources, and the encountered points are also red (blue), then we start more active lines with source red (blue).
  2. If the active lines have red (blue) sources, and we encountered blue (red) points, we will close as many active lines as possible by joining them to the encountered blue (red) points (hence, all closed lines will join a red and a blue point). If the number of encountered points is less than the active lines, we will still have active lines with red (blue) source, which will go further right. On the other hand, if the number of blue (red) points is higher than the number of active lines, then all active lines will be closed, and we might need to start new active lines with blue (red) sources, if some of the blue (red) points are unmatched.

It is easy to see that at any point the number of active lines is the absolute difference between the red and blue points encountered, which was in fact the minimum number of lines crossing a point. This means the lower bound is in fact achievable.

Time Complexity:

O (N)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.
Tester’s solution will be put up soon.

3 Likes

what a cool question 'twas.

That feeling when your solution is exactly the same as author’s solution! :slight_smile:

can we use backtrack for this purpose??

Hello all,

First of all kodoos to the problem setter for this interesting problem and interesting story too and editorialist for nice explanation.

I solved this problem with the same observation but way i solved it is more intutive i think .

Here is what i did .

I kept too pointers one is for positive and other is for negative. I iterate both the pointers till i find the first positive (>0 )and first negative( < 0 ) element. As soon as i get first positive and first negative i make either positive element zero or negative element zero (depending upon the abs(A[negative] >= A[positive])) or (abs(A[negative] < A[positive]) and answer is updated depending upon the difference.

Here is code fragment.

 int pos=1,neg=1;

	ll ans=0;
	while(neg<=n){
	
		while(neg<=n&&arr[neg]>=0){
			neg++;
		}

		while(pos<=n&&arr[pos]<=0){
			pos++;
		}

		if(neg<=n&&pos<=n){
			if(abs(arr[neg]) <= arr[pos]){
				arr[pos]-=abs(arr[neg]);
				ans += 1LL*abs(pos-neg)*abs(arr[neg]);
				arr[neg] = 0;
			}else{
				ans += 1LL*(abs(pos-neg))*arr[pos];
				arr[neg] += arr[pos];
				arr[pos] = 0;
			}
		}
	}

if you are still not clear with the idea feel free to ask doubts.

2 Likes

@djdolls I tried to solve this problem but was getting WA everytime… please tell me where I am wrong???/
Solution is Here http://www.codechef.com/viewsolution/5053587

I think this solution is way more easy to grasp and understand.

I did the same thing but it is showing TLE. :confused:

that is the most unintuitive answer to an easy solution i have ever read! :confused:

1 Like

Please provide test cases for which my code fails. I use the same logic as above, but my code is a little lengthy.
http://www.codechef.com/viewsolution/5477629

Your code will fail when N=10^5 and D[0]=-10^4, D[1]=D[2]=…D[99998]=0, D[99999]=+10^4. :slight_smile:

answer to your case will be 10^9, and i was using ‘int’ data type to represent this value. I think int can display this value. Anyways, I changed it to long long int now. Still I am getting WRONG ANSWER.
http://www.codechef.com/viewsolution/5479279

Try N=10 and D[i] = {-1 0 0 0 0 1 -1 0 0 1}.

Your code gives 10 as the output. Answer should be 8 :slight_smile:

thnx for the help.

1 Like

where am i wrong ?..please tell!

https://www.codechef.com/viewsolution/11568550

Where did I went wrong? submission here

Every help will be appreciated.

my other submissions

P.S. I tried doing this via two pointers approach and I already considered the testcase where answer could be more than range of int.
Please provide some testcase if possible.
Thanks in advance.

:smiley: