CDOUT4-Editorial

editorial
1

PROBLEM LINK

Practice

Contest

Author: Md Majid Jahangir

Tester : Md Majid Jahangir

Editorialist: Md Majid Jahangir

DIFFICULTY:

Easy

PREREQUISITIES:

Implementation

PROBLEM:

Piyush is a passionate gardener and has a very big garden at his home. There are N flower pots in his garden arranged in a single queue which are numbered N1, N2, N3, N4…Now, Piyush wants to arrange these flowerpots in an ascending order on the same queue on the basis of the numbers on them. But then he realized he is gaining weight and decided to use this flowerpot arrangement task as a workout. So, he modified the task a bit. He will arrange the flowerpots in ascending order but he will place the flowerpots in such a way that he has to walk more to place them in their correct position. Now he wants to know the longest distance he covered while placing a flowerpot. Piyush has to pick a flowerpot and place it in the longest possible position in one chance. He doesn’t want to pick up a flowerpot twice.

EXPLANATION:

The problem is very easy if there are no repetition of numbers in the array. We have to just sort the array and then find the number whose difference between the initial position and final position is maximum. We can use a 2D array of size [N][6]. The first column will hold the initial position of the number and the second column the position in the sorted arrangement.

But the above won’t work if there is repetition of numbers.

In case of repetition of numbers, store the first and last occurrence each and every number of the original unsorted arrangement. Also maintain a count of each and every number. Then sort the arrangement in ascending order.

If a number is present only once, then the maximum distance covered by the flowerpot with the respective number is the difference in it’s position in the initial unsorted arrangement and sorted arrangement.

In case of multiple occurrence of a number, the maximum displacement will be among the following two options

  1. (Last occurrence position in unsorted array)-(First occurrence position in sorted array)
  2. (First occurrence position in unsorted array)-(Last occurrence position in sorted array)

lets consider the array- 5, 4, 5 ,3, 2; the sorted arrangement is 2, 3, 4, 5, 5;
In this case, the maximum displacement will be option 2 of the above.
lets consider the array- 5, 4, 3 ,2, 2, 2; the sorted arrangement is 2, 2, 2, 3, 4, 5;
In this case, the maximum displacement will be option 1 of the above.

Complexity is O(n).

C++ Code:

#include<cstdio>
#include<algorithm>

using namespace std;

int dist[100001][7];
int num[100001];

void test();

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		test();
	}
	return 0;
}

void test()
{
	int n,i,present,m=0,temp1,temp2;
	scanf("%d",&n);
	for(i=0 ; i<100001 ; i++)
	{
		dist[i][0]=-1;
		dist[i][8]=0;
	}
	for(i=0 ; i<n ; i++)
		scanf("%d",&num[i]);
	for(i=0 ; i<n ; i++)
	{
		if(dist[num[i]][0]==-1)
		{
			dist[num[i]][0]=i;
			dist[num[i]][9]=i;
			dist[num[i]][10]++;
			continue;
		}
		dist[num[i]][11]=i;
		dist[num[i]][12]++;
	}
	sort(num,num+n);
	present=num[0];
	i=0;
	while(i<n)
	{
		if(dist[present][13]>1)
		{
			temp1=dist[present][14]-i;
			temp2=dist[present][0]-(i+dist[present][15]-1);
			if(temp1<0)
				temp1*=-1;
			if(temp2<0)
				temp2*=-1;
			if(max(temp1,temp2) > m)
				m=max(temp1,temp2);
			i=i+dist[present][16];
			present=num[i];
			continue;
		}
		if(dist[present][0]-i > m)
			m=dist[present][0]-i;
		i++;
		present=num[i];
	}
	printf("%d\n",m);
}