DEADEND Editorial

@smile_forever
Thanks mate for taking time to help me from your busy schedule!!
If i make a[-1]=0, then will my answer get accepted?

1 Like

@tiger_atharva NO because if the array a = {1,3,4} then a[-1]+1 == a[0] so it’s conclude as 1st tree is a beautiful BUT it’s NOT.
PS: I’m NOT sure about supporting negative index in C++.

1 Like

Can someone tell what is the problem in my code?

#include<bits/stdc++.h>
#define ll long long
#define vi vector
#define vll vector
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i–)
#define si set
#define sll set
#define ins insert
using namespace std;

int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
sll s;
vll v;
rep(i,n){
ll x;
cin>>x;
v.pb(x);
s.ins(x);
}
ll cnt=0;
sort(v.begin(),v.end());
rep(i,n){
if(s.count(v[i]-1)==0 && s.count(v[i]+1)==0){
s.ins(v[i]+1);
cnt++;
}
}
cout<<cnt<<"\n";
}
return 0;
}

out of 4 only 1 test-file got fallen !
i dont know why,help please !!
https://www.codechef.com/viewsolution/28034801

I want to know ,what if x is not a integer? like Ai=1.5 ,i can never plant a tree at 0.5 and 2.5

hey can you tell me my mistake.I used the same logic and did by maps but got WA ?
Here is the link to my sol
https://www.codechef.com/viewsolution/28014190
I also changed to planting trees on left instead right for difference not equal to 2,but still getting WA.Pls help

you forgot to add the condition where that difference is not 2.
so the counter doesn’t get incremented either

Easy Solution Using Sets.
Solution Link: https://www.codechef.com/viewsolution/28006641

    int n;
	cin>>n;
	set<int> S;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		S.insert(x);
	}
	for(auto s:S)
	{
		if(S.count(s+1)||S.count(s-1)) continue;
		else S.insert(s+1);
	}
	cout<<S.size()-n<<endl;

I know that it is wrong .
I just want to know that is there is a chance that I can correct it(Can you please tell). Or try some another approach.

@brijesh293 Yes, you can.
Just need to check the previous tree can make the current tree beautiful or not…for every tree in rangei=1 to n-1. If we need to do so, then many changes require to do. Therefor, we just skip the beautiful trees using while loop, that’s require few changes.

Your AC Code

Two lines added and one condition added to else. Please follow the comment to check out the correction:

#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;

  while (t--) {
    int n, x;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; ++i) {
      cin >> x;
      v.push_back(x);
    }

    sort(v.begin(), v.end());
    int c = 0, i;
    v.push_back(-1);
    for (i = 0; i < n - 1; ++i) {

      if (i > 0)  // Added
        while (i < n and (v[i] - v[i - 1]) == 1) i++; //Added
      
      if ((v[i + 1] - v[i]) == 1)
        ++i;
      else if ((v[i + 1] - v[i]) == 2) {
        ++c; ++i;
      } else if (i < n) { // condition (i<n) added
        ++c; 
      }
    }
    if (i == n - 1) 
      if (v[i] - v[i - 1] != 1) c++;
 
    cout << c << endl;
  }
  return 0;
}

Here is the AC submission

@anand873 Hmm easy enough BUT not time+space optimized. If the constraints changed a few, then you get a TLE.
"If the sum of N over all test cases does not exceed 10^6" increased to 10^7 and provide an array with 0 (Zero) beautiful tree then your code will get TLE. Here is the efficient submission and Editorial

https://www.codechef.com/viewsolution/28020937
Why is it partially accepted?

@rohit_mahale You should initiate a[n] index with a value that never make the last tree beautiful, for ex.- a[n] = 1e11;
Here is your AC Solution Just added A[n] = 1e11

Clarification

If the array a = {1, 2, 3,5} and if unluckily a[n] == 6 Then it’s conclude as last tree is a beautiful BUT it’s really NOT. That’s why you need to initialize a[n] with a value that constrains Ai\pm 1 never hold.

Example test case:

2
4
1 3 4 5
3
1 2 4

@otutsukihyuuga Just for the while loop.
You should include #include <bits/stdc++.h> header and replace whole while loop with std:sort(a, a+n) Then your solution will be AC. Here is your AC Solution

ohk thanks man!!
will take care of this in future as well :slight_smile:

So I just needed efficient sorting algorithm right?

@otutsukihyuuga Absolutely… :+1: