MKSQR please suggest the logic?

general
1

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.

2

get the logic by using your brain…

3

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!

4

@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
1 Like
5

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

6

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

7

Okay pudge but thanks anyways! :slight_smile: