DEADEND Editorial

editorial
, , , ,
23

@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
24

@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
25

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

26

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

27

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

28

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

29

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

30

Easy Solution Using Sets.
Solution Link: CodeChef: Practical coding for everyone

    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;
31

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.

32

@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

33

@anon71312354 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

34

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

35

@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.

36

Example test case:

2
4
1 3 4 5
3
1 2 4

12
screenshot-www.codechef.com-2019.12.png1237×788 19.5 KB

37

@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

38

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

39

So I just needed efficient sorting algorithm right?

40

@otutsukihyuuga Absolutely… :+1:

41

But as far as I know you can write your code in a single line unless there are multiple statements in a block. Then why is it giving wrong answer? And if there was an issue with the syntax then it wouldn’t have compiled.

42

i think i have used a very simple approach by looking at the solution others posted.
just keep a pointer(l) of where you have planted last tree. which is array[0]+1 initially…and a counter of how many extra tree planted upto now.
now for every index there are 3 conditions possible.

  1. either l==array(i) which means that i have planted a extra tree on the same place so counter–
  2. if (array(i) - l) >1 which means that there is more than 1 difference between last planed tree and current tree so plant a tree just after array(i). and update l
  3. else update l as array(i).
    that’s it
    print counter.