Need help with Planting trees(DEADEND)

help
1

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.

2

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
3

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 :v:
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
5

Thank you!

6

Thanks for the detailed explanation !

1 Like
7

@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);