[codejam] veterans-2013 oceanview (not complete)

// https://code.google.com/codejam/contest/2334486/dashboard#s=p2

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <tuple>
#include <unordered_map>
#include <fstream>

using namespace std;

typedef size_t hash_t;
typedef tuple<int,int,int> mykey_t;


template<typename T>
inline void hash_combine(hash_t & H, const T v)
{
    std::hash<T> hash_fn; // standard hash function
    H ^= hash_fn(v) + 0x9e3779b9 + (H<<6) + (H>>2);
}

// hash function for partial hash
class mykey_hash_fn {
public:
    size_t operator ()(const mykey_t &v) const
    {
        hash_t H = 0;
        hash_combine(H, std::get<0>(v));
        hash_combine(H, std::get<1>(v));
        hash_combine(H, std::get<2>(v));

        return H;
    }
};

class mykey_eq{
public:
    bool operator ()(const mykey_t &a, const mykey_t &b) const
    {
        return std::get<0>(a) == std::get<0>(b) &&
            std::get<1>(a) == std::get<1>(b) &&
            std::get<2>(a) == std::get<2>(b);
    }
};

typedef unordered_map<mykey_t, int, mykey_hash_fn, mykey_eq> cache_t;


int maxIncrSubSeq(vector<int> & A, size_t pos, int maxSoFar, int lenSoFar, cache_t & cache)
{
    if(pos >= A.size()) { return lenSoFar; }

    auto key = make_tuple(pos, maxSoFar, lenSoFar);
    cache_t::iterator it = cache.find(key);
    if(it != cache.end()) { return it->second; }

    int L1 = 0, L2 = 0;

    if(A[pos] > maxSoFar)
    {
        L1 = maxIncrSubSeq(A, pos + 1, A[pos], lenSoFar + 1, cache);
    }

    L2 = maxIncrSubSeq(A, pos + 1, maxSoFar, lenSoFar, cache);
    int ret = max(L1, L2);
    cache[key] = ret;
    return ret;

}

int _tmain(int argc, _TCHAR* argv[])
{
    int T;

    ifstream fin(argv[1]);

    fin >> T;

    for(int t = 1; t <= T; ++t)
    {
        int N;
        fin >> N;
        vector<int> A(N);
        for(int i = 0; i < N; ++i)
        {
            int h;
            fin >> h;
            A[i] = h;
        }
        int L = maxIncrSubSeq(A, 0, 0, 0, cache_t());
        cout << "Case #"<< t << ": " << N - L << '\n';
    }

    return 0;
}