586F - Lizard Era : Beginning

Solution:

This problem has a very cool hashing and look-up idea. (This method is described in the official editorial as well)

First break the array of l[i], m[i], and w[i] into two halves, namely the upper half and the lower half. This helps to reduce down the \(O(3^n)\) component to \(O(3^{n/2})\), which actually allows us to solve the problem given \(n \leq 25\).

Suppose the upper part gives us (a, b, c) as the sum of the chosen configuration of l[i], m[i], and w[i]. Similarly, we suppose (a', b', c') are the sum for the lower part. Hence our job is actually to find such (a', b', c') that \(a+a' = b+b' = c+c' \).

This condition can be rewritten as: given (a, b, c), find (a', b', c') such that \(a-b = -(a'-b')\) and \(b-c = -(b'-c')\). This equivalent form is very useful since we are now able to classify each of the upper and lower configurations in terms of their (a-b, b-c).

So suppose that we have already worked out all the possible configurations of the lower part and classified them into their (a'-b', b'-c') groups). Then for a given upper part configuration (a, b, c), we can zoom in to group (-(a-b), -(b-c)) and find which of the lower part configurations in that classification that gives the highest a+a' (or b+b', or c+c').

See, the grouping of lower part configurations is indeed similar to creating hash groups!

Now, suppose we fixed (a, b, c). We know that in class (-(a-b), -(b-c)), we only need to choose (a', b', c') such that a' is the largest in the group. Why, because it will gives us the highest a+a' possible for the given (a, b, c). Therefore, for each possible classification (a'-b', b'-c'), it suffices for us to store the one configuration with the highest a'.

The runtime complexity is now \( O(3^{n/2}) + O(3^{n/2} \log{(3^{n/2})}) \) which is roughly \( O(n3^{n/2})\), assuming that a C++ map is used.

Implementation:

#include <iostream> #include <cstdio> #include <algorithm> #include <map> #include <utility> #include <vector> #include <string> using namespace std; /* a+a' = b+b' = c+c' <=> a-b = -(a'-b') and b-c = -(b'-c') say (a-b, b-c) = (dab, dbc) are fixed we want to find another (dab', dbc') with dab = -dab' and dac = -dac' such that a+a' is maximised for a given (dab,dac) given two (dab', dac', a') and (dab*, dac*, a*) fixing a, we will want max(a', a*) transform a,b,c to key:[a-b, b-c], value:[a, path] */ int val[30][3]; int n; string path; map<pair<int,int>,pair<int,string> > m[2]; string mp[] = {"MW\n","LW\n","LM\n"}; map<pair<int,int>,pair<int,string> >::iterator iter, ater; int ans = (int) -1e9; string sp; void dfs(int k, int h, int x, int p, int q, int r) { if (h == 0) { if (k == 0) { iter = m[1].find(make_pair(-p+q,-q+r)); if (iter != m[1].end()) { if (ans < p + iter->second.first) { ans = p + iter->second.first; ater = iter; sp = path; } } } else { iter = m[k].find(make_pair(p-q,q-r)); if (iter != m[k].end()) { if (iter->second.first < p) { iter->second.first = p; iter->second.second = path; } } else { m[k][make_pair(p-q,q-r)] = make_pair(p, path); } } return; } path += mp[0]; dfs(k, h-1, x+1, p, q+val[x][1], r+val[x][2]); path.erase(path.size()-3); path += mp[1]; dfs(k, h-1, x+1, p+val[x][0], q, r+val[x][2]); path.erase(path.size()-3); path += mp[2]; dfs(k, h-1, x+1, p+val[x][0], q+val[x][1], r); path.erase(path.size()-3); } int main(){ scanf("%d",&n); for(int i=0;i<n;++i){ for(int j=0;j<3;++j){ scanf("%d",&val[i][j]); } } if (n == 1) { for(int i = 0; i < 3; ++i) { int j = (i+1)%3; if (val[0][i] == val[0][j] && !val[0][i]) { cout << mp[(i+2)%3]; return 0; } } printf("Impossible\n"); return 0; } int h = n/2; dfs(1, h, n-h, 0, 0, 0); dfs(0, n-h, 0, 0, 0, 0); if (ans > (int) -1e9) { //printf("%d\n",ans); cout << sp; cout << (ater->second.second); } else { printf("Impossible\n"); } return 0; }