## Wednesday, December 30, 2015

### Codeforces 586F - Lizard Era: Beginning

Problem Statement:
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;
}