USACO 100 DP Problem 'cownum' Analysis

by Md. Mahbubul Hasan

Problem 'cownum' Analysis

The state of the DP is not that obvious.

While solving this problem by myself the first idea that came to mind is the 
obvious one, O(N^5) that is sliding window. We need 4 information in a state 
in this algorithm, [at which position are we (n)][number at n-1 th 
postion][number at n-2 th state][number at n-3 th state].

If we think a bit we can reduce this to O(N^4). In that case the state will be:
[at which position are we (n)][minimum of number at n-1 th and n-2 th
postion][minimum of number at n-2 and n-3 th position]. (Why it is a valid 
state 
information? - I am leaving this question as excercise for the readers)

But from here we cant see any obvious improvement. So we step back and return 
to drawing board. In worst case, N  = 1000. So it is quite obvious that 
the expected solution should be O(N^2). How can we represent a state by only 
two variables? One obvious variable is the position number. And what should be 
the other one? We must use the limit. Ok, lets start with this type of state:

[position][the highest limit of the ID].

And if we think a bit then we can realize that this will lead to O(N^2) 
solution. This is how it can be cracked down:

Say we will label the cows from rear. That means we are going to assign cow 
number from n'th cow.

[i][j] = number of ways we can label j cows by id 1 to i.

1st obvious choice is we can label j cows using id 1 to i-1. ([i-1][j])
2nd choice is we label last two cows by i. ([i-1][j-2])
3rd choice we can label last one i, and other j-1 less than i. ([i-1][j-1])
4th choice, we can label last one x (ranging from 1 to i-1) and second last 
one i. (sum x = 0 to i-2 cnt[x][j-2])

So our recurrence is:
[i][j] = [i-1][j] + [i-1][j-2] + [i-1][j-1] + sum (x = 0 to j-2) [i][j-2]

This leads to our desired O(N^2) algorithm. A sample code is given below which 
implements the above idea:

(Note that in our recurrance we still have a linear loop. To get rid of it i 
used another array scnt[][] that keeps information about the sum. There is 
certainly a way not using two different array. We can just simply switch our 
dp state to sum state. That means in the following code we could have just 
used scnt[][] to solve the problem!)

#include<stdio.h>

int i,j,N,M,cnt[1001][1001],scnt[1001][1001];

int main()
{
	freopen("cownum.in","r",stdin);
	freopen("cownum.out","w",stdout);

	scanf("%d%d",&N,&M);

/*Base Case*/
	for(i=1;i<=N;i++) cnt[0][i]=scnt[0][i]=0;
	for(i=0;i<=N;i++) {cnt[i][0]=1; scnt[i][0]=i+1;}
	for(i=1;i<=N;i++) {cnt[i][1]=i; scnt[i][1]=scnt[i-1][1]+i;}
/*Base Case*/

	for(j=2;j<=N;j++)
		for(i=1;i<=N;i++)
		{
			cnt[i][j]=(cnt[i-1][j]+cnt[i-1][j-2]+cnt[i-1][j-
1]+scnt[i-2][j-2])%M;
			scnt[i][j]=(scnt[i-1][j]+cnt[i][j])%M;
		}

	printf("%d\n",cnt[N][N]);

	return 0;
}