# Need help with Planting trees(DEADEND)

Someone help me out with planting trees. I got partial solution ( TLE ). With O(n) complexity.
https://www.codechef.com/viewsolution/28015723
I guess it’s due to the sort. Does it become O(n^2).
I tried inserting in vector instead of sorting repeatedly , using
a.insert(a.begin()+i+1,a[i] + 1)
but it gave me sigtstp error. So i decided to sort in every iteration.

You are traversing in while loop for N iterations,
and in each iteration you are sorting which takes NlogN time.
So your actual time complexity is : O( N * NlogN ) which is why you got tle.

1 Like

Yes, You’re right, It’s due to the sorting.

You can follow this simple technique to avoid extra sorting.

Explanation
1. Use an array with 2 extra index. say a[n+2]. and initiate with a[0] = -1, a[n+1]=1e11 so that after sorting it never changed their position.

2. Get input. ex.-  for (int i = 1; i <= n; i++) cin >> a[i];

3. Sort the array. ex.- sort(a, a + (n + 2));

4. Then check it’s beautiful or not. If beautiful then continue. Otherwise, increase counter and plant a tree at position pos+1 (Really! you don’t need to insert new item in a, just increase the i'th position by 1. For ex.- if a = {2, 4} then we just need a tree at position 3 to make it beautiful [We just increase our counter and tree’s position by 1 to achieve this] ) Code ex.-

for (register int i = 1; i <= n; i++) {
if (a[i] + 1 != a[i + 1] and a[i] - 1 != a[i - 1]) { // not beautiful
ans++;
a[i]++;
}
}

1. Print the counter. That’s all
Solution
#include <bits/stdc++.h>
using namespace std;

void solve() {
int n, ans = 0; cin >> n;
lint a[n + 2];
a[0] = a[n+1] = -1;
for (register int i = 1; i <= n; i++) cin >> a[i];

sort(a+1, a + (n + 1));
for (register int i = 1; i <= n; i++)
if (a[i] + 1 != a[i + 1] and a[i] - 1 != a[i - 1]) {
ans++; a[i]++;
}

cout << ans << "\n";
}

int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
register int tc; cin >> tc;
while (tc--) solve();
return 0;
}


Note: You should initialize two index as a[0]= a[n+1]=-1. If you initiate a[0]=0 and if the array a = {1,3,4} then a[0]+1 == a[1] so it’s conclude as 1st tree is a beautiful BUT it’s NOT. Similarly a[n+1] \leq -1.

1 Like

Thank you!

Thanks for the detailed explanation !

1 Like

@hellaweird You can use int a[n+2].
Therefor some update:

int a[n+2];
a[0] = a[n+1] = -1;
sort(a+1, a+n+1);
`