DateFormat.cpp

#include <bits/stdc++.h>
#define debug(args...) // Just strip off all debug tokens
using namespace std;

// CUT begin
#undef debug
#define debug(args...) {dbg,args;cout<<endl;}
struct debugger{template<typename T> debugger& operator ,(const T& v){cout<<v<<" ";return *this;}}dbg;
template <typename T1,typename T2> inline ostream& operator<<(ostream& os,const pair<T1,T2>& p){return os<<"("<<p.first<<", "<<p.second<<")";}
template<typename T>inline ostream&operator<<(ostream& os,const vector<T>& v){string delim="[";for(unsigned int i=0;i < v.size();i++){os<<delim<<v[i];delim=", ";}return os<<"]";}
template<typename T>inline ostream&operator<<(ostream& os,const set<T>& v){string delim="[";for (typename set<T>::const_iterator ii=v.begin();ii!=v.end();++ii){os<<delim<<*ii;delim=", ";}return os<<"]";}
template<typename T1,typename T2>inline ostream&operator<<(ostream& os,const map<T1,T2>& v){string delim="[";for (typename map<T1,T2>::const_iterator ii=v.begin();ii!=v.end();++ii){os<<delim<<*ii;delim=", ";}return os<<"]";}
// CUT end

//vector<vector<string>> dp;

class DateFormat {
public:
    vector<string> mysplit(string s, char c) {
        vector<string> ret;
        int i=0;
        while(i<s.size()) {
            int j=s.find(c, i);
            if(j==-1) {
                ret.push_back(s.substr(i));
                break;
            } else {
                ret.push_back(s.substr(i, j-i));
            }
            i=j+1;
        }
        return ret;
    }

    int mysti(string s) {
        stringstream ss;
        ss<<s;
        int ret;
        ss>>ret;
        return ret;
    }
    
    string myswap(string s) {
	string F = s.substr(0, 2);
	string S = s.substr(3, 2);
	return S+'/'+F;
    }

    bool myValidUS(string s) {
	vector<int> days_in_month = {'h', 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	
	string m = s.substr(0, 2);      
        int mi = mysti(m);
        string d = s.substr(3, 2);
        int di = mysti(d);

	if(mi>12) return false;
	if(di>days_in_month[mi]) return false;
	return true;
    }
    
    vector<string> possibles(string s) {//to usa
	string s2 = myswap(s);
	vector<string> ret;
	if(myValidUS(s)) ret.push_back(s);
	if(myValidUS(s2)) ret.push_back(s2);
	sort(ret.begin(), ret.end());
	return ret;
    }

    bool increasingp(const string& s) {
	vector<string> vs = mysplit(s, ' ');
	for(int i=1; i<vs.size(); ++i) {
	    if(vs[i]<=vs[i-1])
		return false;
	}
	return true;
    }
    
    string fromEuropeanToUs(vector<string> dateList) {
	/*
	  my mistake:
	  only greedy was enough , here I have implemented a dp solution starting at end of vs
	  a greedy starting at beginning of vs is enough
	 */
	string dl;
	for(int i=0; i<dateList.size(); ++i)
	    dl += dateList[i];
	vector<string> vs = mysplit(dl, ' ');
	int N = vs.size();
	//	debug(vs);
	
	vector<vector<string>> dp(N+1);
	//sentinel:
	dp[N-1] = possibles(vs[N-1]);
	
	for(int i=N-2; i>=0; --i) {
	    //debug("i=", i, "#################################");
	    vector<string> ati = possibles(vs[i]);
	    
	    for(int j=0; j<ati.size(); ++j) {
                for(int k=0; k<dp[i+1].size(); ++k) {
		    string run = ati[j] + " " + dp[i+1][k];
		    if(increasingp(run)) {
			dp[i].push_back(run);
			break;
			//		debug(run);
		    }
		}
	    }
	}
	vector<string> at0 = dp[0];
	//	debug(at0);
	sort(at0.begin(), at0.end());

	if(at0.size() == 0) return "";
	else return at0[0];
    }
};

// CUT begin
//------------------------------------------------------------------------------
const double CASE_TIME_OUT = 2.0;

bool disabledTest(int x)
{
    return x < 0;
}
template<class I, class O> vector<pair<I,O>> getTestCases() { return {
    { { {"16/01"} }, {"01/16"} },
    { { {"02/01 08/02 08/02 21/09 06/11"} }, {"01/02 02/08 08/02 09/21 11/06"} },
    { { {"08/02 08/02 03/04"} }, {""} },
    { { {"2","9/02"," 08/","03 01/08"} }, {"02/29 03/08 08/01"} },
    { { {"17/01 05/05 03/07 07/24 23/09 09/30 01/11 11/11"} }, {"01/17 05/05 07/03 07/24 09/23 09/30 11/01 11/11"} },
    { {{"01/01 02/01 03/01 04/01 05/01 06/01 01/07 01/08 09", "/01 01/10 01/11 12/01 13/01 01/14 01/15 16/01 01/1", "7 18/01 19/01 20/01 21/01 01/22 23/01 24/01 25/01 ", "01/26 27/01 01/28 01/29 01/30 01/31 01/02 02/02 02", "/03 04/02 02/05 06/02 02/07 08/02 02/09 02/10 11/0", "2 12/02 13/02 14/02 15/02 02/16 17/02 02/18 19/02 ", "20/02 21/02 02/22 02/23 02/24 02/25 02/26 02/27 02", "/28 02/29 01/03 02/03 03/03 03/04 05/03 03/06 07/0", "3 03/08 03/09 10/03 11/03 03/12 13/03 03/14 15/03 ", "03/16 03/17 18/03 19/03 20/03 21/03 03/22 23/03 03", "/24 03/25 26/03 03/27 28/03 29/03 30/03 03/31 01/0", "4 04/02 03/04 04/04 04/05 04/06 04/07 08/04 04/09 ", "10/04 04/11 04/12 13/04 04/14 04/15 04/16 04/17 04", "/18 19/04 04/20 04/21 04/22 23/04 04/24 04/25 04/2", "6 04/27 04/28 04/29 04/30 01/05 02/05 05/03 05/04 ", "05/05 05/06 05/07 08/05 09/05 05/10 11/05 12/05 05", "/13 05/14 05/15 16/05 17/05 05/18 05/19 20/05 21/0", "5 22/05 05/23 05/24 05/25 26/05 05/27 05/28 29/05 ", "05/30 05/31 06/01 02/06 03/06 04/06 05/06 06/06 07", "/06 08/06 09/06 06/10 06/11 06/12 06/13 06/14 15/0", "6 06/16 06/17 18/06 19/06 06/20 06/21 06/22 23/06 ", "24/06 25/06 26/06 06/27 06/28 29/06 30/06 07/01 02", "/07 07/03 07/04 05/07 07/06 07/07 08/07 07/09 07/1", "0 07/11 07/12 07/13 07/14 07/15 07/16 17/07 18/07 ", "19/07 20/07 07/21 22/07 07/23 24/07 07/25 07/26 27", "/07 07/28 07/29 30/07 07/31 08/01 08/02 03/08 04/0", "8 05/08 08/06 08/07 08/08 09/08 10/08 08/11 12/08 ", "08/13 14/08 08/15 16/08 08/17 08/18 19/08 08/20 21", "/08 08/22 23/08 08/24 25/08 26/08 08/27 28/08 08/2", "9 08/30 31/08 09/01 02/09 09/03 09/04 05/09 09/06 ", "09/07 08/09 09/09 10/09 11/09 09/12 13/09 14/09 15", "/09 16/09 09/17 09/18 09/19 20/09 09/21 22/09 09/2", "3 24/09 25/09 09/26 27/09 09/28 09/29 30/09 10/01 ", "10/02 03/10 10/04 10/05 06/10 07/10 08/10 09/10 10", "/10 10/11 10/12 10/13 14/10 15/10 10/16 17/10 10/1", "8 19/10 10/20 21/10 10/22 10/23 24/10 10/25 26/10 ", "10/27 28/10 10/29 30/10 31/10 11/01 11/02 03/11 04", "/11 11/05 06/11 07/11 11/08 09/11 11/10 11/11 12/1", "1 11/13 11/14 15/11 16/11 11/17 18/11 11/19 11/20 ", "11/21 11/22 23/11 24/11 11/25 26/11 27/11 28/11 11", "/29 30/11 12/01 12/02 03/12 12/04 12/05 12/06 07/1", "2 12/08 09/12 10/12 12/11 12/12 12/13 14/12 12/15 ", "12/16 12/17 12/18 12/19 12/20 12/21 22/12 12/23 24", "/12 12/25 12/26 27/12 28/12 29/12 30/12 12/31"}},  {"01/01 01/02 01/03 01/04 01/05 01/06 01/07 01/08 01/09 01/10 01/11 01/12 01/13 01/14 01/15 01/16 01/17 01/18 01/19 01/20 01/21 01/22 01/23 01/24 01/25 01/26 01/27 01/28 01/29 01/30 01/31 02/01 02/02 02/03 02/04 02/05 02/06 02/07 02/08 02/09 02/10 02/11 02/12 02/13 02/14 02/15 02/16 02/17 02/18 02/19 02/20 02/21 02/22 02/23 02/24 02/25 02/26 02/27 02/28 02/29 03/01 03/02 03/03 03/04 03/05 03/06 03/07 03/08 03/09 03/10 03/11 03/12 03/13 03/14 03/15 03/16 03/17 03/18 03/19 03/20 03/21 03/22 03/23 03/24 03/25 03/26 03/27 03/28 03/29 03/30 03/31 04/01 04/02 04/03 04/04 04/05 04/06 04/07 04/08 04/09 04/10 04/11 04/12 04/13 04/14 04/15 04/16 04/17 04/18 04/19 04/20 04/21 04/22 04/23 04/24 04/25 04/26 04/27 04/28 04/29 04/30 05/01 05/02 05/03 05/04 05/05 05/06 05/07 05/08 05/09 05/10 05/11 05/12 05/13 05/14 05/15 05/16 05/17 05/18 05/19 05/20 05/21 05/22 05/23 05/24 05/25 05/26 05/27 05/28 05/29 05/30 05/31 06/01 06/02 06/03 06/04 06/05 06/06 06/07 06/08 06/09 06/10 06/11 06/12 06/13 06/14 06/15 06/16 06/17 06/18 06/19 06/20 06/21 06/22 06/23 06/24 06/25 06/26 06/27 06/28 06/29 06/30 07/01 07/02 07/03 07/04 07/05 07/06 07/07 07/08 07/09 07/10 07/11 07/12 07/13 07/14 07/15 07/16 07/17 07/18 07/19 07/20 07/21 07/22 07/23 07/24 07/25 07/26 07/27 07/28 07/29 07/30 07/31 08/01 08/02 08/03 08/04 08/05 08/06 08/07 08/08 08/09 08/10 08/11 08/12 08/13 08/14 08/15 08/16 08/17 08/18 08/19 08/20 08/21 08/22 08/23 08/24 08/25 08/26 08/27 08/28 08/29 08/30 08/31 09/01 09/02 09/03 09/04 09/05 09/06 09/07 09/08 09/09 09/10 09/11 09/12 09/13 09/14 09/15 09/16 09/17 09/18 09/19 09/20 09/21 09/22 09/23 09/24 09/25 09/26 09/27 09/28 09/29 09/30 10/01 10/02 10/03 10/04 10/05 10/06 10/07 10/08 10/09 10/10 10/11 10/12 10/13 10/14 10/15 10/16 10/17 10/18 10/19 10/20 10/21 10/22 10/23 10/24 10/25 10/26 10/27 10/28 10/29 10/30 10/31 11/01 11/02 11/03 11/04 11/05 11/06 11/07 11/08 11/09 11/10 11/11 11/12 11/13 11/14 11/15 11/16 11/17 11/18 11/19 11/20 11/21 11/22 11/23 11/24 11/25 11/26 11/27 11/28 11/29 11/30 12/01 12/02 12/03 12/04 12/05 12/06 12/07 12/08 12/09 12/10 12/11 12/12 12/13 12/14 12/15 12/16 12/17 12/18 12/19 12/20 12/21 12/22 12/23 12/24 12/25 12/26 12/27 12/28 12/29 12/30 12/31"} },
    // Your custom test goes here:
    //{ { {}}, {} },
};}

//------------------------------------------------------------------------------
// Tester code:
    //#define DISABLE_THREADS
    #include "tester.cpp"
    struct input {
        vector<string> p0;

        string run(DateFormat* x) {
            return x->fromEuropeanToUs(p0);
        }
        void print() { Tester::printArgs(p0); }
    };
    
    int main() {
        return Tester::runTests<DateFormat>(
            getTestCases<input, Tester::output<string>>(), disabledTest, 
            600, 1486131837, CASE_TIME_OUT, Tester::COMPACT_REPORT
        );
    }
// CUT end