Omar_Mekkawy's blog

By Omar_Mekkawy, 5 years ago, In English,

in the editorial it's mentioned that No solution exists if 3x < y. in case of n=2.

can anyone please tell me why is that true? and in my accepted solution , in case of n=2 i iterated 10^6 and assumed that my 3 sorted numbers are the first,second,and third number , can any one please tell me why did this solution pass and we didnt have to try all the permutations for the 3 numbers with the 4th generated one?

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My formulas no so good,but I hope that you will understand. x4-x1=(x2+x3)/2 x4-x1=(x1+x2+x3+x4)/4 X4-x1=(x1+2(x4-x1)+x4)/4 only change x2+x3 with 2(x4-x1),first equally 4(x4-x1)=(3x4-x1) 4x4-3x1=3x4-x1 X4=3x1 So the biggest number must be exactly three times bigger then the smallest number. In your case Xq<=x and xmax>=y and this condition not valid.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

let's assume we have the four numbers a<=b<=c<=d satisfy that (b+c)/2 = (a+b+c+d)/4 = (d-a) , with some basic math you can see that (b+c)/2 = (a+d)/2 , since (d-a) = (b+c)/2 "range = median " so the equation is (d-a) = (a+d)/2 , by reformulating the equation we get (d = 3a) , note that "a" is the smallest number and "d" is the largest number so the greatest ratio between two numbers is 1:3 so if there are two numbers x,y and (y>3x) that's mean these two number don't belong to the same sequence .

why your solution pass without trying all permutations ?

because the limits are so small , in the worst case the two numbers can be equal to 500 , and you can find a solution even if you just iterated over [1-1500] because if you exceed 1500 that's mean there are two numbers x and y such as (y>3x) and in this case there's no solution and your code will output "NO" .