Halloween Costumes

This is a problem from recently held ACM ICPC Dhaka Regionals. You can find the problem here -
http://acm.uva.es/archive/nuevoportal/region.php?r=as9&year=2010

The problem can be reduced to this -

Find minimum number of push operations needed to build a number sequence by printing the top element of the stack.

For example, if the sequence to be built is -

1 2 1 1 3 2 1 

We can do it through the following steps -

1. Push 1 into stack and print top [Current Stack : 1]
2. Push 2 into stack and print top [Current Stack : 1 2]
3. Push 1 into stack, print top twice and pop it from stack [Current Stack : 1 2]
4. Push 3 into stack, print top and pop it from stack [Current Stack : 1 2]
5. Print top & pop 2 from stack [Current Stack : 1]
6. Print top [Current Stack : 1] 

As we can see, we'll require 4 push operations here.

I have used dynamic programming to solve this problem. The key idea is to optimally use push and pop operations so that we can re-use elements from the stack. Note that if we want to re-use a portion of the stack, like '1 5 2', these elements need to appear in that order as a subsequence of the original sequence and in reverse order (2 5 1) from the element where the first subsequence ended.

When we're trying to find optimal solution between 2 start and end indexes of the sequence, we have the following options -

1. Push, print and pop the first element of the sequence. Find the optimal solution for the rest of the sequence.
2. Find the optimal solution for the sequence [start, end-1] and then push, print and pop the last element.
3. For each element that matches the first number, we can push the first number into the stack and try to optimally solve the 2 subsequence created before and after the element we're considering.

The source code would certainly make things more clear - 

/*
Problem Name : Halloween Costumes
Problem Number : Archive 4857
Link   : http://acm.uva.es/archive/nuevoportal/region.php?r=as9&year=2010
Problemsetter : Manzurur Rahman Khan
Problem Type : Dynamic Programming, Building a sequence using stack operations (minimum number of pushes)
Difficulty  : Medium
Complexity  : O(N^3)
Date   : November 10, 2010
*/

#include <stdio.h>

#define rep(i,n) for(i = 0; i < (n); i++)
#define min(a,b) (((a)<(b))?(a):(b))

#define MAXN 100
#define INF 10234567

int N,M;
int ct[MAXN+2]; //original input array
int c[MAXN+2]; //sanitized input array
int dp[MAXN+2][MAXN+2];

// create a new sequence such that same number does not appear consecutively
// for example - 1 1 2 3 3 4 2 2 1 would become 1 2 3 4 2 1
void sanitize() {
 int i,j;
 int n = 0;
 rep(i,N) {
  c[n++] = ct[i];
  for(j=i;j<N;j++) {
   if(ct[i] != ct[j]) break;
  }
  i = j - 1;
 }
 N = n;
}

// recursive function to calculate and memoize the result
// a and b are start and end index of the sequence
int go(int a, int b) {
 if(a > b) return 0;
 if(dp[a][b] < INF) return dp[a][b];
 if(a == b || a+1 == b) return dp[a][b] = (b-a+1);
 int &ret = dp[a][b];
 ret = min(ret, 1 + go(a+1,b));
 ret = min(ret, 1 + go(a,b-1));
 if(c[a] == c[b]) ret = min(ret, 1 + go(a+1,b-1));
 int i;
 
 for(i = a+1; i <= b; i++) if(c[i] == c[a]) {
  ret = min(ret, 1 + min( go(a+1,i-1), go(a,i-1)-1 ) + min( go(i,b)-1, go(i+1,b) ) );
 }

 return ret;
}

int main() {
 int T,kase=1;
 int i,j;
 int res;
 scanf(" %d",&T);
 while(T--) {
  scanf(" %d %d",&N,&M);
  rep(i,N) scanf(" %d",&ct[i]);
  sanitize();
  rep(i,N) rep(j,N) dp[i][j] = INF;
  res = go(0,N-1);
  printf("Case %d: %d\n",kase++,res);
 }
 return 0;
}