@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?
@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++.
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: 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;
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
@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
@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.
@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
So I just needed efficient sorting algorithm right?
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.
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.
- either l==array(i) which means that i have planted a extra tree on the same place so counterâ
- 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
- else update l as array(i).
thatâs it
print counter.