Equilibrium codechef ques
Chef is an intern at Zoozle. He has a co-intern named Ajar who's good at maths. Chef wants to impress Ajar with his zoozliness, so he decided to play the following game with Ajar:
Consider n force vectors in a 2D plane.
First, Ajar uniformly randomly chooses a non-negative real magnitude for each vector such that the sum of all magnitudes is equal to k. (More formally, each valid n-tuple of magnitudes can be chosen with the same probability.)
Then, Chef must choose a direction for each force vector in such a way that the net force (vector sum of all forces) is equal to zero. Chef wins the game if he is able to do that; otherwise, Ajar wins the game.
Since Chef knows that it may not always be possible to choose the directions such that he wins the game, he would like to know the probability that he'll be able to win if he plays optimally. Can you help him?
It can be proven that this probability can be written as a fraction P/Q, where P≥0 and Q>0 are coprime integers. Since we are in the 21st century, nobody is interested in fractions. Therefore, you should compute P⋅Q−1 modulo 109+7, where Q−1 denotes the modular inverse of Q modulo 109+7. (It is guaranteed that this inverse exists and is unique.)
I want only hint....no source code
Consider n force vectors in a 2D plane.
First, Ajar uniformly randomly chooses a non-negative real magnitude for each vector such that the sum of all magnitudes is equal to k. (More formally, each valid n-tuple of magnitudes can be chosen with the same probability.)
Then, Chef must choose a direction for each force vector in such a way that the net force (vector sum of all forces) is equal to zero. Chef wins the game if he is able to do that; otherwise, Ajar wins the game.
Since Chef knows that it may not always be possible to choose the directions such that he wins the game, he would like to know the probability that he'll be able to win if he plays optimally. Can you help him?
It can be proven that this probability can be written as a fraction P/Q, where P≥0 and Q>0 are coprime integers. Since we are in the 21st century, nobody is interested in fractions. Therefore, you should compute P⋅Q−1 modulo 109+7, where Q−1 denotes the modular inverse of Q modulo 109+7. (It is guaranteed that this inverse exists and is unique.)
I want only hint....no source code
We badly need a separate section for so-called "competitive" programming. That way it would be easier to ignore.
let n = 1.
therefore Ajar wins, 100% probability.
If Ajar is not a moron, he should bet money with Chef after accepting to play his flawed game. Unless 0 is allowed as a magnitude, in which case Ajar can still win 100% of the time, he just needs to construct an unwinnable scenario which is more trouble.
In other news, relate P and Q to N for me. This feels like one of those problems that reads … two trains are moving toward each other at whatever speeds, is it raining in Tennessee?
therefore Ajar wins, 100% probability.
If Ajar is not a moron, he should bet money with Chef after accepting to play his flawed game. Unless 0 is allowed as a magnitude, in which case Ajar can still win 100% of the time, he just needs to construct an unwinnable scenario which is more trouble.
In other news, relate P and Q to N for me. This feels like one of those problems that reads … two trains are moving toward each other at whatever speeds, is it raining in Tennessee?
Last edited on
I am asking you how P&Q relate to N.
That is the hint ... if you figure that out, you can probably solve the whole thing easily.
The rest of it was just joking a little. I am saying that you have an obviously rigged game such that Ajar can win 100% of the time if he sets it up correctly.... the question is poorly worded. If Ajar is setting up the problem at random, Chef has a chance. Ajar isnt stupid, so he won't do that, he will set it up to win.
That is the hint ... if you figure that out, you can probably solve the whole thing easily.
The rest of it was just joking a little. I am saying that you have an obviously rigged game such that Ajar can win 100% of the time if he sets it up correctly.... the question is poorly worded. If Ajar is setting up the problem at random, Chef has a chance. Ajar isnt stupid, so he won't do that, he will set it up to win.
@jonin, If let's say we have n=5 then chef has to play optimally to get the value as 0, so I think the force vectors will be zero if we can form a closed polygon witht these points ?? I don't know if this approach is correct or not , but I think we need to find the number of ways we can form a polygon with these points, maybe ? please help
any one having full ac for NMNMX or NSA i can give full ac solution for equilibrium problem.
PM me
PM me
I don't know. A polygon might work, but only if it zero sums to the center. Not all polys do that, of course; most do not...
Chef may also be able to break all the vectors into their component forms and then solve something from there. you can try to find all the solutions to
a * cos(angle1) + b * cos(angle2) ... = 0
and
a * sin(angle1) + b*sin(angle2)... = 0
the solution that works for both wins, I think.. and the trig(angle)s are just constants.
there are tons of implications to such equations... the y side equals the x side since both equal zero ... but is there a clever way to get the answer from that? I don't know.
you don't want the solution anyway, you want the probability, relating the number of possible solutions ... but what does optimally even mean? Playing optimally means solving the thing, if a solution exists. Is it asking what the odds of a solution existing are??
Chef may also be able to break all the vectors into their component forms and then solve something from there. you can try to find all the solutions to
a * cos(angle1) + b * cos(angle2) ... = 0
and
a * sin(angle1) + b*sin(angle2)... = 0
the solution that works for both wins, I think.. and the trig(angle)s are just constants.
there are tons of implications to such equations... the y side equals the x side since both equal zero ... but is there a clever way to get the answer from that? I don't know.
you don't want the solution anyway, you want the probability, relating the number of possible solutions ... but what does optimally even mean? Playing optimally means solving the thing, if a solution exists. Is it asking what the odds of a solution existing are??
Last edited on
Since the magnitude has to be real and not just integers, the number Q, if its the sample space, will be quite large, and unpredictable too. Same goes for P also.
closed account (jy6DLyTq)
I m ready to give NMNMX / EQUILBR 100 POINTS SOULUTION IN EXCHANGE OF GEARS 100 POINTS SOLUTION
if someone can give me full ac solution for NMNMX i can give me full ac solution for equilibrium prob!!
PM me
PM me
Do they give away money or something? Why is everyone trying to cheat on a self-improvement exercise?!
... do you know how vectors work?
take any pair of vectors 180 degrees apart and they will zero sum with the same coefficient. so take a few pairs... 4 or 6 of opposed vectors and give them the same value and its a win.
or nontrivial example, try 45 degrees and a 180 & 270. (the coefficients won't all be equal here...)
take any pair of vectors 180 degrees apart and they will zero sum with the same coefficient. so take a few pairs... 4 or 6 of opposed vectors and give them the same value and its a win.
or nontrivial example, try 45 degrees and a 180 & 270. (the coefficients won't all be equal here...)
Last edited on
I am still not sure what its the probability OF. Nothing is randomized, its constructed by a human in the problem statement, and the human is trying to make it not happen. I mean, can you figure out the odds of just 2 vectors being possible if the guy who created them does not want chef to win? Its 100% probable that chef cannot win.
if the directions are random, which is not what it says, what is the probability of 2 vectors being winnable? Its nearly zero, if you use floating point angles, and if you use integer angles, its what, 1 in 360 chance?
Ill help any well asked problem, but this problem has too much wrong with it to give a sensible answer.
common sense tells me that the more vectors you have, the higher the odds for chef. If you had a vector at every possible angle, infinite vectors, chef wins -- every vector has an opposed vector, and they can be zeroed. and the more you have, the more you can balance the x and y components to zero it. but I can't tell you how to compute that.
if the directions are random, which is not what it says, what is the probability of 2 vectors being winnable? Its nearly zero, if you use floating point angles, and if you use integer angles, its what, 1 in 360 chance?
Ill help any well asked problem, but this problem has too much wrong with it to give a sensible answer.
common sense tells me that the more vectors you have, the higher the odds for chef. If you had a vector at every possible angle, infinite vectors, chef wins -- every vector has an opposed vector, and they can be zeroed. and the more you have, the more you can balance the x and y components to zero it. but I can't tell you how to compute that.
Last edited on
Topic archived. No new replies allowed.