Friday fun with a dynamic program.

Its been almost an year I wrote my personal blog. I missed so many fun things I used to do as student. Well I'm a pursuit of relentless improvement. Today I just wanted to write a dynamic program --  which I have missed for a while -- so I randomly pick one of the hardest DIV-1 problems and got the dynamic program working. This is a very interesting dynamic program -- a two level one. You can read the problem -- because I cannot' post here-- from this link http://community.topcoder.com/stat?c=problem_statement&pm=1996&rd=4710 . Following is my code which passed all the 88 system tests.

/*
 * Solution to  problem: http://community.topcoder.com/stat?c=problem_statement&pm=1996&rd=4710 (SRM-178, DIV-1, hard)
 *
 * Vamsi K. Kundeti 10/05/2012
 *
 **/
#include
#include
#include
#include
#include

using namespace std;
#define MAX_ROWS 50
#define MAX_STROKES 3000
class MinPaint {
   private:
      /*Optimal number of mismatches to color a row 'i' till 'j' with a
       *stoke ending black using 'k' strokes : 'm_aB[j%2][i][k]'
       */
      size_t m_aB[2][MAX_ROWS][MAX_STROKES];
      size_t m_aW[2][MAX_ROWS][MAX_STROKES];
      /*Optimal number of mismatches in the image upto row 'i' using 'k' 
       *strokes*/
      int m_aOPT[2][3001];
      //optimal value is stored in m_aB[0][i][j]
      vector m_aImg;

   public:
      MinPaint(): m_aB(), m_aW(), m_aImg() {}

      void initRow(size_t idx, size_t maxStrokes){
         for(size_t j=0; j<=maxStrokes; j++){
            m_aB[0][idx][j] = !j ? 1 : m_aImg[idx][0] == 'W';
            m_aW[0][idx][j] = !j ? 1 : m_aImg[idx][0] == 'B';
         }
      }
      size_t findMin(size_t a, size_t b){
         return a < b ? a : b;
      }
      void dynamicProgramPerRow(size_t idx, size_t maxStrokes){
         initRow(idx, maxStrokes);
         for(size_t i=1; i < m_aImg[idx].size(); i++){
            for(size_t j=0; j <= maxStrokes; j++){
               if(m_aImg[idx][i] == 'W'){
                  m_aW[i%2][idx][j] = !j ? i+1 : 
                     findMin(m_aW[(i-1)%2][idx][j], m_aB[(i-1)%2][idx][j-1]);
                  m_aB[i%2][idx][j] = !j ? i+1 : 
                     findMin(m_aB[(i-1)%2][idx][j]+1, m_aW[(i-1)%2][idx][j-1]+1);
               }else{
                  m_aB[i%2][idx][j] = !j ? i+1 : 
                     findMin(m_aB[(i-1)%2][idx][j], m_aW[(i-1)%2][idx][j-1]);
                  m_aW[i%2][idx][j] = !j ? i+1 : 
                     findMin(m_aW[(i-1)%2][idx][j]+1, m_aB[(i-1)%2][idx][j-1]+1);
               }
            }
         }
         //choose the min between m_aB and m_aW
         size_t nidx = m_aImg[idx].size()-1;
         for(size_t i=0; i<=maxStrokes; i++){
            m_aB[nidx%2][idx][i] = findMin(m_aB[nidx%2][idx][i], 
               m_aW[nidx%2][idx][i]);
         }
      }

      int leastBad(const vector &Img, const int &maxStrokes){
         m_aImg = Img;
          for(size_t i=0; i< Img.size(); i++){
            dynamicProgramPerRow(i, (size_t)maxStrokes);
         }

         //now find the optimal across rows//
         for(int i=0; i<=maxStrokes; i++){
            m_aOPT[0][i] = m_aB[(Img[0].size()-1)%2][0][i];
         }

         for(size_t j=1; j<Img.size(); j++){
            /*choose number of strokes from [1, maxStrokes-j] to paint row 'j'*/
            size_t rsize_idx = m_aImg[j].size()-1;
            for(int usedStrokes=0;  usedStrokes<=maxStrokes; usedStrokes++){
               int min = numeric_limits::max();
               int current_min;
               int min_k=0;
               for(int k=0;  k<=usedStrokes; k++){
                  //use 'k' strokes to color current row 'j' and 'usedStrokes-j' for the
                  //array below 'j'.
                  current_min = 
                     m_aOPT[(j-1)%2][usedStrokes-k] + (m_aB[(rsize_idx)%2][j][k]);
                  if(current_min < min){
                     min = current_min;
                     min_k = k;
                  }

               }
               m_aOPT[j%2][usedStrokes] = min;
            }
         }
         return m_aOPT[(Img.size()-1)%2][maxStrokes];
      }

      size_t OptPerRow(size_t idx, size_t maxStrokes){
         return m_aB[(m_aImg[idx].size()-1)%2][idx][maxStrokes-1];
      }
};
/*INPUT FILE FORMAT:
 * 
 *
 * X Y
 * string1
 * string2
 * ...
 * ...
 * ...
 * stringX
 *
 *X is the number of rows
 *Y is the maximum number of strokes
 **/
int main(int argc, char **argv){
   char buf[4096];
   vector input;
   size_t imgSize, maxStrokes;
   MinPaint X;

   while(scanf("%lu%lu", &imgSize, &maxStrokes)==2){
      input.clear();
      while(imgSize-- && scanf("%s", &buf) == 1){
         input.push_back(string(buf));
      }
      int opt = X.leastBad(input, maxStrokes);
      printf("%d\n", opt);
   }
}

Have fun -- because you can afford it only on a Friday.

Vamsi.