zanoes's blog

Codeforces Round #185 Editorial (Div.2 B&Div.1 E)
By zanoes, 12 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    P-вероятность того, что игра закончится после хода первого игрока.

    Q-вероятность того, что игра продлится ещё один раунд.

    И того складываем вероятность, что игра сразу закончится после 1-ого круга, после второго, третьего и т.д.

    Настя, извини, что не на английском!

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it -10 Vote: I do not like it

        Excellent question.

        SmallR, who shoots first can win in the following cases:

        1. He shoots the target in the first shot. OR
        2. He misses AND his opponent misses AND he shoots the target. OR
        3. 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:

        1. A did not happen AND B did not happen => C did not happen
        2. A happened AND B did not happen => C did not happen
        3. A did not happen AND B happened => C did not happen
        4. 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.

        → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +28 Vote: I do not like it

312B - Archer can also be accepted by Brute Force, during contests this algorithm is more covenient for us. 3783547

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        (a + b) ^ 3 is not equal to a ^ 3 + b ^ 3.

        → Reply