taratam's blog

Problem: Game probabilities
By taratam, 11 years ago, In English

Two players playing a game. Peter has a dice with N walls ( numbered from 1 to N ), Sam has a dice with M walls ( numbered from 1 to M ). Before the game on random they select two numbers L ( L <= N ) and K ( K <= M ). If a during the game Peter throw any of his L numbers he wins. If a Sam throw any of his K numbers — he wins the game. They change off on each turn while someone win. The first turn is for Peter. What is the probability Peter to win the game?

Input

The first line has four numbers — 1 <= N, L, M, K <= 1000. The second line has L numbers — the winning numbers for Peter, 1 <= Ai <= N. The third line has K numbers — the winning numbers for Sam, 1 <= Bi <= M.

Output

The probability Peter to win the game like a rational fraction. The output fraction must be simplified ( if the fraction is 2/4, we must output 1/2 ). The numbers 0 and 1, will be represent like a 0/1 and 1/1.

Input

2 1 6 2

1

1 2

Output

3/4

Can someone explain me the solution of problem?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm no pro, but this is how I see it:

Find the probabilities of getting the winning number (P = L/N, S = K/M) Also, let's call the probability of Sam not getting his winning numbers Q (so Q would be 1-(K/M)

Then it's a repeated case study

Peter has a P chance of winning immediately, but if he loses he can win if Sam loses and he wins, or if they both lose and Sam loses again and then he wins, and so forth

It becomes P+Q*P+Q*Q*P+Q*Q*Q*P+...

Which is a geometric sequence with the first term P and the common ratio Q, so I believe the answer is P/(1-Q), so (L/N)/(1-(K/M)), which is the answer (You can disregard what the actual winning values are, they aren't important)

I'm not sure if I messed up somewhere in my calculations, this formula at least holds true with the sample

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

    I'm agreed with you. I thinking something like you and i got your formula, but it fails on the second test case in the example input.

    Here is it:

    49 3 52 5

    2 47 29

    46 40 11 20 1

    And the answer is 78/193. With this formula the answer is 146/2303 ( maybe is not simplified, but it is smaller than the correct answer )... ):

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

      Oh, whoops, I see where I messed up:

      So, you also have to use the probability of Peter getting it wrong n number of times (and sam also getting it wrong n times). So the common ratio is (1-p)(1-s)

      The correct formula would be:

      p/(1-(1-p)(1-s))

      (I think xD)

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

        Your logic is correct! and passed the second test case :) Thank you! :)

        → Reply