0
$\begingroup$

Here is a problem inspired by the game Across the Obelisk.

4 players have decks of cards. Each card has an integer value between 0-9 on it. The decks can be any size, and there's no other restriction on the card values - each possible card-value can be represented any number of times, including 0.

The game chooses an integer $X$, then each player shuffles their deck and draws one card. What are the chances the sum of those cards is $\geq X$?

Digging into the game's code, the developers solve this problem by generating every possible combination of cards and putting their sums into an array, then counting how many instances are $\geq X$. With deck size $D$, this is $O(D^4)$. This is only feasible because there's a low number of players and the deck sizes are small. Is there a solution that scales better?

$\endgroup$

1 Answer 1

1
$\begingroup$

Here's a solution I came up with that's $O(PD + PV\log{P})$, where

  • $D$ = The size of the largest deck
  • $P$ = The number of players (4 in the original problem)
  • $V$ = The max card-value (9 in the original problem)

The main ideas of this algorithm are:

  • We can treat any deck, no matter how large, as a discrete probability distribution containing only the $V+1$ values $0$ thru $V$, each with its own probability of being chosen.
  • Because each deck is independent, we can treat the two cards coming from any two decks as though it were a single card coming from a single larger probability distribution, whose value lies in the range $0$ thru $2V$
  • Any card-value $\geq X$ (the integer we want our sum to beat) can be replaced by $X$ without changing the result

Combining these ideas, we get the following algorithm:

  1. For each deck, create a probability table mapping each card-value to its probability of being drawn

  2. Combine two tables $A,B$ into a new table $AB$, using the rule $AB(N) = A(0)B(N) + A(1)B(N-1) + ... + A(N-1)B(1) + A(N)B(0)$

    In other words, the probability of their sum being exactly $N$ is the $Prob(Card_1 = 0, Card_2 = N) + Prob(Card_1 = 1, Card_2 = N-1) + ...$

    2a. (Optional): Combine all the entries $\geq X$ into a single entry by summing their values

  3. Keep combining tables like this until there is only one left, always combining the two smallest tables. The sum of all values $\geq X$ then gives the answer.


Asymptotic analysis:

Step 1 takes time $PD$ to calculate, plus $PV$ to initialize the arrays, for an overall $O(PD + PV)$

Step 2 does one multiplication for each combination of cards, for a total of $|A||B|$.

Step 3 has step 2 repeating a total of P-1 times. The first P/2 times, the tables will each have size V. The next P/4 times, the tables will have size 2V. The next P/8 times, the tables will have size 4V, etc. So the total number of multiplications is $$(P/2)(V+V) + (P/4)(2V+2V) + (P/8)(4V+4V) + ...$$$$= PV + PV + PV + ...(\log_2{P}\text{ times})$$

for an overall $O(PV\log{P})$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.