Perfect Memory

Problem name: Perfect Memory
Problem source: Topcoder, SRM 513, Div 1 - 500
Link: http://www.topcoder.com/stat?c=problem_statement&pm=11500 (Log in is required to see the problem)

In this problem you have a board having N * M cells. Each cell has a symbol in it's back. Each symbol is in exactly two cells in the board. So there will be (N * M) / 2 symbols. In each move you can turn two cells one by one to see the symbols behind them. If these two symbols differ, both the cell turned back to hide the symbols again. If both the symbols are same, they will remain same and never turn back again. What is the expected number of moves to make all the symbols visible, if you have the perfect memory?

Note that, having perfect memory, you'll never forget what was the symbol in a cell which you saw, but turned back. In this problem it's guaranteed that N * M will be even.

I couldn't solve this problem in real contest. I thought in each turn both of the cells will be turned simultaneously. But in the problem statement it was clearly mentioned that, two cells will be turned one by one. It seems that I am not the only one who got this wrong.

This problem can be solved by dynamic programming. Our state will be (total, seen, turn). Here,
total = number of symbols for which both cells are not seen yet i.e. at least one cell is unseen. So we are actually considering (2 * total) cells.
seen = number of symbols partially seen i.e. number of cells of which exactly one cell is seen.
turn = Is this the first turn or second turn of the move? We know each move consists of two turns.

Initially, total = (N * M) / 2, seen = 0, and turn = FIRST.

Boundary condition: If total = 0, we don't have any symbol left to consider, so expected number will be zero.

In state (total, seen, turn), we have (total * 2 - seen) cells we didn't see yet. Lets say unseen = total * 2 - seen.

Now if the turn = FIRST, here we will always open an unseen cell and two things can happen after turning a cell on.
1. With p1 probability the cell contains a symbol which is already seen in another cell.
2. With p2 probability the cell contains a new symbol which is not visible before.

Here,
p1 = seen / unseen
p2 = 1.0 - p1

If (1) happens, we will just turn on the other symbol we already saw, and both will remain open forever. So our new state will be (total - 1, seen - 1, FIRST) and one move will be completed.
If (2) happens, new state will be (total, seen + 1, SECOND)

exp_move(total, seen, FIRST) = p1 * (1 + exp_move(total - 1, seen - 1, FIRST)) +
p2 * (exp_move(total, seen + 1, SECOND)

Note that, in first option we completed a move, so added +1, but in second option move is not done yet.

If turn = SECOND, we'll open another unseen cell. Three things can happen
1. With probability p1, symbol in the SECOND turn matches with the symbol of the FIRST turn.
Here p1 = 1 / unseen
2. With probability p2, symbol in the SECOND move matches with a symbol which is previously seen, but not seen in the first turn of this move. So,
p2 = seen / unseen - p1 = (seen - 1) / unseen
3. With probability p3, symbol in the SECOND move is completely a new symbol.
p3 = 1 - p2 - p3

If (1) happens, this pair will remain visible, so our state will be (total - 1, seen - 1, FIRST) and one move will be completed.
If (2) happens, this pair will be turned back, but we know both cells of the symbol of last turn. So we'll open both symbol in next move, so two moves will be completed in this case and new state will be (total - 1, seen - 1, FIRST).
If (3) happens, just another seen added. So state will be (total, seen + 1, FIRST), and one move will be completed.

exp_move(total, seen, SECOND) = p1 * ((exp_move(total - 1, seen - 1, FIRST) + 1) +
p2 * ((exp_move(total - 1, seen - 1, FIRST) + 2) +
p3 * ((exp_move(total, seen + 1, FIRST) + 1)

My solution in C++:

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <queue>
#include <cstring>
#include <set>
#include <ctime>
#include <cfloat>
using namespace std;

typedef long long i64;
#define I64 "%lld"
#define rep(i,n) for (i=0; i < (n); ++i)
#define all(c) (c).begin(),(c).end() 

bool done[1500][1500][2];
double memo[1500][1500][2];
enum{FIRST = 0, SECOND};
double exp_move(int total, int seen, int turn) {
    double &ret = memo[total][seen][turn];
    if (done[total][seen][turn]) return ret;
    done[total][seen][turn] = true;

    int unseen = total * 2 - seen;
    if (total == 0) return ret = 0;

    ret = 0.;
    
    // open one unseen cell randomly
    if (turn == FIRST) {
        double p1 = 0, p2 = 0;

        // Probability of it's pair is already seen is p1
        if (seen > 0) {
            p1 = (double) seen / (double) unseen;
            ret += p1 * (exp_move(total - 1, seen - 1, FIRST) + 1);
        }

        // Probability of it's pair is not seen yet is p2
        if (unseen > seen) {
            p2 = 1.0 - p1;
            ret += p2 * (exp_move(total, seen + 1, SECOND));
        }
    }
    else {
        double p1 = 0, p2 = 0, p3 = 0;

        // Probability of it's pair is already open is p1
        p1 = (double) 1 / (double) unseen;
        ret += p1 * (exp_move(total - 1, seen - 1, FIRST) + 1);

        // Probability of it's pair is seen but not open is p2
        if (seen > 1) {
            p2 = (double) (seen - 1) / (double) unseen;
            ret += p2 * (exp_move(total - 1, seen - 1, FIRST) + 2);
        }

        // Probability of it's pair is unseen is p3
        if (unseen > seen) {
            p3 = 1.0 - p1 - p2;
            ret += p3 * (exp_move(total, seen + 1, FIRST) + 1);
        }
    }
    return ret;
}

class PerfectMemory {
    public:
    double getExpectation(int N, int M) {
        return exp_move((N * M) / 2, 0, FIRST);
    }
};

Counting triangles

I'm going to discuss the analysis of the problem Counting triangles here.

Problem description is very short:

Consider a 2D integer grid with lower left corner at (0, 0) and upper right corner at (X, Y). We are interested in isosceles right triangles which all the 3 corners at the grid node (integer coordinates). Your task is to count the number of those triangles.

There was another problem with the same name: Counting Triangles, in which you have to count all the triangles within a grid having all the three corners in integer coordinate inside the grid. But in this problem you need not to count all of those triangles. You only need to count those triangles which are Isosceles triangle and Right triangle. Now, a triangle can have different shapes and same shaped triangle can have different rotations in the grid. We have to count them all carefully.

For simplicity, lets consider our triangle is OAB, where angle O is right angle, side OA and side OB are equal, so it fulfills both of the conditions above. lets consider the triangle such that, if we rotate OA clockwise in respect of O by 90 degrees then A will be reach to the exactly on the point B. lets consider the coordinate of A, B and O is (x1, y1), (x2, y2) and (x3, y3) respectfully, and also consider O is in the origin, i.e. (0, 0).

Now coordinate of A is (x1, y1) if we rotate it in respect of origin, by rotation matrix of 90 degrees we will get that x2 = y1 and y2 = -x1.

Here is the equation to calculate the coordinate of B form O and A.






You can find the rotation matrix for 90 degrees here.

We know that O (here origin) is an integer coordinate. By the above equation we found that if A is integer coordinate, then B will also be integer coordinate.

So we will brute force for all the integer coordinate for A and calculate the coordinate of B. By all I mean [-X, X] for x coordinate and [-Y, Y] for y coordinate, for other values of x or y, it will definitely occupy a bounding box which is larger than the given 2D grid. So the complexity of this brute force solution is O(X * Y), which is not too big.

In our brute force we will find several triangles OAB, and coordinates of their corner (x3, y3), (x1, y1) and (x2, y2) respectfully. Can you calculate the height and weight of the bounding box of this triangle?

Yes, it's very easy. Height is H = max(y1, y2, y3) - min(y1, y2, y3), and width is W = max(x1, x2, x3) - min(y1, y2, y3).

Now we can place this bounding box in our grid if H ≤ Y and W ≤ X, otherwise it will not fit in our grid and in the same way, our triangle will not fit in the grid. If we can place the bounding box in the grid, we can easily put the lower left corner of the bounding box in (0, 0), so the upper right corner will be (W, H). So, here we found one place where we can place our triangle as well. Can we place the same triangle in another way by shifting our bounding box horizontally or vertically? Yes we sometimes we can. if X is less than W we can shift it horizontally and find another position to place our triangle, in the same way we can shift it vertically if Y is less than H.

In general, for a given bounding box (W, H) we can place it in (X - W + 1) * (Y - H + 1) ways. So this calculation is simply O(1). We will sum up the values for all triangles we calculated by brute-forcing on coordinate A. So our overall complexity of this algorithm is O(X * Y).

Here is my function in java to solve this problem -

long my_solution(int X, int Y){
  if (X == 0 || Y == 0){
      return 0;
  }

  int x3 = 0;
  int y3 = 0;
  long count = 0;
  for (int x1 = -X; x1  <= X; x1 ++) {
      for (int y1 = -Y; y1  <= Y; y1 ++) {
          if (x1 == 0 && y1 == 0) continue;
        
          int x2 = y1;
          int y2 = -x1;
        
          int maxX = Math.max(x1, Math.max(x2, x3));
          int minX = Math.min(x1, Math.min(x2, x3));
          int maxY = Math.max(y1, Math.max(y2, y3));
          int minY = Math.min(y1, Math.min(y2, y3));
        
          int WIDTH = maxX - minX;
          int HEIGHT = maxY - minY;
        
          if (WIDTH > X || HEIGHT > Y) {
              continue;
          }
        
          count += (X - WIDTH + 1) * (Y - HEIGHT + 1);
      }
  }
  return count;
}

Warning:
The result can be big, don't rely on 32 bit integers.