Solution to GCJ2014 QR

Magic Trick

Enumerate all possible card and check each card and obtain the possible card set POSSIBLE.
If |POSSIBLE| == 0, we say "Volunteer cheated!"
If |POSSIBLE| > 1, we say "Bad magician!"
If |POSSIBLE| == 1, we just output the unique card.

Cookie Clicker Alpha

Consider the final situation: there are U farms producing cookies.
What is the best strategy to buy U farms?
After buying the Uth farm, how many cookies we left?
Supposing we have some cookies left, why do not we buy the Uth farm in a earlier time?
If we buy it earlier, the situation is certain better.
So, the best strategy to buy U farms is "To buy each farm as early as possible, and the other
strategy is always worse than this one.
Using A[i] to record the best time to buy i farms, and A[i] can be easily calculate through A[i-1]
where A[0] = 0.
So we can enumerate each possible U and calculate the time to achieve the goal to find the best one.
When the time with i farms is longer than the best time to achieve the goal through no more than i-1 farms,
we stop enumerating.
What's the complexity of this algorithm?
We use S to denote the number that buying S+1 farms become worse than all the previous solutions.
We also use K to denote the number that buying S+1 farms become worse than the previous solutions.
It is easy to see K >= S.(It seems that K == S because of the monotonicity of solution)
We solve the inequality: TIME(K) > TIME(K+1) and get:
(X-C)/X > (2 + K * F) / (2+(K+1)*F)
The maximum of K which satisfy the above inequality is an upper bound of the algorithm.

Minesweeper Master

M == R*C - 1 is a special case, we solve it alone.
We can claim that, if it can be solved by a click, then:

  • There exist at least one ZERO cell (cell labelled 0).
  • All the ZERO cells are in the same connected component.
  • All the non-star cells are in a connected component.
  • Each cell with a label great label has a ZERO cell as its neighbour.
    • So the strategy is to enumerate the configuration which can satisfy the condition above easily.
    The left-top corner is a u * v rectangle with star.
    Then put the left stars in the left-bottom corner column by column, and from top to bottom in
    each column.
    We can see the above configurations can satisfy the first three condition and
    most of them satisfy the last condition.
    After enumerating each configuration, check it.
    Note: the configuration satisfy the condition easily does not mean all the configuration satisfy the condition.

    Deceitful War

    The most important information in the description is "2.Naomi tells Ken the mass of the block she chose."
    So, Ken's strategy is very simple:

  • If I have a heavier one, choose the lightest one I can get a point.
  • Otherwise, I choose the lightest on and get none point.
    • And Naomi's best strategy is to choose each from heavier to lighter.

    In Deceitful War, Naomi's strategy is to make each block as useful as possible.
    If the lightest one is than the lightest of Ken's,
    Naomi can say that it is very heavy, and Ken choose his lightest one, so Naomi get a point.
    Otherwise, Naomi can say it is a little lighter than Ken's heaviest one, and make Ken's situation worse.
    We can sort all the block and using to variable to indicate the lightest one and the heaviest one, and simulate
    the game to get the answer.