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.
Need help with Planting trees(DEADEND)
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.
Yes, You’re right, It’s due to the sorting.
You can follow this simple technique to avoid extra sorting.
Explanation

Use an array with 2 extra index. say
a[n+2]
. and initiate witha[0] = 1, a[n+1]=1e11
so that after sorting it never changed their position. 
Get input. ex.
for (int i = 1; i <= n; i++) cin >> a[i];

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

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 ina
, just increase thei
'th position by1
. For ex. ifa = {2, 4}
then we just need a tree at position3
to make it beautiful [We just increase our counter and tree’s position by1
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]++;
}
}
 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`.
Thank you!
Thanks for the detailed explanation !
@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);