Competitive Programming Algorithm Sock Drawing Probability Question

Question

First let me paste the question.

This problem is based on an (almost) true story. A child, who shall remain nameless, has a large pile of clean socks. This pile contains m pairs of socks with pictures and patterns and n pure white socks. Each pair of socks consists of two identical socks and every pair is unique — no two pairs look the same. All pure white socks are identical. Each day, the child randomly selects two socks from the pile, puts them on, and heads for school. But today is a picture day and the child needs to wear two identical socks. So the child randomly selects two socks and if both socks are identical, the child puts them on and heads out the door. If the two socks are not identical, the child throws the socks into the laundry basket (they are now dirty — don’t ask why) and continues the same process of randomly selecting two socks from the pile of remaining clean socks. As this process continues, the parents are starting to get worried: Will this child ever make it to school today? Please help them to compute the probability that the child will not find a pair of identical socks using this process. This problem is based on an (almost) true story.

First of all, the limitations are n<=500 pairs of socks, and m<=200 white socks. I've really tried to solve question every way i can. I used permutation of 7! and then count the paired socks. At test problem, there are 3 white and 2 paired socks. I could only solve this by counting all paired socks in 7! permutations. Which is O(n^n) and really inefficient. Can you help me how i can solve this question? I used python by the way, and this is a competitive programming question.

You can find the question at:https://open.kattis.com/problems/thesockpile

I'm just solving these questions for fun, it's an open question. I've really tried 2 days to solve this, but still couldn't. Appreciate any help.

At initial test answer, there are 3 white socks and 2 paired socks (total of 7 socks). And the answer is:0.457142857142857

Answer 1

High-level strategy: another way to view the problem is that the child pulls pairs of socks until there are zero or one left, then checks for a matched pair. Compute Pr(no pair is a white match) and Pr(no pair is a patterned match | no pair is a white match), then compute the answer using Probability 101.

Pr(no pair is a white match): a white match is guaranteed if and only if m+2 ≥ 2n. If m+2 < 2n, no pair is a white match if and only if either there are exactly m pairs with exactly one white sock, or m is odd and there are exactly m−1 pairs with exactly one white sock and the leftover sock is white.

For this computation, treat the patterned socks as indistinguishable. There are (m + 2n) choose m ways to draw the socks. When m is even, count the number of ways to draw the socks without a white pair as (m/2 + n) choose m ways to choose pairs with a white sock times 2^m ways to draw those pairs. When m is odd, we get (((m−1)/2 + n) choose (m−1)) × 2^m−1 ways where the leftover sock is white plus ((m−1)/2 choose m) × 2^m ways where the leftover sock is patterned.

Pr(no pair is a patterned match | no pair is a white match): I'll tackle the case where m is even and leave the other case to you or someone else. We have m/2 + n pairs, of which m contain exactly one white sock, so n − m/2 pairs with two patterned socks. Inclusion-exclusion on subsets of patterns that match gives us the alternating sum

        i                    1            1                  1
 ∑  (−1)  (m choose i) (---------- × ---------- × … × ---------------)
i≥0                     2n + m − 1   2n + m - 3       2n + m - 2i + 1

where m choose i is the number of ways to choose the i patterns, and the product is the probability that all i are matched (for each pattern in some order, we reveal the first sock and then compute the probability that its mate matches).

The odd case works similarly except that, as before, we split into cases based on whether the leftover sock is white.

Answer 2

This sounds like a classic dynamic programming problem. If you slightly expand the problem to include singleton socks (so k singletons, m socks that are parts of pairs, and n white socks) you can memoize the probability of any triplet. Here's my python implementation:

probabilities = {};

def socks(k, m, n):
  total = k + m + n
  if total < 2:
    return 0

  if (k, m, n) in probabilities:
    return probabilities[(k, m, n)]

  prob = 0

  # Selected a white pair
  if n >= 2:
    prob += n * (n-1)

  # Selected two paired socks
  if m >= 2:
    # Successful pair
    prob += m
  if m >= 4:
    # Mismatched pair
    prob += m * (m-2) * socks(k+2, m-4, n)

  # Selected mixed white and paired socks
  if m >= 2 and n >= 1:
    prob += socks(k+1, m-2, n-1) * m * n * 2

  # Selected a singleton (always mismatched)
  if k >= 2:
    prob += socks(k-2, m, n) * k * (k-1)
  if k >= 1 and m >= 1:
    prob += socks(k, m-2, n) * k * m * 2
  if k >= 1 and n >= 1:
    prob += socks(k-1, m, n-1) * k * n * 2


  prob /= total * (total - 1.0)
  probabilities[(k, m, n)] = prob
  return prob;

Note that anytime you selected a paired sock you effectively destroy two paired socks and create a new singleton.

Also it looks like you're answering the inverse of your own question (or one or both of us have a bug somewhere), since the answer my code spits out for socks(0, 4, 3) is 0.542857142857.

Answer 3

//
// Created by phystech on 19.09.2020.
//
#include <iostream>

#include <unordered_map>
#include <string>
#include <iomanip>

typedef std::tuple<int,int,int> nkey;

class CustomHash
{
public:
// Implement a hash function
    std::size_t operator()(const nkey& k) const
    {
        // This could be a bad hash function anyway
        std::size_t h1 = std::hash<int>{}(std::get<0>(k));
        std::size_t h2 = std::hash<int>{}(std::get<1>(k));
        std::size_t h3 = std::hash<int>{}(std::get<2>(k));
        return h1 ^ h2 ^ h3;
    }
};

std::unordered_map<nkey ,float,CustomHash> probs;


double socks(int k,int m,int n)
{
    int total = k+m+n;

    if (total<2)
    {
        return 0;
    }


    nkey key(k,m,n);


    if(probs.find(key) != probs.end())
    {
        return probs[key];
    }

    double prob = 0.0;

    if (n>=2)
    {
        prob += n*(n-1);
    }

    if(m>=2)
    {
        prob += m;
    }
    if(m>=4)
    {
        prob += m*(m-2)*socks(k+2,m-4,n);
    }

    if (m>=2 && n>=1)
    {
        prob += socks(k+1,m-2,n-1)*m*n*2;
    }

    if(k>=2)
    {
        prob += socks(k-2,m,n) * k * (k-1);
    }
    if(k>=1 && m>=1)
    {
        prob += socks(k,m-2,n)*k*m*2;
    }
    if(k>=1 && n>=1)
    {
        prob += socks(k-1,m,n-1)*k*n*2;
    }

    prob /= total*(total-1.0);
    probs[key] = prob;

    return prob;

}

int main(){
    uint_fast64_t m,n;

    std::cin >> m >> n;

    if(n>=2*m+2)
    {
        std::cout<<"1.0";
    }
    else
    {
        std::cout << std::setprecision(15);
        std::cout << (1.0-socks(0,m*2,n));
    }



}`enter code here`