MKSQR Problem - CodeChef 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…
@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
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!
got it! thank you very very much sir!
hey keyser don’t call me sir because i am also a student like you
Okay pudge but thanks anyways!