PROBLEM LINK:
Tester: Kasra Mazaheri
Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
There are N trees (numbered 1 through N) planted at distinct positions on a line; for each valid i, the position of the i-th tree is A_i.
A set of trees is beautiful if for each tree in this set (let’s denote its position by x), there is a tree at the position x−1 and/or a tree at the position x+1.
Kerim’s task is to plant some (possibly zero) trees in such a way that the resulting set of all planted trees (the initial N trees and those planted by Kerim) is beautiful. It is only allowed to plant trees at integer (possibly negative) positions. Find the minimum number of trees he needs to plant in order to achieve that.
DIFFICULTY:
Easy
CONSTRAINTS
1 \leq N \leq 10^5
EXPLANATION:
According to the task, each tree must have at least one tree adjacent to it (to the left or to the right) and this must apply also to the trees we plant.
First, let’s sort our trees in increasing order of positions.
Let’s iterate through our trees one by one (from left to right). For each tree, let’s check if there’s a tree exactly to the left of it. If there’s one, then we don’t need to plant any (because the current tree has one adjacent to it so it’s not violating the condition). Assume the current tree position is equal to x.
If there’s no tree to the left of it, then we must plant one to the right (unless a tree exists to the right). This is optimal because we are processing trees from left to right. Planting to the left would make the current tree satisfy the “beauty” condition. Planting to the right would do the same, and also provide the chance that the planted tree is adjacent to some tree to the right, specifically at position x+2. So always planting to the right in our case (when needed) is most optimal.
Check editorialist implementation for an easy code.
Complexity: O(N\,\,logN)
Editorialist solution
#include<bits/stdc++.h>
using namespace std;
int T , n , K , arr[1<<20];
string str;
int main(){
cin>>T;
while(T--){
cin>>n;
for(int j = 1 ; j <= n ; j++)
scanf("%d",&arr[j]);
sort(arr+1 , arr+1+n);
set < int > S;
for(int j = 1 ; j <= n ; j++){
S.insert(arr[j]);
if(S.count(arr[j] - 1) == 0)
S.insert(arr[j] + 1);
}
cout<<S.size() - n<<endl;
}
}
Tester Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, q, A[N];
int main()
{
int SMN = 0;
scanf("%d", &q);
assert(1 <= q && q <= 1000);
for (; q; q --)
{
scanf("%d", &n);
assert(1 <= n && n <= 100000);
SMN += n;
for (int i = 1; i <= n; i ++)
scanf("%d", &A[i]), assert(1 <= A[i] && A[i] <= (int)(1e9));
sort(A + 1, A + n + 1);
for (int i = 1; i < n; i ++)
assert(A[i] < A[i + 1]);
int i = 1, c = 0;
while (i <= n)
{
bool f = 1;
while (i < n && A[i] == A[i + 1] - 1)
i ++, f = 0;
if (!f) {i ++; continue;}
c ++;
if (i < n && A[i] == A[i + 1] - 2)
{A[i] ++; continue;}
i ++;
}
printf("%d\n", c);
}
assert(SMN <= (int)(1e6));
return 0;
}
