DEADEND Editorial

PROBLEM LINK:

Practice
Contest

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;
} 
5 Likes

Here is the easiest way to solve it:

  1. Use an array with 2 extra index. say a[n+2]. and initiate with a[0]=a[n+1]=-1 so that it never make a tree beautiful.

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

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

  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;
 int 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 extra 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`.

3 Likes

I have a which is similar to the editorial i used maps instead of sets.
here’s a link to my AC solution: https://www.codechef.com/viewsolution/28010782
:slight_smile:

Did very similar solution, however in your solution doesn’t the a[i+1] cause an out of bounds error when i = n?.

size of array is n+2

Oh yeah fair enough I can’t read lmao.

Nice solution btw, did the same thing but without the forward check because I didn’t wanna deal with the out of bounds thing.

1 Like

@sirjunglefowl Absolutely nope, because I used 2 extra index a[n+2], one at fast, another at last with a negative value, so that it never make a tree beautiful.

I submitted a solution with data type as long long int and it got Partially Accepted. While on making data type as Int , I got it fully accepted. Can someone tell me why this happened ?

Partially accepted- https://www.codechef.com/viewsolution/28028350
Fully accepted- https://www.codechef.com/viewsolution/28028412

Shouldn’t we be checking if arr[j] + 1 is in the set?
Wouldn’t this fail for 2 3 7 ?
As for 2 by the Editorialist’s solution there is no tree at 1 but it does satisfy the ‘beautiful’ condition as there is a tree at 3?

Can anyone please tell me what is wrong with my code or logic. I have been dry running this code and it seems to work fine. I have used the same logic as explained above.
https://www.codechef.com/viewsolution/28011801

I did the same thing in Python, can any1 tell me what’s the mistake in here

I think its perfect. Then why WA ?

Can anyone tell me my mistake. I tried a bit different approach.
https://www.codechef.com/viewsolution/28031172

@tiger_atharva There is some bug in array indexing. (negative index). I’m very busy now,when I’ve time, I’ll try to find out the defect. Your both solution should not be accepted. Here is a test case for your AC solution, try out this:

1
8
9 1 4 16 18 12 19 11

Output should be 4, BUT your AC solution provide 3. Happy coding.

Can you Please tell me what is this statement doing here?

@smile_forever I’m getting output as 4 only.

dead
Any possible test case i may have missed or bugs in the question?

Happy Coding : -)

@super_saiyan1 Bro, your logic is correct. BUT…alignment not. If you properly aligned your code, then you can see -

// Wrong Alignment
...
else if(i == (n - 1)) if(a[i] - a[i - 1] > 1) ans++;
else
{
      if(((a[i] - a[i - 1]) > 1) && ((a[i + 1] - a[i]) > 1))
...

Here is the proper alignment:

...
} else if (i == (n - 1))
    if (a[i] - a[i - 1] > 1)
        ans++;
    else {
          if (((a[i] - a[i - 1]) > 1) && ((a[i + 1] - a[i]) > 1)) {
...

You should use bracket if you prefer your alignment, Like this:

...
else if(i == (n - 1)) 
{ 
    if(a[i] - a[i - 1] > 1) ans++;
}
else
{
      if(((a[i] - a[i - 1]) > 1) && ((a[i + 1] - a[i]) > 1))
...

Here is your AC code with proper alignment with bracket: YOUR AC Solution
Hope you get it. Happy Coding :heart_eyes:

1 Like

@tiger_atharva It’s depends on the environment. For i = 0 your code get a negative index and therefore unexpected value… Here follow the comment to see it:

...
#Check out the comment  for i = 0
for (i = 0; i < n; ++i) {
      if (i == n - 1 && b[i] == 1) { #skip
      ...
      } else { # get in
        diff = abs(a[i] - a[i + 1]); # diff = 3 for given TC
        if (diff == 1 && b[i] == 1) { # skip
          b[i] = 0;
          b[i + 1] = 0;
          i++;  // cout<<"2st if"<<"\n";
        } else if (a[i] - a[i - 1] == 1) { #  index < 0 (&get in when i debug your code)
          b[i] = 0;  #executed for  i = 0 (when debugging in my pc)
        }
1 Like

Bro see this one code link

@brijesh293 Check out the following test case:

1
10
17 13 5 2 20 9 8 14 19 10

Answer: 3
Output: 4
Hope you get it. Happy coding :slightly_smiling_face: