Codeforces div 3

#1

https://codeforces.com/contest/988/problem/D

can anyone explain me the approach

#2

@dare_devil_007 hey bro we are not allowed to tell on running competition solution.sorry I will help when its over.

#3

it’s not ongoing contest,it is from the past contests

#4

@dare_devil_007 hey, Let’s prove that the size of the sub-set will not be > 3 . Suppose a , b , c and d are four elements from a sub-set and a < b < c < d .
Let abs(a – b) = 2k and abs(b – c) = 2l then abs(a – c) = abs(a – b) + abs(b – c) = 2k + 2l = 2m . It means that k = l . Conditions must hold for the triple (b, c, d) too. Now it is easy to see that if abs(a – b) = abs(b – c) = abs(c – d) = 2k then abs(a – d) = abs(a – b) * 3 which is not a power of two. So the size of the sub-set will never be greater than 3.

  • Let’s check if the answer is 3 . Iterate over the given array for middle elements of the sub-set and for powers of two from 1 to 30 inclusively. Let xi be the middle element of the sub-set and j the current power of two. Then if there are elements xi-2j and xi+2j in the array then the answer is 3 .
  • Else check if the answer is 2 . repeat the previous step but here one can get either left point xi-2j or xi+2j .
  • If the answer is neither 2 nor 3 then print -1 .
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.