ADDED SRM/TCO17-2B-U/1A.cpp Index: SRM/TCO17-2B-U/1A.cpp ================================================================== --- SRM/TCO17-2B-U/1A.cpp +++ SRM/TCO17-2B-U/1A.cpp @@ -0,0 +1,113 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class DengklekGaneshAndChains { public: + string getBestChains(vector chains, vector lengths) + { + for (string& chain : chains) + chain = make_it_lex_last(chain); + sort(chains.begin(), chains.end()); + + string ans; + for (int len : lengths) + { + string s = chains.back().substr(0, len); + for (size_t i = 0; i < chains.size(); ++i) + if(chains[i].substr(0, len) == s) { + ans += s; + chains.erase(chains.begin() + i); + break; + } + } + return ans; + } + + string make_it_lex_last(const string& s) + { + string t = s; + for (size_t i = 1; i < s.size(); ++i) + t = max(t, s.substr(i) + s.substr(0, i)); + return t; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const string& Expected, const string& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, DengklekGaneshAndChains().getBestChains(chains, lengths));} +int main(){ + +CASE(0) + string chains_[] = {"topc", "oder", "open", "twob"}; + vector chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); + int lengths_[] = {2, 1, 3}; + vector lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); + string _ = "wotrod"; +END +CASE(1) + string chains_[] = {"ssh", "she", "see", "sea"}; + vector chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); + int lengths_[] = {2, 3, 2, 3}; + vector lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); + string _ = "ssshesesee"; +END +CASE(2) + string chains_[] = {"wri", "ter", "who", "are", "you"}; + vector chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); + int lengths_[] = {3}; + vector lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); + string _ = "you"; +END +CASE(3) + string chains_[] = {"harus", "imfyo"}; + vector chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); + int lengths_[] = {5, 5}; + vector lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); + string _ = "yoimfushar"; +END +/* +CASE(4) + string chains_[] = ; + vector chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); + int lengths_[] = ; + vector lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); + string _ = ; +END +CASE(5) + string chains_[] = ; + vector chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_)); + int lengths_[] = ; + vector lengths(lengths_, lengths_+sizeof(lengths_)/sizeof(*lengths_)); + string _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/TCO17-2B-U/1B.cpp Index: SRM/TCO17-2B-U/1B.cpp ================================================================== --- SRM/TCO17-2B-U/1B.cpp +++ SRM/TCO17-2B-U/1B.cpp @@ -0,0 +1,188 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +struct UnionFind +{ + vector uf, sz; + int nc; + + UnionFind(int N) : uf(N), sz(N, 1), nc(N) + { + for (int i = 0; i= sz[b]) swap(a, b); + uf[a] = b; + sz[b] += sz[a]; + --nc; + } + return (a != b); + } +}; + +static const unsigned MODVAL = 1000000007; + +class DengklekGaneshAndTree { public: + int getCount(string labels, vector parents) + { + const int N = labels.size(); + + vector> children(N); + UnionFind uf(N); + for (int i = 1; i < N; ++i) { + int u = parents[i-1], v = i; + children[u].push_back(v); + if (labels[u] == labels[v]) + uf.Union(u, v); + } + + vector level(N); + { + function rec; rec = [&](int v, int lv) { + level[v] = lv; + for (int u : children[v]) + rec(u, lv + 1); + }; + rec(0, 0); + } + + map lb, ub; + for (int v = 0; v < N; ++v) { + int r = uf.Find(v), lv = level[v]; + if (lb.count(r) == 0) { + lb[r] = lv; + ub[r] = lv; + } + else { + lb[r] = min(lb[r], lv); + ub[r] = max(ub[r], lv); + } + } + + vector> rng; + for(auto kv : lb) + rng.emplace_back(kv.second, ub[kv.first]); + int L = *max_element(level.begin(), level.end()); + return solve(rng, L); + } + + // Number of ways to cover [0,L] by choosing subset of |rng|s. + int solve(vector> rng, int L) { + sort(rng.begin(), rng.end()); + + function rec; + vector memo(rng.size() * (L+2), -1); + rec = [&](int i, int coveredUpto) { + if (i == rng.size()) + return coveredUpto == L ? 1 : 0; + + const int key = i*(L + 1) + (coveredUpto+1); + if (memo[key] != -1) + return memo[key]; + + if (coveredUpto + 2 <= rng[i].first) + return memo[key] = 0; + return memo[key] = (rec(i + 1, coveredUpto) + rec(i + 1, max(coveredUpto, rng[i].second))) % MODVAL; + }; + return rec(0, -1); + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, DengklekGaneshAndTree().getCount(labels, parents));} +int main(){ + +CASE(0) + string labels = "seems"; + int parents_[] = {0, 1, 0, 3}; + vector parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_)); + int _ = 5; +END +CASE(1) + string labels = "like"; + int parents_[] = {0, 0, 0}; + vector parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_)); + int _ = 7; +END +CASE(2) + string labels = "a"; + vector parents; + int _ = 1; +END +CASE(3) + string labels = "coincidence"; + int parents_[] = {0, 1, 2, 0, 2, 1, 4, 7, 7, 6}; + vector parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_)); + int _ = 218; +END +CASE(4) + string labels = "topcoderopenroundtwobgoodluckhavefun"; + int parents_[] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0}; + vector parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_)); + int _ = 147418098; +END +/* +CASE(5) + string labels = ; + int parents_[] = ; + vector parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_)); + int _ = ; +END +CASE(6) + string labels = ; + int parents_[] = ; + vector parents(parents_, parents_+sizeof(parents_)/sizeof(*parents_)); + int _ = ; +END +*/ +} +// END CUT HERE