algorithmrandomized-algorithm

I was trying to solve Card flipping problem with randomized algorithm, but I can't get the expectation of each flip


We are given n cards. Each card has front and back side. fi denotes the front value of a card i. bi denotes the back value of a card i. Each value of the card is a positive integer. In initial status, each card is on top side with its front side. For each card, we can choose to flip or not. We want to maximize the number of distinct numbers on top sides of all the cards. For example, n = 3, f1 = 1, f2 = 2, f3 = 2 and b1 = 3, b2 = 2, b3 = 3. Then by flipping the card 3, we can maximize the number of the distinct numbers on top sides of all the cards which is 3 since there are numbers 1, 2, and 3 on top sides of all the cards after flipping the card 3.

I tried to solve this problem with DP, but after some tries, I wasn't sure if this problem is a P problem. So I wanna solve with a Randomized algorithm, such that flip every card for 1/2 randomness. For the correctness of randomized algorithm, I try to get the expection of every single filp, but I can't do it at all.

  1. How can I calculate expection?
  2. Is there are any better solutions? Thank you for your consideration.

Solution

  • Think of this as a network flow problem.

    Create a source & sink node, and a node for each card, and a node for each distinct value on either side of any card (so the set of unique possible values).

    Create an arc with capacity 1 from the source to each card, and an arc with capacity 1 from each card to the two numbers available to it (or the 1 if they're the same), and an arc with capacity 1 from each number-node to the sink.

    Then find the max (integer) flow through the graph, say via Ford Fulkerson. The numbers this passes through are one of potentially several valid answers.

    Example

    n = 3, f1 = 1, f2 = 2, f3 = 2 and b1 = 3, b2 = 2, b3 = 3

    It's not easy to draw a network in text; but if we imagine all the lines as arrows pointing to the right, and the 'X' as a pair of crossing arrows, then this is a representation of the above example:

             card1 - 1
           /       \   \
    source - card2   3 - sink
           \       X   /
             card3 - 2
    

    Then, the max flow is:

    source - card1 - 1 - sink
    source - card2 - 2 - sink
    source - card3 - 3 - sink