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;
}