Rotate

Code up rotate routine, and then detect win conditions for horionzal, vertical, and diagonal

Pseudo code for rotate

  for col from 0 to n - 1
    oldCol = n - 1
    oldRow = n - col - 1
    for row from n -1 to 0
      while(oldCol >= 0 && old[oldRow][oldCol] == '.')
        oldCol--;

      if (oldCol >= 0)
        new[row][col] = old[oldRow][oldCol]

Pseudo code for check

  for row from 0 to n -1
    for col from 0 to n - 4 
      color = new[row][col];
      if (color == '.')
        continue;
      for i from 1 to 3
        if '.' or color, go to next col

Make it smooth

My approach, which is WRONG. Put here just for the record

  1. If an array is smooth, all subarrays must be smooth

  2. However, reverse can not be said to be true, because the ends of two smooth subarries may have too huge difference => we need to include the actual number as well!

  3. You will never delete and then insert, or vice versa, never insert and update, never update and delete, never update and update, because compress them into 1 step can only save cost. i.e., if we have a list of final ops, the order of applying them does not matter, because there is no dependency between steps

  4. Suppose we have a smooth subarray from 1 to n, with end value v. to make i+1 smooth with end value v1. change the value of a[i+1] to match smoothness range of subarray a[i]

  5. Note we do not attempt to change a[i], because a different end value for position i would cover this case already.

  6. To change a[i+1] to a specific value v, we can either delete and then insert, or do a plain update. We will pick the min choice.

Pseudo code

  Speical case i = 1, only deletion and insertion vs update case

  for i = 2 to N
    for tailVal = 0 to 255
      for newTailVal = 0 to 255
        cost[i][newTailVal] = convertCost(a[i], newTailVal, tailVal) + cost[i - 1][tailVal]

Now we need to design convertCost(fromV, toV, tailVal)

  1. If toV is within the M range of tailVal we either delete fromV and then insert toV, or update fromV, which ever is cheaper

  2. Otherwise, toV is outside M range of tailVal. if toV > tailVal, total cost = convertCost(fromV, toV - M, tailVal) + insertion cost else if toV < tailV total cost = convertCost(fromV, toV + M, tailVal) + insertion cost

The key insight here is that in induction, we limit our steps as much as we can to help discover insight, so long as our # of states will not cause stack overflow problem. But we can compress the +/- into a multiple of Ms to reduce # of states

Number Game

Note that Each step is similar to gcd calculation

Consider the special case: where A,B are co-prime => turns out useless

Consider the simple case, and try to reduce to that case, and w.l.g, assume A > B. Note that state is symmetric along the diagonal

  1. B< A <= 2 * B, and the next step must be (A -B, B), i.e., state(A, B) = !state(A-B, B) when B < A <= 2 * B.

  2. A > 2 * B, state(A,B) is winning if any of (A-B ….A-KB, B) is losing while A-KB > 0, and it is losing if ALL of (A-B…A-KB, B) are winning if A-KB > 0. But there must exist j s.t. B <= A-j * B <= 2 * B, i.e., we can try both state(A -j B, B) and state(A - j B -B, B). But by 1), one of them is losing, and one of them is winning, i.e., A can not lose!

  3. Consider A = B, it is a losing state, since we have to reach 0 ourselves

  4. A < B is same as case 1 and 2

I failed to solve the large case, which involves Fibonacci number and golden ratio

Claim: (A, B) is winnning iff A > phi * B, note because A, B are integers, impossible to have A = phi * B

Proof: Induction on A, w.l.g., assume A >= B A > 2 * B, reuse the preivous solution, A is winning for sure

2B >= A > phi *B, only choice left is go (B, A -B), i.e. B >= A -B > (phi - 1) B i.e., B < phi * (A - B), with B > A - B, by induction, B is losing, i.e., A is winning

If phi * B > A >= B, only choice is (B, A-B) with B > phi * (A-B), by induction, B must be winning and A must be losing!