MKSQR please suggest the logic?

http://www.codechef.com/problems/MKSQR i am not getting d logic to solve this question. I thought it has something to do with linear independence of vectors but i guess i am wrong, i need only a slight idea to solve this and please no code just logic to solve the problem.
Thanks you.

get the logic by using your brain…

If you can’t suggest me anything then please don’t mock me either, I am a newbie here and to competitive programming as well. If u can’t help then just get lost because i dint ask u to utter your bullshit here, idiot!

@keyser: the logic is simple. that is in the given co-ordinates there should be atleast one co-ordinate which should have x > y if all other co-ordinates have x < y or it should have x < y if all other co-ordinates have x > y.

Proof

  • let us prove this first by taking n=3 and then you can think of for n=N
  • let us consider 3 co-ordinates (x1,y1) , (x2,y2) , (x3,y3).
  • now take three arbitrary constants a1,a2,a3 all >0 because mentioned in the question
  • now according to question a1x1+a2x2+a3x3=a1y1+a2y2+a3y3
  • regrouping we get a1(x1-y1) + a2(x2-y2) + a3(x3-y3) = 0
  • now let x1-y1 , x2-y2 , x3-y3 be some constants k1,k2,k3 respectively
  • so above equation becomes a1k1 + a2k2 + a3k3 = 0
  • if k1 , k2 , k3 all are >0 then we cannot make a1k1 + a2k2 + a3k3 equal to 0 because a1, a2 , a3 > 0
  • so there must be atleast 1 k < 0 among k1 , k2 , k3 to make it zero by selecting suitable values of a1 ,a2 , a3.
  • I think now you can extend it upto N
2 Likes

got it! thank you very very much sir! :slight_smile:

hey keyser don’t call me sir because i am also a student like you :slight_smile:

Okay pudge but thanks anyways! :slight_smile:

//