Блог пользователя zanoes

Автор zanoes, 11 лет назад, По-английски

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.

Разбор задач Codeforces Round 185 (Div. 1)
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 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?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

        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.

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 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

»
8 лет назад, # |
  Проголосовать: нравится 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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 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.