zanoes's blog

By zanoes, 6 years ago, ,

312B - Archer

let p=a/b,q=(1-c/d)*(1-a/b). The answer of this problem can be showed as:p*q^0+p*q^1+p*q^2+………… That is the sum of a geometric progression which is infinite but 0<q<1.We can get the limit by the formula:p/(1-q)

311E - Biologist

Obviously, It is about min-cut, which can be solved by max-flow. So, this problem can regarded as the minimum of losing money if we assume SmallR can get all the money and get a total money(sum of wi)at first. Define that, in the min-cut result, the dogs which are connected directly or indirectly to S are 0-gender.otherwise, those to T are 1-gender.We can easily find that the point of a initial-0-gender dog should get a vi weight edge to S.On the other way, initial-1-gender to T. Then, consider the rich men.As to each of rich men, he can appoint only one gender and some dogs.if any one dog he appoint is not the one appointed gender in the result, he can't give SmallR money.How to deal with the rich men in the graph is a difficulty.We can do this, make a new point for a rich man.Then, link the man's point to all points of his dogs by max enough weigh edges(which we can't cut in the min-cut algorithm), and link the man's point to S or T (which depend on that the man's appointed gender is 0 or 1) with a edge of wi weight. lastly run the min-cut(max-flow), we will get the minimum money we will lose. The answer is TotalMoney-LosedMoney. BTW, the issue of g is a piece of cake, we could add it to every special wi but not add it to the total money.

• +5

 » 6 years ago, # |   0 Can you explain please your solution to the problem about probability? I am not good at it, that's why i can't understand the idea... Why do you get this p and q?
•  » » 6 years ago, # ^ |   0 P-вероятность того, что игра закончится после хода первого игрока.Q-вероятность того, что игра продлится ещё один раунд.И того складываем вероятность, что игра сразу закончится после 1-ого круга, после второго, третьего и т.д.Настя, извини, что не на английском!
•  » » » 6 years ago, # ^ |   0 Sorry, but i can understand, why sometimes we have to count product of probabilities of 2 events, and sometimes we have to count their sums?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   -10 Excellent question.SmallR, who shoots first can win in the following cases: He shoots the target in the first shot. OR He misses AND his opponent misses AND he shoots the target. OR He misses AND his opponent misses AND he misses AND his opponent misses AND he shoots the target When there is an OR between 2 events(which lead to same result) happening, it means EITHER of them will lead to the same result, so the probability of the result is the SUM OF ALL THESE PROBABILITIES.On the other hand, when there is AND between 2 events, it means that BOTH OF THEM SHOULD HAPPEN TO GET THE DESIRED OUTCOME. So if event A happens with probability = 1/2 and event B happens with probability = 1/2 and event C happens when both A and B happen, then probability of C happening is 1/2 * 1/2 = 1/4, which also makes sense logically. Because C will happen in only 1 out 4 cases, when BOTH A and B have happened. You can imagine the 4 cases: A did not happen AND B did not happen => C did not happen A happened AND B did not happen => C did not happen A did not happen AND B happened => C did not happen A happened AND B happened => C happened So a good rule of thumb is AND means product of probabilities and OR means sum of probabilities.So now we can get the answer to our problem:answer = a/b + ( (1-a/b) * (1-c/d) * a/b ) + ( (1-a/b) * (1-c/d) * (1-a/b) * (1-c/d) * a/b )... and so on.You can sum this up using formula for sum of infinite geometric series.PS: I know this question was asked 3 years ago, but I hope this helps someone.
•  » » » » » 3 years ago, # ^ |   0 it helps me more thanq
•  » » » » » 2 years ago, # ^ |   0 Helped me , Thanks bro :D
•  » » » » » 21 month(s) ago, # ^ |   0 thanks a lot.
•  » » » » » 3 months ago, # ^ |   0 See it is 26 July 2019 , and it helped me . :) [user:TombBombadil]
•  » » » » » 2 days ago, # ^ |   0 Helped me too, thanks!
 » 6 years ago, # | ← Rev. 3 →   +28 312B - Archer can also be accepted by Brute Force, during contests this algorithm is more covenient for us. 3783547
•  » » 6 years ago, # ^ |   0 I am not good at probabilities. Could you please explain what is the now variable for. I mean, I understand te first two parts and why the for goes up to 1000000, I just can't understand is the update of the now. I also get that (1-z)*(1-r) is the combined probability that there is no winner at all..Thanks
•  » » » 6 years ago, # ^ |   +18 It means the probability after some steps.
 » 4 years ago, # |   0 Hello,This is my submission for problem D.Div1. My Machine output for the sample input is the same as the sample output. However, it displays different output here on CF machine.Can anyone help me with this?
•  » » 4 years ago, # ^ |   0 Try to code your own pow function. Function from cmath returns double, that is, for example, pow(3, 3) could return 26.99999 and became 26 when changed to int.
•  » » » 4 years ago, # ^ |   0 I edited my code and removed the 'pow' function but I got WA on test 2. Well, I don't know what is the wrong about my implementation. Do you have an idea?Here is my new submission.
•  » » » » 4 years ago, # ^ |   0 (a + b) ^ 3 is not equal to a ^ 3 + b ^ 3.
•  » » » » » 4 years ago, # ^ | ← Rev. 4 →   0 You mean this line at 'update' function?tree[node] = tree[node * 2] + tree[node * 2 + 1];The tree is built on sum that's why I wrote that line.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I mean that leaf nodes are raised to power 3 but other nodes are not. Why I should raise non leaf nodes to power 3?