another dp

TheSwap

framework for a dp solution

// memoization unit
int memo[][];

int main() {

  // reset memo
  memset(memo, 0, sizeof(memo));

  // calling subroutine to iteratively solve the problem
  return doit();
}


int doit(int n, int k ) {
  //if already visited state, return memo[][];
  if (memo[][] != 0) return memo[][];

  // if it is the stopping condition, return memo[] = ? //
  // e.g., k = 0 return n????

  // initialize return value
  int ret = 0; // -1 sometimes

  for(all the possible variables) {
    for(for the possible variables) {

      // pre-processing to get n_1

      // enter subproblem
      // comparison_funct, e.g., max, min, ++
      // note k-1 below, this identifies the subproblem
      ret = comparison_function(ret, doit(n_1, k-1) ) ; 

      // post-processing to get back n
      // we might need some processing to retrieve n in the original problem 
      n = f(n_1);
    }
  }

  // this state is visited, set it in the memo
  return ret = memo[][];

}

int doit(vector &v, int k) {
  int rv = get_v(v);

  // visited
  if(memo[rv][k] != 0) return memo[rv][k];

  if(k == 0) return memo[rv][k] = rv;

  int a = -1;
  for(int i = 0; i < v.size(); ++i) {
    for(int j = i+1; j < v.size(); ++j) {

      // excluded cases: highest digit does not swap with '0'
      if (j == v.size()-1 && v[i] == 0) continue;

      // pre-processing
      int tmp = v[i];
      v[i] = v[j], v[j] = tmp;
      // enter subproblem
      a = max(a, doit(v, k-1));

      // post-processing
      v[j] = v[i], v[i] = tmp;
    }
  }
      
  return memo[rv][k] = a;
}

For another problem in NumbersAndMaches.

const int dis[10][7] =
{
  {1, 1, 1, 0, 1, 1, 1},
  {0, 0, 1, 0, 0, 1, 1},
  {1, 0, 1, 1, 1, 0, 1},
  {1, 0, 1, 1, 0, 1, 1},
  {0, 1, 1, 1, 0, 1, 0},
  {1, 1, 0, 1, 0, 1, 1},
  {1, 1, 0, 1, 1, 1, 1},
  {1, 0, 1, 0, 0, 1, 0},
  {1, 1, 1, 1, 1, 1, 1},
  {1, 1, 1, 1, 0, 1, 1},
};


long long dp[20][127][127];

int _inc[10][10], _dec[10][10];

int k;
long long solve(long long N, int idx, int added, int removed) {
 
  if (dp[idx][added][removed] != -1) 
    return dp[idx][added][removed];

  if(N == 0) {
    if (added == removed && added <= k) {
      return 1LL;
    }
    return 0LL;
  }

  int i = N % 10;
  long long ret = 0;
  for(int j = 0; j <= 9; ++j) {
    ret += solve(N/10, idx+1, added + _inc[i][j], removed + _dec[i][j]);
  }
  return dp[idx][added][removed] = ret;
}
  
long long NumbersAndMatches::differentNumbers(long long N, int K)
{
    for (int i = 0; i < 10; i ++)
      for (int j = 0; j < 10; j ++)
      {
        _inc[i][j] = _dec[i][j] = 0;
        for (int k = 0; k < 7; k ++)
        {
          if (dis[i][k] < dis[j][k])
            _inc[i][j] ++;
          if (dis[i][k] > dis[j][k])
            _dec[i][j] ++;
        }
      }
    k = K;
    memset(dp, -1, sizeof(dp));
    return solve(N, 0, 0, 0);    
}

bitset and memoization

SRM 448 DIVII LEVEL 3

http://forums.topcoder.com/?module=Thread&threadID=651040&start=0

Let D(n,m) = number of ways to arrange the cards given that we have used "m" cards (m = bitmask representation) and the last card that was chosen was card n.

sscanf

to read in the numbers in the following string

string s = "1000 ml of water, weighing 1000 g"

int v;
sscanf(s, "%d ml of", &v);

size_t p = s.find(',');

int m;
sscanf(s.substr(p+2, s.length()-p).c_str(), "weighing %d", &m);

Note: the use of c_str() and sscanf()

STL comparison FUNCTOR

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm374

#include < iostream >
#include < vector >
#include < string >
#include < algorithm >
using namespace std;

bool isvowl(char c) {
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
    return true;
  return false;
  
}

struct word {
  string w;
  vector s1; //sorted
  vector s2; //unsorted
};

// comparison function
bool operator < (const word &a, const word &b) {
  if (a.s1 != b.s1) return a.s1 < b.s1;
  return a.s2 < b.s2;
}  

  
class SyllableSorting {
public:
  
  vector  sortWords(vector  words) {
    
    vector vw;

    
    for(int i = 0; i < words.size(); ++i) {
    
      vector syl;
      word W;
          
      string s("");
      s += words[i][0];
          
      for (int j = 1; j < words[i].length(); ++j) {
        char c = words[i][j];
        bool pv = isvowl(words[i][j-1]);
        bool v  = isvowl(c);
        if (pv) { //previous char is a vowl
          if (v)
            s += c;
          else {
            syl.push_back(s);
            s = c;
          }
        } else {  // previous char is a consonant
          s += c;
        } 
      }
      syl.push_back(s);
      
      for(int k = 0; k < syl.size(); ++k)
        cout << syl[k] << "  ";
      cout << endl;
      
      W.w = words[i];
      
      W.s2 = (syl);
      
      sort(syl.begin(), syl.end());
      
      W.s1 = (syl);
           
      vw.push_back(W);
    
    }
    
    sort(vw.begin(), vw.end());
    vector ret;
    for(int i = 0; i < vw.size(); ++i)
      ret.push_back(vw[i].w);
    return ret;
  }
};

Coin toss and Absorbing Markov Chain

http://www.mitbbs.com/mitbbs_bbsdoc_div_article.php?board=Quant&gid=31212871


A fair coin is flipped until the first time one of the following two
patterns appeared: TTH or HTH
ask: which one you should choose for a better chance to win


+ TT = .5 TTH + .5 TT
| HT = .5 HTH + .5 TT
| T = .5 TT + .5 H
| H = .5 HT + .5 H
+ S = .5 T + .5 H

If we let TTH = 1 and HTH = 0, we finally get S = 5/8 (the probability of reaching TTH first)
or otherwise
we let HTH = 1 and TTH = 0, we finally get S = 3/8 (the probability of reaching HTH first)



We start from the definition of Absorbing Markov Chain.
REF: Chap 11, Markov Chains, from www.dartmouth.edu/~chance/teaching


A state s_i of a Markov chain is called absorbing if it is impossible to leave it (i.e., p_ii = 1). A Markov chain is absorbing if it has at lease one absorbing state, and if from every state it is possible to go to an absorbing state (not necessarily in one step). The state that is not absorbing is called transient.

The interesting questions about an absorbing Markov chain are:

- What is the probability that the process will eventually reach a given absorbing state?
- On the average, how long will it take for the process to be absorbed?
- On the average, how many times will the process be in each transient state?

In general, the answers to all questions depends on
- the state from which the process starts
- the transition probabilities.
The answers to the above questions are the theorems listed below.

We first write the transition matrix in canonical Form by explicitly write Q and R.

      TT           T         S         H         HT
Q =

TT    0.5000         0         0         0         0
 T    0.5000         0         0    0.5000         0
 S         0    0.5000         0    0.5000         0
 H         0         0         0    0.5000    0.5000
HT    0.5000         0         0         0         0


       TTH       HTH
R =   

TT    0.5000         0
 T         0         0
 S         0         0
 H         0         0
HT         0    0.5000

Theorem: For an absorbing Markov chain the matrix I-Q has an inverse N = I + Q + Q^2 + .... The ij-entry of the matrix N is the expected number of times the chain is in state s_j, given that it starts in state s_i.

>> N = inv(eye(5)-Q)

N =

    2.0000         0         0         0         0
    1.5000    1.0000         0    1.0000    0.5000
    1.2500    0.5000    1.0000    1.5000    0.7500
    1.0000         0         0    2.0000    1.0000
    1.0000         0         0         0    1.0000

By reading the first line of N, we know that starting from TT, the expected number of times we still in TT is 2.

Theorem: The sum of row i of N is the expected number of steps before the chain is absorbed given that the chain starts in state s_i.

>> t = N*ones(5,1)

t =

     2
     4
     5
     4
     2

So starting from S, the expected number of steps before absorbing in either TTH or HTH is 5.

Theorem: Let b_ij be the probability that an absorbing chain will be absorbed in the absorbing state s_j if it starts in the transient state s_i. Let B be the matrix with entries b_ij. Then B is an txr matrix, and

B = NR,

where N is the fundamental matrix and R is as in the canonical form.

>> B = N*R

B =

    1.0000         0
    0.7500    0.2500
    0.6250    0.3750
    0.5000    0.5000
    0.5000    0.5000

Thus starting from S, we have probability of 0.625 = 5/8 to be absorbed into state TTH and probability of 0.375 = 3/8 to be absorbed into state HTH.



Now let us consider adding another absorbing state THT. The transition graph is as below:

Q =      S         T         H        TH        HT        TT

         0    0.5000    0.5000         0         0         0     S
         0         0         0    0.5000         0    0.5000     T
         0         0    0.5000         0    0.5000         0     H
         0         0    0.5000         0         0         0     TH
         0         0         0         0         0    0.5000     HT
         0         0         0         0         0    0.5000     TT

R =    THT       HTH       TTH

         0         0         0  S
         0         0         0  T
         0         0         0  H
    0.5000         0         0  TH
         0    0.5000         0  HT
         0         0    0.5000  TT

>> N = inv(eye(6)-Q)

N =

    1.0000    0.5000    1.2500    0.2500    0.6250    1.1250
         0    1.0000    0.5000    0.5000    0.2500    1.2500
         0         0    2.0000         0    1.0000    1.0000
         0         0    1.0000    1.0000    0.5000    0.5000
         0         0         0         0    1.0000    1.0000
         0         0         0         0         0    2.0000

>> N*ones(6,1)

ans =

    4.7500 S
    3.5000 T
    4.0000 H
    3.0000 TH
    2.0000 HT
    2.0000 TT

>> B = N*R

B =    THT       HTH       TTH

    0.1250    0.3125    0.5625  S
    0.2500    0.1250    0.6250  T
         0    0.5000    0.5000  H
    0.5000    0.2500    0.2500  TH
         0    0.5000    0.5000  HT
         0         0    1.0000  TT
 

protected data or private data

http://www.parashift.com/c++-faq-lite/basics-of-inheritance.html

Here's the way I say it: if I expect derived classes, I should ask this question: who will create them? If the people who will create them will be outside your team, or if there are a huge number of derived classes, then and only then is it worth creating a protected interface and using private data. If I expect the derived classes to be created by my own team and to be reasonable in number, it's just not worth the trouble: use protected data. And hold your head up, don't be ashamed: it's the right thing to do!

The benefit of protected access functions is that you won't break your derived classes as often as you would if your data was protected. Put it this way: if you believe your users will be outside your team, you should do a lot more than just provide get/set methods for your private data. You should actually create another interface. You have a public interface for one set of users, and a protected interface for another set of users. But they both need an interface that is carefully designed — designed for stability, usability, performance, etc. And at the end of the day, the real benefit of privatizing your data (including providing an interface that is coherent and, as much as possible, opaque) is to avoid breaking your derived classes when you change that data structure.

But if your own team is creating the derived classes, and there are a reasonably small number of them, it's simply not worth the effort: use protected data. Some purists (translation: people who've never stepped foot in the real world, people who've spent their entire lives in an ivory tower, people who don't understand words like "customer" or "schedule" or "deadline" or "ROI") think that everything ought to be reusable and everything ought to have a clean, easy to use interface. Those kinds of people are dangerous: they often make your project late, since they make everything equally important. They're basically saying, "We have 100 tasks, and I have carefully prioritized them: they are all priority 1." They make the notion of priority meaningless.

Repeated Squaring

http://www.algorithmist.com/index.php/Repeated_Squaring

Repeated squaring, or repeated doubling is an algorithm that computes integer powers of a number quickly. The general problem is to compute xy for an arbitrary integer y.

 

// Calculates n to the p power, where p is a positive number.
func power( var n as integer, var p as integer )
   if p = 0 return 1
   if p = 1 return n
   if p is odd
      return n * power( n * n, (p-1) / 2 )
   else
      return power( n * n, p / 2 )
end func

quadtree

http://en.wikipedia.org/wiki/Quadtree

UVa problem: 297: Quadtrees

refer to forum: http://acm.uva.es/board/viewtopic.php?f=2&t=700&p=2691&hilit=297&sid=156699fafa75aaeacf281e1af3a8006c#p2691

#include <iostream>

#define M 32
int p[M];
int idx;

int mask[] = {
  0, 0x1, 0x3, 0, // 0-3
  0xf, 0, 0, 0, 0xff, //4-8
  0,0,0,0,0,0,0,0xffff, // 16
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0xffffffff // 32
};

#ifndef ONLINE_JUDGE
// couting 1's
int count_bit(int n) {
    int bits = 0;
    while(n) {
        n &= n-1;
        ++bits;
    }
    return bits;
}
#endif

void color (char *str, int size, int x, int y) {
  if (str[idx] == 'p') {
    idx ++;
    int sz = size>>1;
    color(str, sz, x+sz, y);
    color(str, sz, x, y);
    color(str, sz, x, y+sz);
    color(str, sz, x+sz, y+sz);
  }
  else if (str[idx] == 'f') {
    idx ++;
    for (int i = y; i < y + size; i ++)
      p[i] |= mask[size] << x;
  }
  else idx++;
}
int main () {
  int num;
  char tree1[1500], tree2[1500];

  scanf("%d\n", &num);
  while(num--) {
    scanf("%s\n%s\n", tree1, tree2);

    memset(p, 0, sizeof(p));

    idx=0;
    color(tree1, M, 0, 0);

    idx=0;
    color(tree2, M, 0, 0);

    int total = 0;
    for (int i = 0; i < M; i ++)
#ifndef ONLINE_JUDGE
      total += count_bit(p[i]);
#else
      total += __builtin_popcount(p[i]);
#endif

    printf("There are %d black pixels.\n", total);
  }
  return 0;
}

UVa problem: 752 - Unscrambling Images

#include <iostream>
#include <deque>
using namespace std;
int q[16][16];
int e[16][16]; // encrypted

int d[16][16]; // decoded
inline int getxy(int size, int k, int &x, int &y) {

  deque<int> Q;
  while(k > 0) {
    int r = k % 4;
    if (r == 0) {
      r = 4;
      k = (k-4) >> 2;
    } else
      k = k >>2;

    Q.push_front(r);
  }

  x = 0, y = 0;
  for(int i = 0; i < Q.size(); ++i) {
    size = size >> 1;
    int idx = Q[i];

    if (idx == 2)
      y += size;
    if (idx == 3)
      x += size;
    if (idx == 4) {
      x += size;
      y += size;
    }
  }
  return size;
}

int main() {
  int ndata;
  scanf("%d ", &ndata);
  int nd = 1;
  while(nd <= ndata) {
    if(nd > 1) printf("\n");
    printf("Case %d\n\n", nd++);
    int n;
    scanf("%d ", &n);

    // quadtree reset to all 0
    memset(q, 0, sizeof(q));

    int m; // number of leaf nodes

    scanf("%d ", &m); 
    int k;
    int intensity;
    for(int i = 0; i < m; ++ i) {
      scanf("%d %d ", &k, &intensity);
      int x, y;
      int size = getxy(n, k, x, y);

      for(int i = x; i < x+size; ++i)
        for(int j = y;j < y+size; ++j)
          q[i][j] = intensity;      
    }
/*
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j)
        printf("%4d", q[i][j]);
      printf("\n");
    }
    printf("\n");
*/
    scanf("%d ", &m);

    // encrypted quadtree reset to all 0
    memset(e, 0, sizeof(e));
    for(int i = 0; i < m; ++ i) {
      scanf("%d %d ", &k, &intensity);
      int x, y;
      int size = getxy(n, k, x, y);

      for(int i = x; i < x+size; ++i)
        for(int j = y;j < y+size; ++j)
          e[i][j] = intensity;
    }

    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j) {
        int x = q[i][j] / n;
        int y = q[i][j] % n;
        d[x][y] = e[i][j];
      }
    }
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j)
        printf("%4d", d[i][j]);
      printf("\n");
    }
  }
}