Help needed with DEADEND : Nov 19 Lunchtime

For each non beautiful tree at position A[i], if there is a tree at A[i] + 2, plant a tree at A[i] + 1, else plant a tree at A[i] - 1.

Why does my approach fail?

https://www.codechef.com/viewsolution/28008695

1
5 
1 2 5 8 11

gives WA for this.
answer should be 3 not 2.
Trees should be planted at 6 9 and 10 right? (one solution)

Please correct me if I am wrong, but planting a tree at position 2 and 7 would suffice in this case right?

1 Like

oh wait…yes you are right.
Lemme check there’s a similar test case to this then
will edit it

I am confused because my code outputs ‘3’ for this case.

https://ideone.com/rggYYK

@sapient Everything is fine but you just need to sort the array.
Check out this test case with your solution and compare with sorted arr (just use sort(arr, arr+n)) solution:

1
5
9 2 6 1 4

Here is my explained editorial
Happy coding :heart_eyes:

1 Like

What is wrong with this code?

t = int(input())

for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	
	a.sort()
	a.insert(0, a[0] - 4)
	a.append(a[-1] + 4)

	s = set(a)
	count = 0
	for i in range(1,n+1):
		if a[i]+1 not in s and a[i]-1 not in s:
			count += 1
			s.add(a[i]+1)
	
	#print('**', a)
	#print('**', s)
	print(count)

It’s getting runtime error…

Thank you, I’ve realised my mistake

Problem with your program is, it is not working for unsorted array or for the arrays which are reversed sorted.
Example: 11 9 7 5 3 1
Actual Output: 3
Your code’s output: 5