## Friday, October 05, 2012

### 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));
}
printf("%d\n", opt);
}
}



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

Vamsi.