Optimal way to annihilate a list by removing items from the ends

Question

I'm stuck with a contest problem.

Description:

What is the minimum number of moves to annihilate an int array where the possible moves are:

• Remove both the first and last elements if they are equal to each other, or
• Remove the first element, or
• Remove the last element.

Input

The first line is the number of test cases (less than or equal to 200).

For any test case there is two lines.

• Line 1 has 1 integer with the size of the vector. (The size never exceeds 1000)
• Line 2 has n integers with the values of the vector. (Values never greater than 10⁹)

Ouput

The output must show the test case number with the minimum value of remove steps.

Input Example:

3
5
1 3 1 3 2
5
1 2 3 2 1
7
1 1 2 3 3 4 2

Output Example:

Case #1: 4  
Case #2: 3  
Case #3: 5

My solution is brute-force and recursive, with memorization:

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int minOf2(int x, int y){
    return (x < y) ? x : y;
}

int minOf3(int x, int y, int z){
    return minOf2(z,minOf2(x,y));
}


int memoization[1010][1010];

int recur(unsigned long long *arr,int i,int j){
    if(i > j){
        return 0;
    }
    int aux = INT_MAX;
    if(arr[i] == arr[j]){
        aux = recur(arr,i+1,j-1);
    }
    if(memoization[i][j])
        return memoization[i][j];
    else
        return memoization[i][j] = 1 + minOf3(aux,recur(arr,i+1,j),recur(arr,i,j-1));
}

int main()
{
    int t,n,i,j;
    unsigned long long arr[1010];
    scanf("%d",&t);
    for (i = 1; i <= t; i++) {
        memset(memoization,0,sizeof(memoization));
        scanf("%d",&n);
        for (j = 0; j < n; j++) {
            scanf("%llu",&arr[j]);
        }
        printf("Case #%d: %d\n",i,recur(arr, 0, n-1));
    }
    return 0;
}

This solution is still getting "Time Limit Exceeded".

Answer 1

Missing use of memoization

Your program is almost right, but you aren't using your memoization to the fullest potential. When the array ends match, you don't check for the memoized value. Therefore, a stress test of an array of 1000 elements with all the same values causes your program to run for a very long time.

Also, another optimization is that when the array ends match, you can always remove 2 instead of also trying to remove just 1 end (which can only be equal or worse than removing both ends).

Other things to note

Your use of 1010 as an array size is a bit odd. First of all, you can use exactly 1000 as the problem stated. Maybe you were afraid of a buffer overflow, but there isn't any. Also you could use a #define instead of copy/pasting the value all over the place. That way you could easily change the test size without accidentally missing one place or another.

You don't need to use long long for your array. An int can hold values up to 10^9.

Corrected function

Here is your function with the memoization corrected:

int recur(unsigned int *arr,int i,int j){
    if(i > j){
        return 0;
    }
    if(memoization[i][j])
        return memoization[i][j];
    if(arr[i] == arr[j])
        return memoization[i][j] = 1 + recur(arr,i+1,j-1);
    return memoization[i][j] = 1 + minOf2(recur(arr,i+1,j),recur(arr,i,j-1));
}

I made an array of 1000 elements all the same value and ran the function 10 times. With the original code, it took 9.6 seconds. With the corrected code it took 0.04 seconds.