USACO 4.3 Letter Game

The basic idea is to use brutal force approach by enumerating all possible words generated from input word and choose the right ones. There are a couple of optimizations that we can do:

• There are at most two strings in each anwser, because the length constraints (3 is the minimum length, 7 is the maximum length, so at most two strings.).
• Similarly, since each word in dictionary is at least 3 characters long, we can skip sub strings with length 1 or 2 during enumeration.
• During enumeration, whenever we find the first substring is greater lexicographically than the second, we can abort because the same string pair can occur later (which is what we want, the lexicographically smaller ones). There are some edge cases to deal with here though, such as the second string is empty, in which case the first string would be the full length of the source string.
• The STL next_enumeration comes really handy.

#include <vector>
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

map<string,int> wordval;
set<string> used;
vector<string> ans;
vector<int> value = {2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7};
int ans1 = 0;
string word;

void compute() {
    sort(word.begin(),word.end());
    do {
        for(int i = 3; i <= (int)word.size(); ++i) {
            for(int j = i; j <= (int)word.size(); ++j) {
                string w1, w2, w;
                w1 = word.substr(0,i);
                w2 = word.substr(i,j-i);
                if (w1 > w2 && w2 != "") continue;
                if(!wordval[w1] || (!wordval[w2] && w2 != "")) continue;
                
                w = w1;
                if(!w2.empty())  {
                    w += " "; w += w2;
                }
                
                if(ans1 == wordval[w1] + wordval[w2] && !used.count(w)) {
                    used.insert(w);
                    ans.push_back(w);
                } else if(ans1 < wordval[w1] + wordval[w2]) {
                    ans1 = wordval[w1] + wordval[w2];
                    used.clear();
                    ans.clear();
                    used.insert(w);
                    ans.push_back(w);
                }
            }
        }
    } while (next_permutation(word.begin(),word.end()));
}

int main() {
    ifstream fdin("lgame.dict");
    ifstream fin("lgame.in");
    ofstream fout("lgame.out");
    
    string str;
    wordval[""] = 0;
    while(fdin >> str && str != ".") {
        int val = 0;
        for(int i = 0; i< (int)str.size(); ++i) {
            val += value[str[i] - 'a'];
        }
        wordval[str] = val;
    }

    fin >> word;
    cout << word << endl;
    compute();
    
    cout << ans1 << endl;
    fout << ans1 << endl;
    for(int i = 0; i < (int)ans.size(); ++i) {
        cout << ans[i] << endl;
        fout << ans[i] << endl;
    }
    
    return 0;
}